[postgis-users] Question on how to optimize linestring to points distance query

[Carl Anderson]

Paul Ramsey wrote:
>
> Perhaps you could try some experiments for us :)
>
> Write a PL/PgSQL function that takes in a linestring and returns a 
> tupleset of two (or four or eight) bounding boxes, that taken together 
> cover the linestring.  By recursively dividing the master box into 
> smaller boxes that still cover the line, you should be able to get 
> bigger index selectivity.

Paul are you suggesting that a geometry can have more than one GIST 
node?  As I read them GIST compress and decompress as tied directly to a 
single tuple having a geometry.

Maybe there could be a concept of a multi-bbox  upon which some some 
index selectivity could be built?

A geometry's bounding box is broken into a grid and each element to 
tested if it truly contains a part of the original geometry.
Optimizations may exist.

That would be way more expensive to index but might massively improve 
query speeds for complex objects.  It would increase index storage size 
a good deal as a downside.
It would be a super elegant way to speed index queries for complex 
entities and have little impact on simple objects.
It would increase index storage size a good deal as a small downside.  
(The entire index works best when it all fits into memory, that is a 
server tuning issue.)

Can a single geometry datatype have alternate GIST index forms?  My 
guess is no.  If so no half way rollout testing.

C.


>
> If your tests work OK, this could be something of more general 
> applicability.
>
I get 1 30x improvement in speed breaking Polygons having more than 500 
vertices into 1/100th chunks.
Of course SQL environments are designed to wade through tons of 
features.  So a 1 - > 100 expansion is no real problem.

I have attached the plpgsql function to do the splitting.  I is tuned 
around some GEOS issues I run into.


> P
>
> Stephen Woodbridge wrote:
>> Hi all,
>>
>> I have a linestring and a large number of points in a table. I want 
>> to find all the points with distance X of the linestring. This is a 
>> pretty straight forward query like:
>>
>> $LINE = "GeomFromText('LINESTRING(...)',4326)"
>> $X    = <number in meters>
>>
>> select distance_sphere($LINE, the_geom) as distance, *
>>   from mypoints
>>  where
>>    expand($LINE, metersToDegrees($X)) && the_geom and
>>    distance_sphere($LINE, the_geom) < $X
>>  order by distance;
>>
>> Discussion:
>>
>> Since the && operator only compares bbox it does not really matter if 
>> you expand one or the other arguments, and you should expand 
>> whichever has the fewest items for speed.
>>
>> In the case of a linestring that might be diagonal across your 
>> extents of the_geom, you are likely to select all the points. It 
>> seems like there should be an optimization or another operator, that 
>> would allow you to expand the points and test their bbox against the 
>> linestring. This could be done very quickly with the first stage of 
>> an Cohen-Sutherland line clipping algorithm or the even faster 
>> Liang-Barsky Line Clipping algorithm or the Nicholl-Lee-Nicholl (NLN) 
>> line clipping algorithm. These have a quick rejection algorithm 
>> between a bbox and a line segment that might be crossing it.
>>
>> Doing something like this might be more expensive then the && 
>> operator but might be much faster overall.
>>
>> Questions:
>>
>> Is anything like this being done?
>> Is there a way to compare a linestring to a large number of bbox 
>> quickly?
>> Is there a better way to do this than the sql above?
>>
>> Thanks,
>>   -Steve
>> _______________________________________________
>> postgis-users mailing list
>> postgis-users at postgis.refractions.net
>> http://postgis.refractions.net/mailman/listinfo/postgis-users
>
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: chopintogrid.sql
Type: text/x-sql
Size: 2589 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20070709/a3956b45/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: grid_example.sql
Type: text/x-sql
Size: 327 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20070709/a3956b45/attachment-0001.bin>