How to sort a collection of points so that they set up one after another?
Here is a possible solution for you: our goal is to construct a path that visits each of points in your list exactly once before it loops back. We can construct paths recursively: we can pick any point from the original list as our starting point and make a trivial path that consists only of a single node. Then we can extend an already constructed path by appending a point that we haven't visited yet.
Then we assume that we can find a good order for the original list of points by making sure by choosing the path that has the smallest length. Here, by length I don't mean number of points in the path, but the total sum of the Euclidian distance between each pair of adjacent points on the path.
The only problem is: given such a path, which point should we append next? In theory, we'd have to try out all possibilities to see which one leads to the best overall path.
The main trick that the code below employs is that it uses the following heuristic: in each step where we have to append a new point to the path constructed so far, pick the point that minimizes the average distance between two adjacent points.
It should be noted that it would be a bad idea to include in this the "loop distance" between the last point on the path and the first point: as we keep adding points, we move away from the first path point more and more. If we included the distance between the two end points, this would severely affect the average distance between all adjacent pairs, and thus hurt our heuristic.
Here's a simple auxiliary class to implement the path construction outlined above:
/**
* Simple recursive path definition: a path consists
* of a (possibly empty) prefix and a head point.
*/
class Path {
private Path prefix;
private Point head;
private int size;
private double length;
public Path(Path prefix, Point head) {
this.prefix = prefix;
this.head = head;
if (prefix == null) {
size = 1;
length = 0.0;
} else {
size = prefix.size + 1;
// compute distance from head of prefix to this new head
int distx = head.x - prefix.head.x;
int disty = head.y - prefix.head.y;
double headLength = Math.sqrt(distx * distx + disty * disty);
length = prefix.length + headLength;
}
}
}
And here's the actual heuristic search algorithm.
/**
* Implements a search heuristic to determine a sort
* order for the given <code>points</code>.
*/
public List<Point> sort(List<Point> points) {
int len = points.size();
// compares the average edge length of two paths
Comparator<Path> pathComparator = new Comparator<Path>() {
public int compare(Path p1, Path p2) {
return Double.compare(p1.length / p1.size, p2.length / p2.size);
}
};
// we use a priority queue to implement the heuristic
// of preferring the path with the smallest average
// distance between its member points
PriorityQueue<Path> pq = new PriorityQueue<Path>(len, pathComparator);
pq.offer(new Path(null, points.get(0)));
List<Point> ret = new ArrayList<Point>(len);
while (!pq.isEmpty()) {
Path path = pq.poll();
if (path.size == len) {
// result found, turn path into list
while (path != null) {
ret.add(0, path.head);
path = path.prefix;
}
break;
}
loop:
for (Point newHead : points) {
// only consider points as new heads that
// haven't been processed yet
for (Path check = path; check != null; check = check.prefix) {
if (newHead == check.head) {
continue loop;
}
}
// create new candidate path
pq.offer(new Path(path, newHead));
}
}
return ret;
}
If you run this code on the sample points of your question, and then connect each adjacent pair of points from the returned list, you get the following picture:
This is not a Sort algorithm - it is more of a rearrangement to minimise a metric (the distance between consecutive points).
I'd attempt some kind of heuristic algorithm - something like:
- Pick three consecutive points a, b, c.
- If distance(a,c) < distance(a,b) then swap(a,b).
- Repeat from 1.
It should be possible to calculate how many times you should need to cycle this to achieve a minimal arrangement or perhaps you could detect a minimal arrangement by finding no swaps during a run.
You may need to alternate the direction of your sweeps rather like the classic optimisation of bubble-sort.
Added
Experiment shows that this algorithm doesn't work but I've found one that does. Essentially, for each entry in the list find the closest other point and move it up to the next location.
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);
}
}
}
prints:
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)]
which looks like what you are looking for.
The efficiency of the algorithm is not good - somewhere around O(n log n) - I hope you don't need to do this millions of times.
If you want the points to appear in a predictable order (say leftmost one at the start) you could add a fake point at the start of the list before rebuilding it and remove it after. The algorithm will always leave the first point alone.
My thinking is that you first need a mathematical definition of your ordering. I suggest (Note, this definition wasn't clear in the original question, left here for completeness):
Starting with placing any point in the sequence, then perpetually append to the sequence the point closest to the current point and that hasn't already been appended to the sequence, until all points are appended to the sequence.
Thus with this definition of the ordering, you can derive a simple algorithm for this
ArrayList<point> orderedList = new ArrayList<point>();
orderedList.add(myList.remove(0)); //Arbitrary starting point
while (myList.size() > 0) {
//Find the index of the closest point (using another method)
int nearestIndex=findNearestIndex(orderedList.get(orderedList.size()-1), myList);
//Remove from the unorderedList and add to the ordered one
orderedList.add(myList.remove(nearestIndex));
}
The above is pretty universal (regardless of the algorithm for finding the next point). Then the "findNearestIndex" method could be defined as:
//Note this is intentially a simple algorithm, many faster options are out there
int findNearestIndex (point thisPoint, ArrayList listToSearch) {
double nearestDistSquared=Double.POSITIVE_INFINITY;
int nearestIndex;
for (int i=0; i< listToSearch.size(); i++) {
point point2=listToSearch.get(i);
distsq = (thisPoint.x - point2.x)*(thisPoint.x - point2.x)
+ (thisPoint.y - point2.y)*(thisPoint.y - point2.y);
if(distsq < nearestDistSquared) {
nearestDistSquared = distsq;
nearestIndex=i;
}
}
return nearestIndex;
}
Update: Since the question was revised to largely adopt the definition I used, I took out some of the caveats.