Improved algorithm for ST_DWithin (also proposed ST_DFullyWithin ?)

[robe]

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.

[robe]

Oops I meant to mark this as an enhancement rather than a defect.

[pramsey]

<i>(No comment was entered for this change.)</i>

[mtnclimb]

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.

[pramsey]

Patched as of r2796, in trunk and branches/1.3. Please try this out, poorly tested.

[nicklas]

Just for the record of this ticket.
In PostGIS 1.5 also ST_DFullyWithin is implemented.