Re: [boost] generative geometry algorithms library idea

Subject: Re: [boost] generative geometry algorithms library idea
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2008-10-04 14:43:47

--------------------------------------------------
From: "Paul A Bristow" <pbristow_at_[hidden]>
Sent: Thursday, September 25, 2008 12:06 PM
Newsgroups: gmane.comp.lib.boost.devel
To: <boost_at_[hidden]>
Subject: Re: generative geometry algorithms library idea

>
>
>>-----Original Message-----
>>From: boost-bounces_at_[hidden]
>>[mailto:boost-bounces_at_[hidden]] On Behalf Of Brandon Kohn
>>Sent: 22 September 2008 21:29
>>To: boost_at_[hidden]
>>Subject: [boost] generative geometry algorithms library idea
>

Hi Paul,

Thank you for having a look and providing useful feedback.

>>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.
>
> This all looks interesting stuff of course.
>
> And the use of templates is adventurous.  I trust it does not mean that 
> the need for both compile and runtime speed won't lead some
> to reject the library outright.

I wouldn't really expect this to be much of an issue. I have been using 
variants of this stuff is a fairly large sized projects. The templates have 
an insignificant impact on compile times in my experience.

>
> I presume one could also use it with other arbitrary (but inexact) 
> precision libraries?
>

Yes, that is the goal. It remains to be proven of course as the interfaces 
get hammered into shape.

> Past discussions on geometry have not produced a consensus on design/spec 
> :-((
>

I've noticed this. I waited for awhile (vacation) to respond to this email 
to see if there was anymore feedback. There seems not to be a very vocal 
geometry user base in the boost dev lists. The only people who have 
responded to my request for feedback seem to be other geometry library 
writers, and from those responses, I didn't really get the sense that they 
had really investigated what my library tries to do (I.e. all talk about 
merging with their works with little feedback about the substance of my 
library.) The notion of a concept driven traits based interface is a bit 
different than simply having users define their points in terms of a 
boost::point type. Same for the segments and polygons/lines. With my library 
I'm really trying to define an interface where any user defined geometry 
type can be used and the traits specialized on their type provide the 
necessary mechanisms for interaction with the algorithms in the library. I 
do define a point, and segment type (and point sequences based on 
std::vector of those defined point types) for the native coordinate types, 
but it isn't intended that these types are forced onto the users. The 
concrete primitive types I define really are for convenience only (or for 
internal usage in some instances).

I have continued working on my library, refining some of the interface 
definitions and algorithms. I've added polygonal boolean operations based on 
binary search partition trees in 2D and a doubly_connected_edge_list class 
based on boost::graph (similar to a planar graph except with directed 
edges). I've also added code for the Bentley-Ottmann sweep to differentiate 
between floating point and integral coordinates (specialized via a 
coordinate_traits< C > class) so the sweep line segment comparison functor 
will use boost::rational< IntegerCoordinate > to do the sweepline segment 
intersection comparisons when the points use integer coordinates (this is 
necessary to avoid slope truncation and correct intersect y value 
interpolation.) I will be doing some more testing and then will put the 
latest version up on the vault.

So still plodding away, and hoping for more feedback.

> So you may prefer to ignore that and simply present your version.
>
> There is the little matter of some documentation ;-)
>

I'm still trying to finalize some design issues and would like to complete 
that before writing documentation. Soon hopefully!

> Paul
>
> PS I see you have neatly 're-solved' the floating point comparison 
> problems, and present them in a more generally useful form that
> in Boost.Test.  I find the function names a step too long, but I feel that 
> they would be most useful as a independent module.

Thanks again Paul. I also agree with your assessment that the number 
comparison functors for floating point should be put into a stand-alone 
number comparison library under numeric. These are issues that arise all the 
time in developing fuzzy number comparison algorithms and precision 
tolerance mechanisms. The names I chose are a bit long in the tooth, but I 
prefer long explanatory names (which in practice are declared infrequently) 
to short names which obscure meaning. I would of course be open to hearing 
any reasonable suggestions as alternates.

Cheers Paul,

Brandon

>
> ---
> Paul A Bristow
> Prizet Farmhouse, Kendal, Cumbria UK LA8 8AB
> [phone] & SMS, Mobile [phone] & SMS
> pbristow_at_[hidden]
>
>
>
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost
>