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
> +44 1539561830 & SMS, Mobile +44 7714 330204 & SMS
> pbristow_at_[hidden]
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://listarchives.boost.org/mailman/listinfo.cgi/boost
>