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
[email protected]
http://postgis.refractions.net/mailman/listinfo/postgis-users
--
Paul Ramsey
Refractions Research
http://www.refractions.net
[EMAIL PROTECTED]
Phone: 250-383-3022
Cell: 250-885-0632
_______________________________________________
postgis-users mailing list
[email protected]
http://postgis.refractions.net/mailman/listinfo/postgis-users
