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.

Answer 1

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...

Answer 2

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.

Answer 3

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