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

From: Fernando Cacciola (fernando_cacciola_at_[hidden])
Date: 2007-10-07 15:35:23

Simonson, Lucanus J wrote:
>>> 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.)
>
Ha, that's better.. much better.

I was confused by this sentence from Gyuszi:

 "The polygons need to be formed by union of axis-aligned rectangles, yes."

> 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.

Ha OK, I see.

> In this way it can apply exact integer
> arithmetic and achieve maximal performance for that special case of
> data.

Right.

>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.
>
Specially if the library is properly layered.
The sweepline process (used by your algo) has many edge-angle-independent 
parts that can be factored out.

> The question we all need to answer is if it is appropriate for boost.

I would say that at least the bottom layer is.

> 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*.

OK. This would be a good reason.

>  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.
>
OK.
There are different ways in which you can approach a concept-based design, 
but is clear that a good modern library must follow one.
Do expect some crictizism regarding the specific approach to concepts you 
have taken, but FWIW I like it better than the CGAL approach (which is also 
concept based).

>We got so caught up in
 explaining to boost what we did that we forgot to mention why.
>
It happens :)

> 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.
>
OK.

So one stated goal of your library is that it should be truly *generic*, 
meaning that a user should be abe to take some concrete facility and apply 
it to its own data structures.

> 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.

Indeed.

> The usefulness of the libraries is just the
> bait to get people to read the code and learn from it.

Being useful is one of the stated requirements for any boost library, but 
you have a point. If the library is really cool in the way it is designed 
and implemented, then one could argue that its usefullness lies exactly 
there.

Best

Fernando Cacciola