Ordering a list of points nearest to a given point

Question

I am trying to order a list of points by distance from a given point.

The application is to find the nearest landmarks (gps coordinates) to your current gps coordinate.

so if you take the following code :

public static void main(String[] args) throws SQLException {
        ArrayList<Point2D.Double> points = new ArrayList<Point2D.Double>();

        Point2D.Double point1 = new Point2D.Double(1,1);
        Point2D.Double point2 = new Point2D.Double(2,2);
        Point2D.Double point3 = new Point2D.Double(3,3);

        points.add(point1);
        points.add(point2);
        points.add(point3);

        Point2D.Double myPoint = new Point2D.Double(4,4);

    }

If i use a Comparator to sort the points array I will get a nice ordered list of points but how do I find which one is closer to myPoint? and what are the distances.

That should certainly answer my question, but for bonus points.. how can I limit the result of points back if give a maximum distance. eg : return an ordered list of coordinates that are no further than 100 miles.

How do you want the distance to be calculated? Euclidian distance? Manhattan distance? And this looks more like a homework question ... — Dominik Sandjaja, Mar 27 '14 at 09:38
I have no idea to be honest. This is all new to me. and I assure you it is not homework. — Fuzz, Mar 27 '14 at 09:43

score 4 · Accepted Answer · edited May 23 '17 at 11:58

First, some minor things:

You should not declare the list as an ArrayList, but only as a List ( What does it mean to "program to an interface"? )
The same for the points: They should not be declared as Point2D.Double, but only als Point2D

Regarding the actual question: The Point2D class already has methods for (euclidean and other) distance computations. However, for a point storing geo coordinates, you might have to implement the distance function on your own.

In general, a comparator that compares by the distance to a given point can be implemented as in the following example:

import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class PointsByDistanceTest
{
    public static void main(String[] args) 
    {
        List<Point2D> points = new ArrayList<Point2D>();

        points.add(new Point2D.Double(1,1));
        points.add(new Point2D.Double(2,2));
        points.add(new Point2D.Double(3,3));
        points.add(new Point2D.Double(4,4));
        points.add(new Point2D.Double(5,5));
        points.add(new Point2D.Double(6,6));

        Point2D myPoint = new Point2D.Double(4,4);

        Collections.sort(points, createComparator(myPoint));

        double maxDistance = 2.0;
        int index = 0;
        for (Point2D p : points)
        {
            if (p.distanceSq(myPoint) > maxDistance * maxDistance)
            {
                break;
            }
            index++;
        }
        List<Point2D> result = points.subList(0, index);
        System.out.println(
            "The closest points with distance <="+maxDistance+" are "+result);
    }

    private static Comparator<Point2D> createComparator(Point2D p)
    {
        final Point2D finalP = new Point2D.Double(p.getX(), p.getY());
        return new Comparator<Point2D>()
        {
            @Override
            public int compare(Point2D p0, Point2D p1)
            {
                double ds0 = p0.distanceSq(finalP);
                double ds1 = p1.distanceSq(finalP);
                return Double.compare(ds0, ds1);
            }

        };
    }

}

The question about limiting the number of points has also been targeted in this sample: It will ony return the points that have a distance that is not greater than maxDistance. However, you'll still sort the whole list of points. If you want to avoid sorting the whole list, then this turns into a "K Nearest neighbors" problem ( http://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm ) where you can employ some really sophisticated data structures...

Thank you very much for your answer, and your best practice tips. I did not want to limit the number of results back, I wanted to limit the results back according to maximum distance. — Fuzz, Mar 27 '14 at 09:50
@Fuzz Sorry, I misunderstood that second part. I edited the answer with a very "pragmatic" solution: One can simply walk through the list, and see when the maximum distance is exceeded. But agin: When you have "many" points (100000 or so), and only want to look for "few" points (10 or so) that have a small distance to the referernce point, then you should use a dedicated K-Nearest-Neighbor search data structure, because the approach sketched in the answer will then be comparably inefficient. — Marco13, Mar 27 '14 at 10:43

RMachnik · Answer 2 · 2014-03-27T09:59:38.600

1

Simple math check it.

     int dist = Math.sqrt(Math.pow(b1.x - b2.x,2) - Math.pow(b1.y-b2.y,2))

Edit: added dot in b2x

edited Mar 27 '14 at 09:59

answered Mar 27 '14 at 09:40

RMachnik

3,598
1
34
51

So I could essentially, map all the distances and then sort by distance? then limit the results on the max distance I want. – Fuzz Mar 27 '14 at 09:42
1

pow requires 2 arguments, I think that your function should be: int dist = Math.sqrt(Math.pow(b1.x - b2.x,2) - Math.pow(b1.y-b2.y, 2)) – Guillermo Merino Mar 27 '14 at 09:55
1

Three hints: **1**.: The euclidean distance is already available as a method in the `Point2D` class. **2**.: In order to compare points by their euclidean distance, you can use the *squared* distance (and save the `sqrt` computation). And **3**.: Computing x² as `pow(x,2)` is horribly inefficient. You should use `x*x` instead. – Marco13 Mar 27 '14 at 10:49
Yes your comment maybe is good but I made my point with showing some example of answer. – RMachnik Mar 27 '14 at 11:30

score 1 · Answer 3 · answered Mar 27 '14 at 09:46

Have you considered using this algorithm - Planar divide and conquer?

* Sort points according to their x-coordinates.
* Split the set of points into two equal-sized subsets by a vertical line x=xmid.
* Solve the problem recursively in the left and right subsets. This yields the 
  left-side and right-side minimum distances dLmin and dRmin, respectively.
* Find the minimal distance dLRmin among the pair of points in which one
  point lies on the left of the dividing vertical and the second point lies 
  to the right.
* The final answer is the minimum among dLmin, dRmin, and dLRmin.

Also you mention using GPS coordinates, if those are stored as latitude/longitude, perhaps you should use Haversine formula to calculate distances.

Haversine isn't really needed for smaller distances; a square root of sum of powers suffices. The issue is that longitude isn't linear and so must be multiplied by cos(latitude) before you multiply by deg-to-meter constans (111244m per degree). — Michał Leon, May 24 '17 at 16:30

score 0 · Answer 4 · answered Mar 27 '14 at 09:43

If you have the ordered list you can then look for the closest point by writing two lists where one is for X-coordinates and one for Y-coordinates. Then check the position of the points in list and the one with the lowest indexes is the closest point.

Just a suggestion.

score 0 · Answer 5 · answered Mar 27 '14 at 09:50

public class DistanceComparator implements Comparator<Point2D.Double>{

Point2D.Double refPoint;

public DistanceComparator(Double refPoint) {
    super();
    this.refPoint = refPoint;
}


@Override
public int compare(Double o1, Double o2) {
    return (refPoint.distance(o1)<refPoint.distance(o2)?-1:1);
}

}

Guillermo Merino · Answer 6 · 2014-03-27T10:55:37.810

This should do the work:

public static void main(final String[] args) {
        ArrayList<Point2D.Double> points = new ArrayList<Point2D.Double>();

        Point2D.Double point1 = new Point2D.Double(1, 1);
        Point2D.Double point2 = new Point2D.Double(2, 2);
        Point2D.Double point3 = new Point2D.Double(3, 3);

        points.add(point1);
        points.add(point2);
        points.add(point3);

        final Point2D.Double myPoint = new Point2D.Double(4, 4);

        Collections.sort(points, new Comparator<Point2D.Double>() {

            @Override
            public int compare(final Double o1, final Double o2) {
                double dist1 = Math.sqrt(Math.pow(o1.x - myPoint.x, 2) - Math.pow(o1.y - myPoint.y, 2));
                double dist2 = Math.sqrt(Math.pow(o2.x - myPoint.x, 2) - Math.pow(o2.y - myPoint.y, 2 ));
                return Double.compare(dist1,dist2);
            }
        });
    }

See the comment that I added in http://stackoverflow.com/a/22683547/ . In your case, additionally, the computation of the result in the comparator is flawed: When the distances are `0.3` and `0.1`, then the comparator will return `0` due to the cast to `int`. You should `return Double.compare(dist1, dist2)` instead. — Marco13, Mar 27 '14 at 10:53
You're right, thanks, I've edited the answer with your correction — Guillermo Merino, Mar 27 '14 at 10:56

Ordering a list of points nearest to a given point

6 Answers6