-------------------------------------------------- From: "Michael Marcin" <mike.marcin@gmail.com> Sent: Tuesday, September 23, 2008 1:37 PM Newsgroups: gmane.comp.lib.boost.devel To: <boost@lists.boost.org> Subject: Re: generative geometry algorithms library idea

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 va ult. 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.

Apologies I haven't looked at your library yet but is it likely that the algorithms will be usable with eigen2* data types? Eigen2 seems to be the best open source small vector/matrix library right now for performance. At least that I can find.

* http://eigen.tuxfamily.org/

Thanks,

-- Michael Marcin

HI Michael, I wouldn't see any reason why it wouldn't. The basic rationale for representation of primitives is that their numeric traits, dimension etc are embedded in a point_traits<> specialization. Access functions are specified in a separate traits specialization. There are a couple of ways you can use the code: (apologies if the format doesn't come out right... this is my first time posting code) For example, say you have a vector type for your point: (eigen seems to use: VectorXf ) BOOST_DEFINE_USER_POINT_TRAITS( VectorXf, float, 2 );//note the 2 is dimension. template <> struct cartesian_access_traits< VectorXf > { typedef VectorXf point_type; typedef boost::numeric::geometry::point_traits< VectorXf

::coordinate_type coordinate_type; typedef boost::numeric::geometry::point_traits< VectorXf>::dimension_type dimension_type;

static inline coordinate_type get_x( const point_type& p ) { return p[0]; } static inline coordinate_type get_y( const point_type& p ) { return p[1]; } //Note, the template requirement here is due to some experimentation I'm doing on how to deal with different dimensions and the //construct member functions specification both 2 and higher dimensions. //I wanted to make use the enable_if/disable_if based on the point_traits<>::dimension_type and to do that, you have to be in a template member function //(at least in visual studio) template <typename Point> static inline point_type construct( const coordinate_type& x, const coordinate_type& y ) { point_type p(dimenstion_type::value); p[0] = x; p[1] = y; return p; } }; BOOST_DEFINE_SEGMENT_TRAITS( VectorXf, segment< VectorXf > ); BOOST_DEFINE_SEGMENT_ACCESS_TRAITS( segment< VectorXf > ); Here is a specialization I did for the GMP rational type using the point template provided with my code: typedef point<mpq_class, 2> point_rational_2d; BOOST_DEFINE_POINT_TRAITS( point_rational_2d ); BOOST_DEFINE_CARTESIAN_ACCESS_TRAITS( point_rational_2d ); BOOST_DEFINE_SEGMENT_TRAITS( point_rational_2d, segment< point_rational_2d

); BOOST_DEFINE_SEGMENT_ACCESS_TRAITS( segment< point_rational_2d > );

You can then use the points as-is in the algorithms: For example: BOOST_AUTO_TEST_CASE( TestIntersections ) { using namespace boost::numeric::geometry; typedef cartesian_access_traits< VectorFx > point_access; VectorFx p1 = point_access::construct< VectorFx >( 0., 0. ); //I agree... it's annoying to have the point type specified here as a template parameter. VectorFx p2 = point_access::construct< VectorFx >( 1., 1. ); VectorFx p3 = point_access::construct< VectorFx >( 1., 0. ); VectorFx p4 = point_access::construct< VectorFx >( 0., 1. ); segment< VectorFx > seg1( p1, p2 ); segment< VectorFx > seg2( p3, p4 ); VectorFx xPoints[2]; intersection_type iType = intersect( seg1, seg2, xPoints, fraction_tolerance_comparison_policy<float>(1e-5) ); std::cout << iType << " at point: " << point_access::get_x( Points[0] ) << ", " << point_access::get_y( xPoints[0] ) << std::endl; } This is still very much a work in progress, but please do have a look and see what you think. I'd like to hear suggestions about the design or how I might improve things. Cheers, Brandon

Hi Brandon, 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. 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. 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

-------------------------------------------------- From: "Paul A Bristow" <pbristow@hetp.u-net.com> Sent: Thursday, September 25, 2008 12:06 PM Newsgroups: gmane.comp.lib.boost.devel To: <boost@lists.boost.org> Subject: Re: generative geometry algorithms library idea

...

-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Brandon Kohn Sent: 22 September 2008 21:29 To: boost@lists.boost.org 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@hetp.u-net.com

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost