Boost logo

Boost :

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.


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

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.


> 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


Fernando Cacciola

Boost list run by bdawes at, gregod at, cpdaniel at, john at