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

[Obe, Regina]

Paul,

I was thinking along those lines too.  Would seem to be the best place
to call it would be a 

a wrapper around  FINALFUNC=unite_garray

So instead of calling the unite_garray function directly - we would call
an intermediary function that does a GeoHash first and then sends it off
to unite_garray.

Then you don't have to rely on the user remembering to order by the
geometry.

Thanks,
Regina



-----Original Message-----
From: postgis-devel-bounces at postgis.refractions.net
[mailto:postgis-devel-bounces at postgis.refractions.net] On Behalf Of Paul
Ramsey
Sent: Tuesday, August 05, 2008 3:43 PM
To: PostGIS Development Discussion
Subject: Re: [postgis-devel] Ordering of geometries in
multipolygons,prepared geometries

Perhaps it is time to add a geohash generation function to PostGIS,
for these kinds of problems. (Also to simply back ST_Union() into a
cascaded implementation :). But an order by ST_GeoHash(geom) should
provide a pretty optimal input to the standard union function.

This is something that could even be done in plpgsql, I bet. Take the
centroid of the geometry and apply an interleave to the coordinates.

P.

On Tue, Aug 5, 2008 at 11:58 AM, Martin Davis <mbdavis at refractions.net>
wrote:
> 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/01
7696.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
>
> _______________________________________________
> 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
-----------------------------------------
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.