Re: [boost] Computational Geometry Library

From: Mateusz Loskot (mateusz_at_[hidden])
Date: 2006-07-24 04:15:29

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