Re: [boost] generative geometry algorithms library idea

Subject: Re: [boost] generative geometry algorithms library idea
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2008-09-26 17:46:28

--------------------------------------------------
From: "Barend Gehrels" <barend_at_[hidden]>
Sent: Friday, September 26, 2008 3:56 PM
To: <boost_at_[hidden]>
Subject: Re: [boost] generative geometry algorithms library idea

> Hi Brandon,
>

Hi Barend,

> Interesting to see another geometry library appearing into the Boost list. 
> It definitely shows the need of such a library in the Boost community.
>
> I don't know if you followed the list this year. In January and in March I 
> posted two previews of a geometry library, based on similar concepts as 
> the library you posted: generic, based on templates, header only, defines 
> points, lines and polygons (which might have holes, this is probably a 
> difference) and has operations on these. It also has 2D/3D possibilities.
>

I actually haven't followed the list for a few years :-).

I did do a browse of your library before I started, but I found that it 
didn't do exactly what I was looking to do. I have been working on a legacy 
geometry library for many year which has some algorithms which are 
proprietary, but is sorely lacking of others which are not generally 
available under free license for the commercial domain.  This means that I 
need to retain the use of the legacy primitives, but also that I would like 
to develop some of the new sorely needed algorithms (boolean ops, doubly 
connected edge lists) and at the same time be able to develop new primitives 
which can use exact precision types in these same newly developed 
algorithms. My only choice was to develop all my algorithms to a defined set 
of traits for the concepts of points, segments and point sequences. So the 
algorithms in my library are actually built to work with any primitives for 
which traits for point, segment, and point sequence (polylines,polygons) 
have been specialized. All the algorithms are implemented to access 
underlying coordinate values and to construct the points, segments, and 
point sequences using static methods specialized in the traits classes.  I 
think this is perhaps significantly different to what your library does 
(although I didn't see any higher level algorithms like the bentley-ottmann 
sweep line, trapezoidal decomposition, binary search partition trees, and 
boolean operations so maybe you have done similar since last posting to the 
vault.)  Could you post a current version so I have some basis for proper 
comparison?

Also, there are some other issues with respect to using custom number types 
which may not use math function like std::sqrt or the trig functions which 
may require specialization of math_function traits for the coordinate type. 
I had to do this in order to use mpq_class (rational exact type in GMP) so 
that I could get distances between two points :-).  (In the end its going to 
require defining a generic Taylor series expansion for all the trig + sqrt 
functions that support number types as template parameters.)

The same goes for constants. How is PI defined for mpq_class etc? Something 
users should explicitly control depending on their precision requirements.

How does your library deal with number comparisons for floating types and 
precision issues?

> Based on these previews there has been much discussion on the list, 
> especially about the underlying concepts and how explicit they were made 
> in the library code.
>
> Bruno Lalande, Boost-contributor and active member of the Boost community, 
> joined and together we worked on the concepts of the library, making them 
> more explicit. We planned to republish it in June but, as often, this was 
> delayed somewhat. However, we're still enthousiastic and hope to publish a 
> new preview within a month.
>
> You might consider to look at our work to see if it is worth to merge with 
> us, if it is valuable for you as a source of inspiration or if it is worth 
> to join us. It's actually open source already and still intended to be 
> submitted as a Boost library. Also, note that there is a Google Summer of 
> Code project mentored by Boost which is based on this library.
>

>From looking at the library in the vault, I seem to have implemented all the 
algorithms you have so far + have more functionality in my library ;-). Plus 
I need to support legacy primitives in my algorithms as I said before which 
doesn't seem possible with your library. Please send your latest so I can 
make a more fair appraisal. :D

Very respectfully,

Brandon

>
> Best regards,
> Barend Gehrels, Geodan, Amsterdam, the Netherlands
> Bruno Lalande, France
>
>
>
>
> Brandon Kohn wrote:
>> Hi all,
>>
>> I've been doing some work for the past few weeks on a generative/generic 
>> 2D geometry library (leaving open the possibility for 3D in the future). 
>> The idea is for all the algorithms to be generative taking coordinate, 
>> point, segment, polyline/gon types as template parameters (or deducing 
>> where presented as nested typedefs) and specialized traits types for 
>> accessing type traits and methods ( things like 
>> access_traits<point_type>::get_x( point ) .). So far the library has 
>> allowed me to work with the same algorithms in native floating type and 
>> exact types like gmp's mpq_class. It's just a first rough draft of ideas, 
>> and I would really like some input from the community to see if I'm on 
>> the right track for something that boost would be interested in having. 
>> I'll post a copy of the lib in the vault. It's header only (with a small 
>> testbed with trivial testing and a visual studio 2008 solution/project). 
>> I hope there should not be too many issues compiling these tests/headers 
>> under
> ot
>>  her platforms.
>>
>> I'll put it in the vault as generative_geometry_algorithms.zip
>>
>> link:
>> http://www.boostpro.com/vault/index.php?action=downloadfile&filename=generative_geometry_algorithms.zip&directory=Math%20-%20Geometry&
>>
>> Thanks for any constructive input.
>>
>> With regards,
>>
>> Brandon Kohn
>> _______________________________________________
>> Unsubscribe & other changes: 
>> http://lists.boost.org/mailman/listinfo.cgi/boost
>>
>>
>>
>
>
>
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
>