[geos-devel] [Fwd: [Boost-users] [boost] Formal Review: Boost.Polygon
starts today August 24, 2009]
Barend.Gehrels at geodan.nl
Wed Sep 2 05:39:32 EDT 2009
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:
More information about the geos-devel