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

[Stephen Woodbridge]

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