Boost logo

Boost :

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

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,


> 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
>> link:
>> Thanks for any constructive input.
>> With regards,
>> Brandon Kohn
>> _______________________________________________
>> Unsubscribe & other changes:
> _______________________________________________
> Unsubscribe & other changes:

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