[postgis-devel] Ordering of geometries in multipolygons, prepared geometries

[Martin Davis]

CascasedUnion in JTS works great - for independent feedback see this post:

http://lists.jump-project.org/pipermail/jts-devel/2008-July/002587.html

Unfortunately this code hasn't been ported to GEOS yet.

In the meantime, the "order-by-x" technique will help.



Kevin Neufeld wrote:
> Yes, specifying a custom ordering for collect often makes a huge 
> difference when performing certain operations, but PostGIS does not do 
> anything special internally with the ordering of a collection ... yet.
>
> I recall back in Nov.2007 that Lee Keel was trying to union ~33000 
> polygons together that was taking over 5 hours to compute.  (See the 
> "geomunion revisited..." thread in postgis-users).
>
> Using a technique called cascaded union, Martin Davis and I were able 
> to drop the computation to half a minute by simply ordering the 
> geometries so that they were spatially close to eachother and then 
> unioning small collections at a time. 
> (http://postgis.refractions.net/pipermail/postgis-users/2007-November/017696.html) 
>
>
> Martin, what's the status of your CascadedUnion class in JTS?  Do you 
> know if it ever made its way into GEOS yet?
>
> Cheers,
> -- Kevin
>
>
> Obe, Regina wrote:
>> Do PostGIS functions take advantage of the internal ordering of
>> geometries in a Multi geometry?
>>
>> The reason I ask is that since ST_Collect just collects geometries in
>> the order they are fed in, I'm wandering if its better to advice to
>> first order the geometries before collecting.
>>
>> Something along the line of
>> SELECT stusps,        ST_Collect(f.the_geom) as singlegeom       FROM 
>> (SELECT stusps, (ST_Dump(the_geom)).geom As the_geom                 
>> FROM
>>                 somestatetable
>>             ORDER BY stusps, somestatetable.the_geom ) As f
>> GROUP BY stusps
>>
>> or maybe it doesn't make a difference.
>>
>> Also I've noticed when using ST_Union if I order the geometries first
>> before passing them to ST_Union, it is anywhere from 20-30% faster.  On
>> some occasions though - its actually slower by about 10% (even when my
>> ordering doesn't add any significant time).  I'm still trying to figure
>> this out.
>>
>> Case in point - runs in 359-360 ms
>> SELECT ST_Union(the_geom)
>> from (SELECT * from neighborhoods ORDER BY the_geom)  as foo
>>
>> Vs - runs between 530 - 550 ms
>> SELECT ST_Union(the_geom)
>> from (SELECT * from neighborhoods ) as foo
>>
>> This is all running on - "POSTGIS="1.3.3" GEOS="3.0.0-CAPI-1.4.1"
>> PROJ="Rel. 4.6.0, 21 Dec 2007" USE_STATS"
>>
>> Thanks,> Regina
>>
>>
>> -----------------------------------------
>> 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.
>>
>> _______________________________________________
>> postgis-devel mailing list
>> postgis-devel at postgis.refractions.net
>> http://postgis.refractions.net/mailman/listinfo/postgis-devel
> _______________________________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022