[geos-devel] [Fwd: [Boost-users] [boost] Formal Review: Boost.Polygon starts today August 24, 2009]

[Barend Gehrels]

Martin Davis wrote:
> One thing to make clear - GEOS does not alway require allocations to 
> be done pointwise.  The CoordinateSequence interface and various 
> subclasses provide the option of allocating all storage for a list of 
> points in a single allocation.
OK, sorry for my misunderstanding.

I just debugged the Geos area routine, what could then be the reason 
that it is relatively slow? It might be that it is accessed as a vector, 
indeed, but not as an iterator, so getting points using "return 
(*vect)[pos]" is not efficient as it could be using iterators. Besides 
that it is probably no problem to make the getAt function inline.


>
> I would certainly be curious to see how the algorithmic component of 
> GEOS compares to GGL (or any other library). 

The GGL overlay algorithm will be described in a paper. It is a modern 
variant of the classic Weiler-Atherton algorithm.

> The JTS/GEOS predicate and overlay algorithms were developed with the 
> primary goal being first generality and then performance.  So no doubt 
> there's better ways of doing things.
Actually the GGL algorithm is generic as well, in the sense that it is 
able to overlay polygons and polygon/rectangle (clipping) with the same 
algorithm. The only difference is getting the intersections, which is 
more efficient for the rectangle case. Also intersection/union are 
implemented in one algorithm.

> In the GEOS algorithms at least I don't see any way of avoiding 
> dynamic allocation, since there's no way to predict a priori how many 
> line segment intersections will be found, or how what the structure of 
> the output geometry is.  Does GGL avoid this problem in some way?
Yes. It will be described, but in short: we don't insert the found 
intersection points into the polygons (as done in many algorithms, but I 
don't know about GEOS) but register them separately. That saves a copy, 
plus many inserts (shifts). However, it requires somewhat more 
bookkeeping. So intersected polygons are assembled in the end, in 
between there are no large pieces of memory allocation.


By the way, everyone is of course invited to check the geos comparison 
source files, it might be that I've done something not in the most 
efficient way. It is the intention to have it as efficient as possible, 
of course. Sources are at boost SVN now: 
http://svn.boost.org/svn/boost/sandbox/ggl/other/comparisons/

Regards, Barend