CODEWITHSUNDEEP
javamathcoordinatesdistance
Conner Ruhl
Conner Ruhl

Reputation: 1723

Find nearest point relative to an object without using the distance formula in Java

If I have an object with properties of x an y, how can I tell which point in an array is the closest without using the distance formula?

Upvotes: 1

Views: 1616

Answers (3)

Piotr99
Piotr99

Reputation: 531

If you have to find exactly the closest neighbour, there is no way around evaluating the distance formula, at least for a couple of points. As already pointed out, you can avoid evaluating the expensive sqrt for most of the time when simply comparing the distance-squared r^2 = x^2 + y^2.

However, if you have a big number of points spread out over a large range of distances, you can first use an approximation like the ones shown here http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml . Then you can calculate the real distance formula only for the points closest as given by the approximation. On architectures where also the multiplication is expensive, this can make a big difference. On modern x86/x86-64 architectures this should not matter much though.

Upvotes: 0

Adrian
Adrian

Reputation: 5681

If you don't care about the exact distance, you could perhaps take the difference between the x and y coordinates of your source and destination points to provide you with some ordering.

//The following code does not return the closest point, 
//but it somewhat does what you need and complies with 
//your requirement to not use the distance formula
//it finds the sum of x and y displacements

Point destination=...  
Point nearestPoint= points.get(0);
for (Point p : points){
    closenessCoefficient= Math.abs(destination.x-p.x) + Math.abs(a.destination-p.y);
    nearestPoint=Math.Min(closenessCoefficient, nearestPoint);
}
return nearestPoint;

Upvotes: 1

Ignacio Vazquez-Abrams
Ignacio Vazquez-Abrams

Reputation: 799240

You can't get an accurate result without using some variant of the distance formula. But you can save a few cycles by not taking the square root after the fact; the comparison will remain valid.

r = dx2 + dy2

Upvotes: 3

Related Questions