Re: [boost] Computational Geometry Library
Mateusz Loskot wrote:
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've had a read of articles, and I like some of the ideas that have been presented and proposed. Its a shame that some of the better ideas haven't come to fruition as of yet. But heres hoping that will change sometime soon.
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/
I had a look and it seems you've made a lot of progress, it would be good to begin integrating things at some point soon for an initial review submission.
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.
I had a quick read, isn't this all just some glorified minkowski difference thing?
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.
Some geometric operations just don't make sense for certain pairs of types, hence not all geometric operations can be defined, all one can do is define/implement operations that do make sense.
* 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.
looked at it, seems like standard epsilon/fuzzy arithmetic - nothing special there. I believe one either needs to go down the path of "exact arithmetic" or to delegate the precision issues to the type the "user" chooses. From a "good library design" POV I believe that for the majority of things precision should be delegated to the users choice of type, and to hence maintain the simplicity of the calculation/algorithm's implementation. Say for example the closest point on a line from an external point is merely the dot product of the tangent from the external point and line, which is a very trivial thing. If one were to go down the path of exact arithmetic and you fall into problems such as determining the machine's FPU, its floating point precision etc... why not let the type take care of that, for most things double and float will be more than enough, for other things people may decided to use their own extended or arbitrary precision number types, such as the various rational and integer kernel types that come with CGAL, I believe the BOOST mathematics library will some day have its own extended precision real, rational and integer (bigint) types.
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.
Anything is possible, it just requires that knowledgeable people in the field be willing to chip-in. Arash Partow ________________________________________________________ Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net
Arash Partow wrote:
Mateusz Loskot wrote:
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've had a read of articles, and I like some of the ideas that have been presented and proposed. Its a shame that some of the better ideas haven't come to fruition as of yet. But heres hoping that will change sometime soon.
Arash, IMO the idea seems to be quite new, so there is more manpower needed.
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/
I had a look and it seems you've made a lot of progress, it would be good to begin integrating things at some point soon for an initial review submission.
Yes, that's my idea too.
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.
I had a quick read, isn't this all just some glorified minkowski difference thing?
Hmm, I've not analysed it from Minkowski's point of view, interesting.
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.
Some geometric operations just don't make sense for certain pairs of types, hence not all geometric operations can be defined, all one can do is define/implement operations that do make sense.
The intersection matrix operations apply to all planar geometries.
* 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.
looked at it, seems like standard epsilon/fuzzy arithmetic - nothing special there.
Yup.
I believe one either needs to go down the path of "exact arithmetic" or to delegate the precision issues to the type the "user" chooses.
The latter is seems to be a good idea.
From a "good library design" POV I believe that for the majority of things precision should be delegated to the users choice of type, and to hence maintain the simplicity of the calculation/algorithm's implementation. Say for example the closest point on a line from an external point is merely the dot product of the tangent from the external point and line, which is a very trivial thing. If one were to go down the path of exact arithmetic and you fall into problems such as determining the machine's FPU, its floating point precision etc...
That's right. We're still struggling with machine related and optimization related problems in GEOS.
why not let the type take care of that, for most things double and float will be more than enough, for other things people may decided to use their own extended or arbitrary precision number types, such as the various rational and integer kernel types that come with CGAL, I believe the BOOST mathematics library will some day have its own extended precision real, rational and integer (bigint) types.
I agree with this concept.
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.
Anything is possible, it just requires that knowledgeable people in the field be willing to chip-in.
Sure. Best regards -- Mateusz Loskot http://mateusz.loskot.net
participants (2)
-
Arash Partow -
Mateusz Loskot