Re: [boost] [geometry] area, length, centroid, behavior

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-03-05 11:18:27

Michael Fawcett wrote:
>> I also think
>> that Lucanus Simonson's work could co-exist in some other library or
>> extension since he only works with polygons that have angles of
>> multiples of 45 degrees (or something like that, I'm not sure on
>> specifics).
> 
Bruno Lalande wrote:
> It's also my feeling but I can't be affirmative until I take a closer
> look at his library. But indeed, as 45 degrees computations are
> clearly a specific domain, it would belong in an extension, like GIS.

What was true of my library eight months ago has changed recently as I have added full support for arbitrary angle geometry.  I have implemented 100% numerically robust integer polygon clipping operations (AND, OR, NOT, XOR) based upon my N-layer scanline algorithm that produces all geometries with unique sets of overlapping input layers.  When the number of input layers is two it can be used for Booleans, but we collapse the entire layer stack of an Intel microprocessor (dozens of input layers) including circular and non-manhattan, non-45 package layout using a single pass of this algorithm.

When I say 100% numerically robust integer polygon operations I mean that any input polygons with 32-bit integer coordinates will produce an output that closely approximates the idealized output which is representable only with inifinite precision rational coordinates.  Details of how I accomplish this will be presented at boostcon.  The algorithm is of course parameterized by coordinate data type and with the appropriate traits 64-bit integer would also be robust.  Floating point will work up to a point, and requires some further effort to support in a way that would make fans of floating point coordinates happy.  Collaboration with Brandon or Barend to get the floating point robustness right would be appreicated since I don't care to reinvent a wheel I don't expect to use.

>> I also think that they should use the same concepts and
>> tags where appropriate.
> 
> Yes definitely.
> 
Definitely.

>> I'm ambivalent as to whether they would be separate libraries or
>> simply extensions to a Boost.Geometry library as long as they work
>> together.

There will initially be several implementations of some algorithms.  It will be difficult to choose which ones to make "the" library algorithm because there will be semantic differences in their behavior and in the way their approaches to robustness produce slightly different outputs.  GIS may have different requirements than VLSI, which has different requirements than physical modeling.  It will take some time to unify these requirements in a single implementation to a provides a superset of the specifc needs of (most) everyone who might want to use it.
 
> This is something I had thought about. I was wondering if all the
> library authors could produce a kernel together, and continue to work
> separately but on this same kernel. And the kernel would be proposed
> as Boost.Geometry before any other more specific work. But I have to
> elaborate all this, it's a bit unclear to me for now...

This sounds fine to me.  I have already released my concepts based API to internal users who are very happy with it.  Changes to the names of concepts and mechanisms of generic function overloading would be easy for them to accommodate as long as I can do with an eventual boost geometry concepts type sytem what I can currently do with what I have.  I will be sure to point out which design decisions are important for me to support my exisiting API.

>> See above.  As a side note: I don't think kernel is really the best
>> term for this piece of the library.  I know it's central, but it
>> isn't the central computing mechanism of the library since it
>> doesn't really compute anything.
> 
> I chose this term because the same term is used in CGAL. I thought
> what they call "kernel" was precisely the concepts part of the
> library, but maybe I'm wrong, I don't know much that library.
> 
Funny you should mention CGAL, I have been clarifying the way in which CGAL's type system works to include discussion of it in my paper.  CGAL kernel is not in anyway analogous to our concepts core.  They use the term concept in their documentation, but its definition is different.  It is merely a mechanism for them and their users to easily define new geometry data types that are able to interoperate with their API, not a way to allow data types that don't depend on CGAL header files to interoperate with their API.  That is not possible with CGAL, but I am told they are considering adding it.

We should not use the term kernel.  I would treat it as almost as sacrosanct as a registered trademark and steer clear of comfusing people by avoiding it.  I suggest geometry concepts core.

>> I think this is a good direction to take.  I know both parties will
>> be reluctant since they have invested so much time and effort, but
>> surely it would be better for the community.
> 
> For sure it would be better. And the fact of trying to "extract" a
> kernel from both library is much less frustrating than forcing one to
> give up the core of his work. We don't throw anything away, we rather
> take the "quintessence" of each one.

I am not reluctant to collaborate.  We will have a boost geometry library much sooner by working together than by competing.  It is not really accurate so say both parties, however, because Brandon Kohn, while not as vocal as myself, has proposed a goeometry library at least equal merit.   
Ideally I'd like to see Brandon also attend boostcon so that we can all sit down together and hash out what the concepts core of a boost-geometry library will look like.  I would be happy to implement such a design if we can come to a consensus on its goodness.  I can easily ensure portability to gcc, MSVC and edg based compilers such as icc.

Regards,
Luke