Re: [boost] Preview 3 of the Geometry Library

Subject: Re: [boost] Preview 3 of the Geometry Library
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2008-10-22 13:19:37

Mathias wrote:
>I don't even know how one could define a polygon as a function in any
>coordinate system, by the way.

You define it as a piecewise linear logic inequality.  A planar polygon can be thought of as a function on x and y such that for any x and y that lies inside the polygon the function returns 1 and for any x and y that lies outside the polygon the function returns 0.  The actual mathematic expression for doing that isn't really interesting, but thinking of a polygon as a mathematical function is.  I take the partial derivative of a polygon in x and y to reduce it from something that is conceptually two dimensional to a series of zero dimensional quantities.  These quantities are impulse functions with either positive or negative sign at a given point with a given direction.  This means I can model them as positive or negative unit vectors.  When I scan those quantities, I am taking the integral with respect to x then y and I get back my original polygon.  When I scan many polygons this way I can do boolean logic operations on the 2D logic functions that are the input polygons.  Because of the way I model polygons the algorithm employs arithmetic rather than flow control to do the core computational effort.  Obviously, this approach extends easily into higher dimensional space at the conceptual level, but in practice, it is very hard to write an efficient n-1 dimensional sweep-plane algorithm due to a lack of suitable data structures, but it is easy to write a scan-line that handles the 2D case in near linear time using, for example, the stl red-black tree.

Figures that have curves are not piecewise linear and harder to take the derivative/integrate because there is no order reduction taking place.  In a different coordinate system the curves might be analogous to straight lines, allowing for order reduction, but the more common approach in computational geometry is to simply model the curves as their piecewise linear approximation and solve the problem in the Cartesian coordinate system.

While non-Euclidean geometries are undeniably valuable, I think that it is not worthwhile to try to generalize the geometry away from the geometry library.  Refactoring algorithms that are similar in different coordinate systems to be shared in their implementation is probably harder than duplicating that effort in separate libraries that target separate geometries.  I think it is preferable to design the library to interoperate well with other geometries, rather than try to encompass them.

Luke