[postgis-devel] More work on Cascade Union

[Obe, Regina]

> Yes.  CascadedUnion really only helps if you are reducing the number of 
> points in the geometries as you union them.  With points and lines, it's 
> only in very rare situations that the number of vertices would actually 
> decrease.  (Also, with points the existing union algorithm is about as 
> performant as possible).  So you're better off simply unioning all lines 
>  together at once.

So why does GEOS perform so poorly then? I suspect the cascade algorithm I am using is gaining by the fact that it realizes fairly quickly it can just collect all the points except the rare cases where the points are duplicated then it unions.

 I'll check on unioning tiger lines to see what kind of metrics I get.  Looking at the GEOS code - I don't get a sense its doing the same thing as JTS, but I haven't really delved to see what the Overlay classes are actually doing in JTS or done more than a scant glance at the GEOS functions so I could very well be wrong in my reading.
  
> Hmm...   what exactly is the data that causes this crash?  I'd like to 
> dig into this and find out what's going on in JTS.

Simple - Create a table like this. Granted very unrealistic and then try to union all the points in JTS (well in my case OpenJump latest snapshot - reaches memory heap fault in 11 seconds) - 
1,000,000 points in one geom is hard to swallow anyway so I wasn't too concerned.

CREATE TABLE tmp_points(the_geom geometry);
INSERT INTO tmp_points
SELECT ST_MakePoint(x,y) As the_geom FROM generate_series(1,1000) x,
generate_series(1,1000) y
order by random();


> Not sure what you mean by "internally sorted geometry"?  If you talking 
> about a linear sort of the geometries (by x or possibly x,y), I don't 
> think this is going to be as good as doing a true spatial sort (which is 
> what the Rtree index in CascadedUnion does, and what Kevin's grid 
> approach does)
Doing a true spatial sort - basically order by the_geom which I assume would use the Rtree operators for sorting or at least seems to.








-----------------------------------------
The substance of this message, including any attachments, may be
confidential, legally privileged and/or exempt from disclosure
pursuant to Massachusetts law. It is intended
solely for the addressee. If you received this in error, please
contact the sender and delete the material from any computer.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-devel/attachments/20080820/ea4a9d7a/attachment.html>