根据彼此之间的距离对兴趣点进行排序

Question

我有一个以点对象为输入的数组。我想对这些点进行排序，得到一个覆盖所有点的最短路径的数组。到目前为止，这是我的代码，但我还没有弄清楚，一旦使用了点，如何删除它们。

public Point[] poiSort(Point[] poi){
poi = new Point[lenght+1];
poi[0] = points[0];
distances = new Double[lenght];
double Distance = verybignumber;
double Distancecompare;
for (int i = 1; i < leght+1; i++){
for (int j = 1; j < (lenght); j++){
Distancecompare = points[i-1].getDistance(points[j]);
if (Distance > Distancecompare){
Distance = Distancecompare;
poi[i] = points[j];
distances[i-1] = Disstance;
}
}
}
return poi;
}

Answer 1

您试图解决的问题显然没有意义。

或者至少。。。子问题没有。

如果有N点，则它们之间的成对距离的个数为(N-1)^2。对于每个给定点P，存在到其他点的N - 1距离。基于此，您无法为点定义相关/易于计算的排序。所以排序没有意义。

可以做的是取一点，并根据到该点的距离对其他点进行排序。但这意味着对于总共N个点，您有N个单独的订单。

请注意，您在这里试图解决的是"；旅行推销员¹问题"；(茶匙(。TSP在数学上已被证明是一个NP完全问题。这应该告诉您，尝试通过排序(即O(NlogN)(来解决它是行不通的。

我的建议是：

1. 阅读TSP及其困难原因
2. 尽量避免必须找到问题的确切解决方案
3. 看看寻找近似解的技术/算法。。。而不是试图发明自己的算法
4. 查找现有库

---

^{1-或者；旅行推销员问题"；。不，我不是在开玩笑}

Answer 2

您可以在排序期间构建一个新数组，并将其作为结果返回。这样就不需要删除元素。或者，您可以使用ArrayList或TreeSet以获得更大的灵活性。这里有一个可能不那么优雅，但可以使用数组的示例：

import java.util.Arrays;
import java.util.Comparator;
import java.util.Optional;
public class Main {

public static void main(String... args) {

Point[] points = {new Point(1,1), new Point(3,3), new Point(2,2)};
Point[] result = sort(points);
for (Point p : result) {
System.out.println("point(" + p.x + ", " + p.y + ")");
}

}

public static Point[] sort(Point[] in) {
if (in == null || in.length == 0) {
return in;
}
Point[] out = new Point[in.length];
Point current = in[0];
for (int i = 0; i < in.length; i++) {
if (i == in.length -1) {
out[in.length -1] = Arrays.stream(in).filter(p -> !p.visited).findAny().orElseGet(null);
break;
}
final Point finalCurrent = current;     // variable must be final or effectively final as used in stream
out[i] = finalCurrent;
finalCurrent.visit();
Point next = Arrays.stream(in).filter(p -> !p.visited).min(Comparator.comparingDouble(p -> p.getDistance(finalCurrent))).get();
current = next;
}
return out;
}
}

class Point {
final double x;
final double y;
boolean visited;

Point(double x, double y) {
this.x = x;
this.y = y;
}

public double getDistance(Point point) {
return Math.abs(this.x-point.x) + Math.abs(this.y - point.y);
}

public void visit() {
visited = true;
}
}