Java快速找到距离给定二维点最近的k个点

Question

I 函数接受一组点，检查它们与给定点的距离，并首先返回最近点的有序集。如果两个点到给定点的距离相同，则两个点都会被保留，没有问题。

我使用该函数来选择距离任何用户给定的具有 2D 坐标的点最近的 k 个点。只需从有序集中选取前 k 个点即可。

现在是这样的，我猜对于每个添加的点都会一次又一次地调用距离计算(不好)

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

现在的排序代码是这样的

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

标准库中是否有一个数据结构允许我添加一个具有与其自己的类无关的固定“优先级”的元素？我的意思是，类似 (priority 1, Object ref x) , (priority 2, Object ref y) , (priority 1, Object ref z)等等

我需要它尽可能快，并产生尽可能少的垃圾。它用于图中的路由算法。不需要快速访问有序集的中间，只需访问顶部(距离最小，优先级最高)。然而，能够以有效的方式删除最优先的元素非常重要。

如您所见，只要我得到一个以正确方式排序的列表(第一个元素具有更高的优先级等)，我就不需要在返回的结果中保留优先级信息。

Answer 1

我有想法使用 Map.Entry 来包装距离，那么如果您需要的话，这也允许深度复制。

这是一个完整的示例

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

}