Java find k closest points to a given 2D point, quickly

Question

I function that takes a set of points, checks their distance against a given point and returns an ordered set with the closest points first. In case 2 points have the same distance from the given point, both will be kept, no problem.

I use that function to pick the k closest points to any user-given point with 2D coordinates. It's just a matter of picking the first k points from the ordered set.

Right now it's something like this, and I guess the distance calculation is called again and again for every point that's added (not good)

import java.awt.geom.Point2D;
import java.util.Comparator;

/**
 * This comparator sorts two points by destination distance.
 */
public class NearestComparator implements Comparator<Point2D> {

    /** The point to be reached. */
    private Point2D destination;

    /**
     * Instantiates a new comparator that sorts points by destination distance, descendant.
     * 
     * @param destination the point to reach
     */
    public NearestComparator(Point2D destination) {
        this.destination = destination;
    }

    /**
     * Sort two points by destination distance, descendant.
     * 
     * @param p1 the first point
     * @param p2 the second point
     */
    @Override
    public int compare(Point2D p1, Point2D p2) {
        double p1_distance = p1.distance(destination);
        double p2_distance = p2.distance(destination);
        return (p1_distance < p2_distance) ? -1 : ((p1_distance > p2_distance) ? 1 : 0);
    }
}

The sorting code right now is like this

private List<Point2D> getSendOrder(Point2D destination) {
    LinkedList<Point2D> sendOrderList = new LinkedList<Point2D>();
    sendOrderList.add(myPosition);

    Iterator<Point2D> keyIter = neighborLinks.keySet().iterator();
    while (keyIter.hasNext()) {
        sendOrderList.add(keyIter.next());
    }

    // sort list by distance from destination
    Collections.sort(sendOrderList, new NearestComparator(destination));
    return sendOrderList;
}

Is there a data structure in the standard library that allows me to add an element with a fixed "priority" that is unrelated to its own class? I mean, something like (priority 1, Object ref x), (priority 2, Object ref y), (priority 1, Object ref z) etc.

I need this to be as fast as possible, and to generate as little garbage as possible. It's for a routing algorithm in a graph. There is no need for fast access to the middle of the ordered set, just the top (lowest distance, highest priority). It's important however to be able to remove the top priority element in an efficient way.

As you can see, as long as I get a list ordered in the right way (first element has higher priority, etc.), I have no need to preserve the priority information in the returned result.

Answer 1

I've had the idea to wrap the distance using Map.Entry, then this also allows deep copy, if you want it.

Here's a complete example

package sandbox;

import java.awt.geom.Point2D;
import java.util.AbstractMap.SimpleEntry;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;

public class Node {

    private Point2D myPosition;
    private Map<Point2D, Node> neighborLinks;

    public class NearestComparator implements Comparator<Entry> {

        @Override
        public int compare(Entry e1, Entry e2) {
            return Double.compare((Double) e1.getValue(), (Double) e2.getValue());
        }
    }

    public List<Point2D> getSendOrder(Point2D destination) {
        LinkedList<Entry> sendOrderList = new LinkedList<>();
        Entry<Point2D, Double> pointWithDist;

        // calculate distance from destination and wrap it using an Entry
        pointWithDist = new SimpleEntry<>(myPosition, myPosition.distance(destination));
        sendOrderList.add(pointWithDist);
        for (Point2D otherPoint : neighborLinks.keySet()) {
            pointWithDist = new SimpleEntry<>(otherPoint, otherPoint.distance(destination));
            sendOrderList.add(pointWithDist);
        }

        // sort list by distance from destination
        Collections.sort(sendOrderList, new NearestComparator());

        // print all the list (debug)
        System.out.println(Arrays.toString(sendOrderList.toArray()));

        // unwrap and deep copy
        LinkedList<Point2D> copiedList = new LinkedList<>();
        Point2D pointToCopy, copiedPoint;
        for (Entry entry : sendOrderList) {
            pointToCopy = (Point2D) entry.getKey();
            copiedPoint = new Point2D.Double(pointToCopy.getX(), pointToCopy.getY());
            copiedList.add(copiedPoint);
        }

        return copiedList;
    }

    public Node(Point2D myPosition, Map<Point2D, Node> neighborLinks) {
        this.myPosition = myPosition;
        this.neighborLinks = neighborLinks;
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Map<Point2D, Node> neighborLinks = new HashMap<>();
        Random rand = new Random();
        double x, y, max = 5;
        for (int i = 0; i < 10; ++i) {
            x = rand.nextDouble() * max;
            y = rand.nextDouble() * max;
            neighborLinks.put(new Point2D.Double(x, y), null);
        }

        Point2D nodePos = new Point2D.Double();
        Node myNode = new Node(nodePos, neighborLinks);

        Point2D destination = new Point2D.Double();
        myNode.getSendOrder(destination);
    }

}