Opened 14 years ago

Last modified 12 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:


Implement better short-circuiting algorithm for ST_DWithin ST_DWithin is currently implemented as

SELECT $1 &amp;&amp; ST_Expand($2,$3) AND $2 &amp;&amp; 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 &amp;&amp; ST_Expand($2,$3) AND $2 &amp;&amp; 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 &amp;&amp; ST_Expand($2,$3) AND $2 &amp;&amp; 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 Changed 14 years ago by robe

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

comment:2 Changed 14 years ago by pramsey

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

comment:3 Changed 14 years ago by 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.

comment:4 Changed 14 years ago by pramsey

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

comment:5 Changed 12 years ago by nicklas

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

Note: See TracTickets for help on using tickets.