Revisions to In 2D, how do I efficiently find the nearest object to a point?

continuity does not imply monotonicity

edit approved Nov 8, 2012 at 15:14

4k
1
20
29

sqrt()sqrt() is continuousmonotonic, meaningor order-preserving, for non-negative arguments so:

if sqrt(x) < sqrt(y) theniff x < y

andAnd vice versa.

So if you only want to compare two distances but are not interested in their actual values you can just cut out the sqrtsqrt()-step from your pythagorasPythagoras-stuff:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)² pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)² if (pseudoDistanceB < pseudoDistanceC) { A is closest to B! } else { A is closest to C! }

It's not as efficient as the oct-tree thing, but it's easier to implement and does bump up the speed at least a little bit

sqrt() is continuous, meaning

if sqrt(x) < sqrt(y) then x < y

and vice versa

So if you only want to compare two distances but are not interested in their actual values you can just cut out the sqrt-step from your pythagoras-stuff:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)² pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)² if (pseudoDistanceB < pseudoDistanceC) { A is closest to B! } else { A is closest to C! }

It's not as efficient as the oct-tree thing, but it's easier to implement and does bump up the speed at least a little bit

sqrt() is monotonic, or order-preserving, for non-negative arguments so:

sqrt(x) < sqrt(y) iff x < y

And vice versa.

So if you only want to compare two distances but are not interested in their actual values you can just cut out the sqrt()-step from your Pythagoras-stuff:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)² pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)² if (pseudoDistanceB < pseudoDistanceC) { A is closest to B! } else { A is closest to C! }

It's not as efficient as the oct-tree thing, but it's easier to implement and does bump up the speed at least a little bit

added 20 characters in body

Source Link

edited Jul 8, 2011 at 17:12

HumanCatfood

934
6
12

sqrt() is continuous, meaning

if sqrt(x) < sqrt(y) then x < y

and vice versa

So if you only want to compare two distances but are not interested in their actual values you can just cut out the sqrt-step from your pythagoras-stuff:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)² pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)² if (distBpseudoDistanceB < distCpseudoDistanceC) { A is closest to B! } else { A is closest to C! }

It's not as efficient as the oct-tree thing, but it's easier to implement and does bump up the speed at least a little bit

sqrt() is continuous, meaning

if sqrt(x) < sqrt(y) then x < y

and vice versa

So if you only want to compare two distances but are not interested in their actual values you can just cut out the sqrt-step from your pythagoras-stuff:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)² pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)² if (distB < distC) { A is closest to B! } else { A is closest to C! }

It's not as efficient as the oct-tree thing, but it's easier to implement and does bump up the speed at least a little bit

sqrt() is continuous, meaning

if sqrt(x) < sqrt(y) then x < y

and vice versa

So if you only want to compare two distances but are not interested in their actual values you can just cut out the sqrt-step from your pythagoras-stuff:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)² pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)² if (pseudoDistanceB < pseudoDistanceC) { A is closest to B! } else { A is closest to C! }

It's not as efficient as the oct-tree thing, but it's easier to implement and does bump up the speed at least a little bit

Source Link

answered Jul 1, 2011 at 16:28

HumanCatfood

934
6
12

sqrt() is continuous, meaning

if sqrt(x) < sqrt(y) then x < y

and vice versa

So if you only want to compare two distances but are not interested in their actual values you can just cut out the sqrt-step from your pythagoras-stuff:

pseudoDistanceB = (A.x - B.x)² + (A.y - B.y)² pseudoDistanceC = (A.x - C.x)² + (A.y - C.y)² if (distB < distC) { A is closest to B! } else { A is closest to C! }

It's not as efficient as the oct-tree thing, but it's easier to implement and does bump up the speed at least a little bit

Stack Exchange Network

Return to Answer