Opened 16 years ago
Last modified 15 years ago
#20 closed enhancement (fixed)
Improved algorithm for ST_DWithin (also proposed ST_DFullyWithin ?)
Reported by: | robe | Owned by: | |
---|---|---|---|
Priority: | medium | Milestone: | |
Component: | postgis | Version: | |
Keywords: | Cc: |
Description
Implement better short-circuiting algorithm for ST_DWithin ST_DWithin is currently implemented as
SELECT $1 && ST_Expand($2,$3) AND $2 && ST_Expand($1,$3) AND ST_Distance($1, $2) < $3
—This is wasteful because we don't need to calculate the full distance to know that an object is within $3 distance of another. We only need find one point that is < $3 distance of the other.
—Proposed algorithm Change to do
SELECT $1 && ST_Expand($2,$3) AND $2 && ST_Expand($1,$3) AND _ST_DWithin($1,$2,$3)
Where _ST_DWithin($1,$2,$3) would be an lwgeom function that would return true as soon as it finds a point that is < $3 distance.
There is also some issue as to how ST_DWithin is defined as Paul Ramsey mentioned - should it mean an object is fully within $3 distance of another or only part of it need be. Second proposition - create a ST_DFullyWithin
SELECT $1 && ST_Expand($2,$3) AND $2 && ST_Expand($1,$3) AND _ST_DFullyWithin($1,$2,$3)
_ST_DFullyWithin will be like _ST_DWithin short-circuit and return false as soon as you find 2
points that are further away than $3.
Change History (5)
comment:1 by , 16 years ago
comment:3 by , 16 years ago
For the semantics of _ST_DWithin I vote for the first option:
_ST_DWithin = true iff some point on A and B is closer than dist.
This is the semantics used in JTS, it's the easiest to implement, and will provide the fastest performance. I also think it's the most common use case.
comment:4 by , 16 years ago
Patched as of r2796, in trunk and branches/1.3. Please try this out, poorly tested.
comment:5 by , 15 years ago
Just for the record of this ticket.
In PostGIS 1.5 also ST_DFullyWithin is implemented.
Oops I meant to mark this as an enhancement rather than a defect.