Boost logo

Boost :

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:

and other:

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 (

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

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:
and WKB:

I have some prototype of Spirit based parser to read WKT.

Best regards

Mateusz Loskot

Boost list run by bdawes at, gregod at, cpdaniel at, john at