Re: [boost] [GTL] - geometric template library - determininginterest

From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2007-10-04 22:57:29

>> In addition to that, GTL supports 45 degree polygons as well.
>
Fernando Cacciola wrote:
>What exactly is a 45 degree polygon?
>(45 degree is *one* direction, but a poygon has many sides)
>
>Or do you mean that you can create a polygon as the overlay of rectangles 
>alinged on a 45 degree axis?
>
>I that case, what about the other two sides of the rectangle? (that is, do 
>you support parallelograms or just rectangles)?
>
>And in that case too, can you overlay a 45º rect with a Horzontal rect? (I 
>guess yes)

Your confusion is quite natural since we haven't submitted the code yet.  At this stage, we should focus on clarifying what we are proposing submitting as opposed to details that could be answered by simply reading the code.  In this case the answer is of central importance in understanding the nature of the submission.  The algorithm is vertex based (not rectangle based as you had surmised.) It is an optimal implementation of the classical scanline algorithm for line segment intersection applied to Boolean operations over polygons (sequences of verticies) and handles all the "degenerate" cases that text books wave their hands at.  It does not support arbitrary angles, and is limited to vertical, horizontal and 45 degree diagonal edges.  In this way it can apply exact integer arithmetic and achieve maximal performance for that special case of data.  Intel happens to handle terabytes of such data on a daily basis, so we have an obvious need for such.  My team also has an older arbitrary angle Booleans implementation (not mine and not up to boost standards) so I'm not bluffing when I say we could contribute such in the near future.

The question we all need to answer is if it is appropriate for boost.  If it were nothing more than an industrial strength computational geometry algorithm the answer would probably be no.  The important thing about the library is not so much *what* it does but *how*.  As a library writer in an industrial setting I am faced with a challenge of how to overcome the complexity created by an explosion of C++ geometry types in numerous legacy applications.  Integrating a superior library capability into pre-existing applications is a challenge due to type incapability.  The important thing about my library is that I have solved that problem by applying C++ Concepts, inheriting my types from the template parameter, to allow a minimal concept map to provide the interface between my algorithms and the legacy system's geometry data types.  We got so caught up in explaining to boost what we did that we forgot to mention why.

These algorithms are of sufficient interest to Intel that we had half a dozen different (all suboptimal) implementations of them extant in multiple different legacy applications in my department alone.  They are of interest to many of other companies, as well, each with their own implementations.  My goal was not only to implement a superior library but also to minimize the effort required to integrate that library into the many legacy applications while not compromising on performance.  The way I did that by applying C++ Concepts to overcome the problem of type incompatibility is of general interest to C++ library development.  It ought to be easy for anyone to replace their legacy algorithms with mine if it were a boost library.

As I see it, the value of boost is much bigger than the usefulness of the libraries.  Boost is a way to teach a new generation of C++ developers how to make better use of the language by the example of the code that is shared.  The usefulness of the libraries is just the bait to get people to read the code and learn from it.  I think my library is useful enough that people will read the code and I think they will learn from it.  That is why I am submitting my library to boost.

P.S. my point2d data structure is a class encapsulated array of size 2.  You can override it with your own, of course, through the template inheritance generic interface.
 
Lucanus Simonson