Re: [boost] Computational Geometry Library

From: Arash Partow (arash_at_[hidden])
Date: 2006-07-30 08:01:17

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