Opened 17 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 robe, 17 years ago

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

comment:2 by pramsey, 17 years ago

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

comment:3 by mtnclimb, 17 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, 17 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.