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

[Paul Ramsey]

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.

If your tests work OK, this could be something of more general 
applicability.

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


-- 

   Paul Ramsey
   Refractions Research
   http://www.refractions.net
   pramsey at refractions.net
   Phone: 250-383-3022
   Cell: 250-885-0632