[geos-devel] [Fwd: [Boost-users] [boost] Formal Review: Boost.Polygon
starts today August 24, 2009]
mbdavis at refractions.net
Tue Sep 1 19:57:29 EDT 2009
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
I would certainly be curious to see how the algorithmic component of
GEOS compares to GGL (or any other library). 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
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?
Barend Gehrels wrote:
> Martin Davis wrote:
>> Ok, I can see that. So in other words, GEOS uses a dynamic
>> coordinate access paradigm, which gives flexibility to access
>> different data structures, but can't be optimized by the compiler?
> It is not only the compiler. Dynamic memory allocations are relatively
> slow. Allocating 1000 times a point is slower than allocating once
> 1000 points.
>> Is this the reason for the performance difference for *all* the other
>> libraries which beat it in peformance? Or maybe some of them *don't*
>> provide the dynamic data structure wrapper, and hence also can be
>> optimized by the compiler (but thus they are less adaptable for use
>> with external data structures).
> I don't know this for sure but I think most allocate for the whole
> polygon or linestring at once. GPC is e.g. C, not C++.
>> I presume it would be a big job to convert GEOS to a template-based
> Probably. What would be possible and feasable is adapting GEOS's
> datastructures (polygon) to GGL's concepts and then call e.g. GGL's
> intersection. It would at least be a nice experiment. You still have
> the dynamic memory then, but you can see which part is the algorithm
> and which part is the memory access
>> It's somewhat annoying that the problem of efficient memory access
>> and compiler optimization is quite orthogonal to the actual geometric
>> algorithms, and yet it seems difficult to express the algorithms in a
>> sufficiently abstract way to allow optimizations to take place.
> I don't see this. Using the std-library, both access to a vector and
> (temporary) storage using a vector or deque are usually quite fast.
> Regards, Barend
> geos-devel mailing list
> geos-devel at lists.osgeo.org
Senior Technical Architect
Refractions Research, Inc.
More information about the geos-devel