Re: [boost] Computational Geometry Library

From: Mateusz Loskot (mateusz_at_[hidden])
Date: 2006-07-31 08:25:05

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