Opened 16 years ago

# Improved algorithm for ST_DWithin (also proposed ST_DFullyWithin ?)

Reported by: robe medium postgis

## 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.

### comment:1 by robe, 16 years ago

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

### comment:2 by pramsey, 16 years ago

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

### comment:3 by mtnclimb, 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 pramsey, 16 years ago

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

### comment:5 by nicklas, 15 years ago

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

Note: See TracTickets for help on using tickets.