Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Thomas Klimpel (Thomas.Klimpel_at_[hidden])
Date: 2009-09-01 19:02:51

John Phillips wrote:
> This will not cause a problem in many applications, but in any
> setting where large and small scales mix (such as polygons that are just
> off of regular, but need to be precisely defined; or systems that mix
> large and small polygons) there will be no scaling for the integers that
> both preserves the needed dynamic range and the needed precision.

As strange as it sounds, VLSI is exactly such a domain where the mixing of large and small scales occur, but floating point coordinates are not the complete solution in this case.
The mixing of scales happens as follows: The "global design" is build from smaller building blocks. The small building blocks (referred to as cells) are described in a local coordinate system around the origin. Larger cells then refer these smaller cells and apply a similarity transformation to them. The accuracy within the small cells is in the order of nm (1e-9m) but the coordinates in the "global design" are in the order of cm (1e-2m). So the ~9 digits of a 32-bit integer are luckily just enough, but I think nevertheless that this scenario is quite typical for settings where large and small scales mix.

The mixing is made possible by the translation and rotation invariance of the euclidean plane. Fixed point numbers nicely preserve the translation invariance, and also 90 degree rotation invariance. Arbitrary angle rotations are luckily quite rare in typical applications, but I guess that many of the current tools won't handle arbitrary angle rotations too well (they will probably still snap to the initial integer grid).

To support a mixing of scale would hence be more difficult than just providing support for floating point coordinates. You would also need be able to handle similarity transformations (possibly also with different coordinate types than the polygons) assigned to groups of polygons.

The good thing about fixed point coordinates is that they preserve the translation invariance of the euclidean plane much better than floating point coordinates. (In a certain sense, the 45 degree special case is possible because of the invariance against translation along the diagonal of the grid. This means that a 26.565/63.439 degree special case would probably also be possible, but I guess no one will care for that special case.)

So from my point of view, support for floating point coordinates would be a convenience feature, and possibly also a "performance" feature for a sufficiently good implementation of the floating point algorithms. But you shouldn't require "impossible" postconditions from the results in that case, because the "performance" benefit will otherwise quickly be lost again.

As you probably know, the discussions about the "impossible" postconditions (or which postconditions would be reasonable) were not really settled:
http://lists.boost.org/Archives/boost/2009/03/149515.php
http://lists.boost.org/Archives/boost/2009/03/149693.php

Regards,
Thomas