Ordering a list of points nearest to a given point

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

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

Question 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

Question 4

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.

Question 5

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);
}

}

Question 6

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);
            }
        });
    }