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