Это не алгоритм Sort — это скорее перестановка для минимизации метрики (расстояния между последовательными точками).
Я бы попробовал какой-то эвристический алгоритм - что-то вроде:
- Выберите три последовательные точки a, b, c.
- Если расстояние (a, c) ‹ расстояние (a, b), то поменять местами (a, b).
- Повторить с 1.
Должна быть возможность рассчитать, сколько раз вам нужно будет выполнить цикл, чтобы достичь минимального расположения, или, возможно, вы могли бы определить минимальное расположение, не обнаружив никаких свопов во время прогона.
Возможно, вам придется изменить направление ваших движений, как при классической оптимизации пузырьковой сортировки.
Добавлено
Эксперимент показывает, что этот алгоритм не работает, но я нашел такой, который работает. По сути, для каждой записи в списке найдите ближайшую другую точку и переместите ее в следующее место.
private static class Point {
final int x;
final int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public String toString() {
return "(" + x + "," + y + ")";
}
public double distance(Point b) {
int dx = x - b.x;
int dy = y - b.y;
// Simple cartesian distance.
return Math.sqrt(dx * dx + dy * dy);
}
}
// Sample test data - forms a square.
Point[] points = new Point[]{
new Point(0, 0),
new Point(0, 1),
new Point(0, 2),
new Point(0, 3),
new Point(0, 4),
new Point(0, 5),
new Point(0, 6),
new Point(0, 7),
new Point(0, 8),
new Point(0, 9),
new Point(1, 9),
new Point(2, 9),
new Point(3, 9),
new Point(4, 9),
new Point(5, 9),
new Point(6, 9),
new Point(7, 9),
new Point(8, 9),
new Point(9, 9),
new Point(9, 8),
new Point(9, 7),
new Point(9, 6),
new Point(9, 5),
new Point(9, 4),
new Point(9, 3),
new Point(9, 2),
new Point(9, 1),
new Point(9, 0),
new Point(8, 0),
new Point(7, 0),
new Point(6, 0),
new Point(5, 0),
new Point(4, 0),
new Point(3, 0),
new Point(2, 0),
new Point(1, 0),};
public void test() {
System.out.println("Hello");
List<Point> test = Arrays.asList(Arrays.copyOf(points, points.length));
System.out.println("Before: " + test);
Collections.shuffle(test);
System.out.println("Shuffled: " + test);
List<Point> rebuild = new ArrayList<>(test);
rebuild.add(0, new Point(0, 0));
rebuild(rebuild);
rebuild.remove(0);
System.out.println("Rebuilt: " + rebuild);
}
private void rebuild(List<Point> l) {
for (int i = 0; i < l.size() - 1; i++) {
Point a = l.get(i);
// Find the closest.
int closest = i;
double howClose = Double.MAX_VALUE;
for (int j = i + 1; j < l.size(); j++) {
double howFar = a.distance(l.get(j));
if (howFar < howClose) {
closest = j;
howClose = howFar;
}
}
if (closest != i + 1) {
// Swap it in.
Collections.swap(l, i + 1, closest);
}
}
}
печатает:
Before: [(0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7), (0,8), (0,9), (1,9), (2,9), (3,9), (4,9), (5,9), (6,9), (7,9), (8,9), (9,9), (9,8), (9,7), (9,6), (9,5), (9,4), (9,3), (9,2), (9,1), (9,0), (8,0), (7,0), (6,0), (5,0), (4,0), (3,0), (2,0), (1,0)]
Shuffled: [(9,6), (0,9), (0,8), (3,9), (0,5), (9,4), (0,7), (1,0), (5,0), (9,3), (0,1), (3,0), (1,9), (8,9), (9,8), (2,0), (2,9), (9,5), (5,9), (9,7), (6,0), (0,3), (0,2), (9,1), (9,2), (4,0), (4,9), (7,9), (7,0), (8,0), (6,9), (0,6), (0,4), (9,0), (0,0), (9,9)]
Rebuilt: [(0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7), (0,8), (0,9), (1,9), (2,9), (3,9), (4,9), (5,9), (6,9), (7,9), (8,9), (9,9), (9,8), (9,7), (9,6), (9,5), (9,4), (9,3), (9,2), (9,1), (9,0), (8,0), (7,0), (6,0), (5,0), (4,0), (3,0), (2,0), (1,0)]
который выглядит как то, что вы ищете.
Эффективность алгоритма не очень хорошая - где-то около O(n log n) - надеюсь, вам не нужно делать это миллионы раз.
Если вы хотите, чтобы точки отображались в предсказуемом порядке (скажем, самая левая в начале), вы можете добавить поддельную точку в начало списка перед его перестройкой и удалить ее после. Алгоритм всегда будет оставлять первую точку в покое.
13.08.2014
