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:
Also, there are some prototypes:
> 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.
> 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:
which is a *direct* port of JTS:
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
> * 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,
> 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)
> * 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:
> segment<T,D> seg1 = make_segment(....);
> segment<T,D> seg2 = make_segment(....);
> if (intersect(seg1,seg2))
How about creating segments and linestrings (string of segments)?
I imagine it could be also possible to pass range of std:: containers
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
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:
I have some prototype of Spirit based parser to read WKT.
-- Mateusz Loskot http://mateusz.loskot.net