Java可以快速找到k个给定2D点的最近点 [英] Java find k closest points to a given 2D point, quickly
问题描述
我使用该函数来选择最接近任何用户的k点，给定点与2D坐标。这只是从有序集中挑选第一个k点的问题。
现在是这样的，我想，每次都会一次又一次地调用距离计算点添加（不好）
import java.awt.geom.Point2D;
import java.util.Comparator
/ **
*此比较器按目的地距离排序两点。
* /
public class NearestComparator实现比较器< Point2D> {
/ **要达到的要点。 * /
私人Point2D目的地;
/ **
*实例化一个新的比较器，按目的地距离，后代排序点。
*
* @param目的地达到
* /
public NearestComparator（Point2D destination）{
this.destination = destination;
}
/ **
*按目的地距离，后代排序两点。
*
* @param p1第一个点
* @param p2第二个点
* /
@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）;
}
}
现在的排序代码就像这样
私人列表< Point2D> getSendOrder（Point2D destination）{
LinkedList< Point2D> sendOrderList = new LinkedList< Point2D>（）;
sendOrderList.add（myPosition）;
迭代器< Point2D> keyIter = neighborLinks.keySet（）。iterator（）;
while（keyIter.hasNext（））{
sendOrderList.add（keyIter.next（））;
}
//按目的地距离排序列表
Collections.sort（sendOrderList，new NearestComparator（destination））;
return sendOrderList;
}
标准库中是否有数据结构，允许我添加一个元素与自己的班级无关的固定的优先我的意思是像（priority 1，Object ref x），（priority 2，Object ref y），（priority 1，Object ref z）等。
我需要这么快才能生成尽可能少的垃圾。它是图中的路由算法。没有必要快速访问有序集的中间，只是顶部（最低距离，最高优先级）。重要的是能够以有效的方式删除最高优先级的元素。
正如你所看到的，只要我得到一个以正确的方式排序的列表（第一个元素具有更高的优先级等），我不需要保留返回结果中的优先级信息。
我我们已经有了使用Map.Entry包装距离的想法，那么如果你想要的话，这也允许深层复制。
这是一个完整的例子
包沙箱;
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<>（）;
条目< Point2D，Double> pointWithDist;
//计算距离目的地的距离，并使用条目
pointWithDist = new SimpleEntry（myPosition，myPosition.distance（destination））;
sendOrderList.add（pointWithDist）;
（Point2D otherPoint：neighborLinks.keySet（））{
pointWithDist = new SimpleEntry（otherPoint，otherPoint.distance（destination））;
sendOrderList.add（pointWithDist）;
}
//按目的地距离排序列表
Collections.sort（sendOrderList，new NearestComparator（））;
//打印所有列表（调试）
System.out.println（Arrays.toString（sendOrderList.toArray（）））;
//展开和深层复制
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命令行参数
* /
public static void main（String [] args）{
Map< Point2D，Node> neighborLinks = new HashMap<>（）;
随机rand = new Random（）;
double x，y，max = 5; （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）;
}
}
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.
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);
}
}
这篇关于Java可以快速找到k个给定2D点的最近点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
