Arash Partow wrote:

Hi all,

I was wondering if there was anyone working on / managing the BOOST geometry libraries?

Yes, there were a few discussions on the list. Here is a list of threads I've saved: This is one of the latest and very interesting: http://lists.boost.org/Archives/boost/2002/09/36142.php and other: http://lists.boost.org/Archives/boost/2004/06/66736.php http://lists.boost.org/Archives/boost/2001/08/16400.php http://lists.boost.org/Archives/boost/2000/11/6612.php Also, there are some prototypes: http://www.boost-consulting.com/vault/index.php?direction=0&order=&directory=Math%20-%20Geometry

I can't seem to see if anyone has already put their hand up or not. I've noticed that it was a contender for the 2006 SoC, and that there are a couple of code samples in the BOOST vault.

Right.

In any case I'm planning on making a preliminary library submission sometime soon, I've been contact with one of the other code submitters, I just want to make sure there isn't an effort already underway, I've searched the mailing list, and have found anything of interest.

If anyone has any information about this topic, please feel free to comment as it would help a great deal.

I have no knowledge about any other efforts than listed above. I'm very interested in robust computational geometry library in Boost. So, I'd be also interested in some constributions. For last 6 months, I was working on the GEOS library: http://geos.refractions.net/ which is a *direct* port of JTS: http://www.vividsolutions.com/jts/jtshome.htm Unfortunately, GEOS follows JTS design and implementation almost step by step, so performance is not good. Note, GEOS is a library for GIS and it follows the OpenGIS Simple Features specification (www.opengeospatial.org/docs/99-049.pdf). I think, this specification may be interesting to read about "The Dimensionally Extended Nine-Intersection Model - DE-9IM" as a nice model of spatial/geometric relation operators.

As for a preliminary library design I propose the following:

* primitive geometric structures 2D/3D only (point,line,segment,triangle...) * operations between primitives (intersection, distance, inclusion...) * higher level algorithms in a structured fashion similar to BGL: * hulls, rotating caliper * triangulation (point sets, polygons) * boolean operations over polygons

Boolean operations could be provided for every geometry type, see DE-9IM.

Note: algorithms will be named based on method then algorithm type for example convex hull variations would be: 1. graham_scan_convex_hull(it_begin,it_end,out_it) 2. jarvis_march_convex_hull(it_begin,it_end,out_it) 3. gift_wrapping_convex_hull(it_begin,it_end,out_it) 4. quick_convex_hull(it_begin,it_end,out_it)

Good idea.

* precision related issues to be dealt with mainly by user specified floating point type, and partially at the algorithm level

JTS and GEOS have quite good example of precision model.

* keep code bloat and over-engineering to a minimum. ie: in cgal to determine whether or not 2 segments intersect you need roughly 35 lines of source code.

Should be something like the following:

boost::geometry { segment<T,D> seg1 = make_segment(....); segment<T,D> seg2 = make_segment(....); . . if (intersect(seg1,seg2)) ...; else ...; }

Good idea. How about creating segments and linestrings (string of segments)? I imagine it could be also possible to pass range of std:: containers with iterators. But I also think about avoiding copying data from std:: containers to segments. May be it could be possible to have segments-view over standard containers or sth like that (views in terms of http://www.zib.de/weiser/vtl/). Extension idea: I'd also have an idea about extension for data (de)serialization. In GIS, there are two major formats to save/read geometries WKT - Well-Known Text and WKB - Well-Known Binary. Both have been invented by OpenGIS Consortium. Here are good examples of WKT: http://dev.mysql.com/doc/refman/5.1/en/gis-wkt-format.html and WKB: http://dev.mysql.com/doc/refman/5.1/en/gis-wkb-format.html I have some prototype of Spirit based parser to read WKT. Best regards -- Mateusz Loskot http://mateusz.loskot.net

--- Arash Partow wrote:

Hi all,

Hello, Arash. I'd be more interested in *using* a geometry library than in developing one, so any feedback I provide in this regard would likely come from an interface point of view.

As for a preliminary library design I propose the following:

* primitive geometric structures 2D/3D only (point,line,segment,triangle...) * operations between primitives (intersection, distance, inclusion...) * higher level algorithms in a structured fashion similar to BGL: * hulls, rotating caliper * triangulation (point sets, polygons) * boolean operations over polygons

One of the great bugbears I have with today's implementations of geometric primitives is the lack of a common interface between all of them. Take a point, for instance: should I access its coordinates using the public members x, y, and z? Or is that X, Y, and Z (capitalized)? Are they actually member functions instead of data? How about the subscript operator ([0], [1], and [2])? (Personally, I'd go with this one, since that is what the BGL and uBLAS algorithms are currently used to, and a point can be extended to have more than three dimensions if need be. But if you want interoperability with some of the other geometric libraries, you'll have to deal with their interfaces as well.) Looking forward to seeing your work. Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com