如何对一组点进行排序，使它们一个接一个地建立起来?

I have an ArrayList which contains coordinates of points:

我有一个包含点坐标的数组列表:

class Point
{
   int x, y;
}
ArrayList<Point> myPoints;

of such an image for example:

例如:

The problem is that these points are set chaotically in the ArrayList and I would like to sort them so that 2 points lying next to each other on the image are also one after another in the ArrayList. I can't come up with some good idea or algorithm to solve such a sorting... Are there some known methods of solving such problems?

问题是这些点在ArrayList中设置得很混乱我想对它们进行排序这样图像上相邻的两个点在ArrayList中也是一个接一个的。我想不出什么好主意或算法来解决这样的排序……是否有一些已知的方法来解决这些问题?

edit: The shape cannot cross over itself and let's assume that only shapes looking similarly like this can occur.

编辑:这个形状不能交叉，我们假设只有类似的形状才会出现。

6 个解决方案

#1

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:

上面的方法非常通用(不管查找下一个点的算法是什么)。那么“findNearestIndex”方法可以定义为:

//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.

更新:由于问题被修改为基本上采用了我使用的定义，我提出了一些注意事项。

#2

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:

如果您在您的问题的示例点上运行此代码，然后从返回的列表中连接每一对相邻的点，您将得到以下图片:

#3

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:

我会尝试一些启发式算法，比如:

1. Pick three consecutive points a, b, c.
2. 选择三个连续的点a b c。
3. If distance(a,c) < distance(a,b) then swap(a,b).
4. 如果距离(a,c) <距离(a,b)，则交换(a,b)。< li>
5. Repeat from 1.
6. 重复从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.

算法的效率不是很好——在O(n log n)附近——我希望你不需要这样做数百万次。

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.

如果您希望这些点以可预测的顺序出现(比如最左边的一个)，您可以在列表的开始添加一个假点，然后重新构建它，然后删除它。算法总是把第一点放在一边。

#4

I started this shortly after the question, but it had been delayed due to the question being put on hold. It's the simple approach that in the meantime also has been mentioned in the comments and other answers, but I'll post it here anyhow:

我在这个问题刚开始不久就开始了，但由于被搁置的问题，它被推迟了。这是一种简单的方法，同时在评论和其他答案中也提到过，但无论如何我将在这里发布它:

Here is a MCVE showing the simplest and most straightforward approach. The approach simply consists of picking an arbitrary point, and then continuing by always picking the point that is closest to the previous one. Of course, this has limitations:

这里有一个MCVE展示了最简单和最直接的方法。这种方法仅仅是选择一个任意的点，然后继续选择与前一个点最近的点。当然，这也有局限性:

• It may pick the wrong point, when there are sharp corners or cusps
• 当有尖角或尖角时，它可能会选错点。
• It's not very efficient, because it repeatedly does a search for the closest point
• 它不是很有效，因为它反复地搜索最近的点

One approach for accelerating it could be to sort the points based on the x-coordinate, and then exploit this partial ordering in order to skip most of the points when looking for the next neighbor. But as long as you don't want to apply this to ten-thousands of points in a time-critical context, this should not be an issue.

加速的一种方法是基于x坐标对点进行排序，然后利用这个部分排序，以便在查找下一个邻居时跳过大部分点。但是，只要您不希望在一个时间关键的上下文中将其应用于成千上万个点，这就不应该成为问题。

The possible ambiguities, in turn, may be a problem, but considering that, one has to say that the problem is underspecified anyhow. In some cases, not even a human could decide which point is the appropriate "next" point - at least, when the problem is not extended to detect the "interior/exterior" of shapes (this is somewhat similar to the problem of ambiguities in the marching cube algorithm: You just don't know what the intended path is).

可能的含糊不清，反过来，可能是一个问题，但考虑到这一点，人们不得不说这个问题没有得到充分的说明。在某些情况下,甚至没有人可以决定哪些点是适当的“下一个”——至少,当这个问题不是扩展检测内部/外部的形状(这有点类似于在行进的立方体算法模棱两可的问题:你不知道什么是预定的路径)。

Note that most of the code is not really important for your actual question, but ... you did not provide such a "stub" implementation. The relevant part is === marked ===

注意，大多数代码对您的实际问题并不是很重要，但是……您没有提供这样的“存根”实现。相关的部分是===标记===。

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.Shape;
import java.awt.geom.Area;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Path2D;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;

public class SortShapePoints
{
    public static void main(String[] args)
    {
        SwingUtilities.invokeLater(new Runnable()
        {
            @Override
            public void run()
            {
                createAndShowGUI();
            }
        });
    }

    private static void createAndShowGUI()
    {
        JFrame f = new JFrame();
        f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        Shape shape = createExampleShape();
        List<Point2D> points = computePoints(shape, 6);
        Collections.shuffle(points);

        List<Point2D> sortedPoints = sortPoints(points);
        Path2D path = createPath(sortedPoints, true);
        f.getContentPane().add(new ShapePanel(points, path));

        f.setSize(800, 800);
        f.setLocationRelativeTo(null);
        f.setVisible(true);
    }

    //=== Relevant part starts here =========================================

    private static List<Point2D> sortPoints(List<Point2D> points)
    {
        points = new ArrayList<Point2D>(points);
        List<Point2D> sortedPoints = new ArrayList<Point2D>();
        Point2D p = points.remove(0);
        sortedPoints.add(p);
        while (points.size() > 0)
        {
            int index = indexOfClosest(p, points);
            p = points.remove(index);
            sortedPoints.add(p);
        }

        return sortedPoints;
    }

    private static int indexOfClosest(Point2D p, List<Point2D> list)
    {
        double minDistanceSquared = Double.POSITIVE_INFINITY;
        int minDistanceIndex = -1;
        for (int i = 0; i < list.size(); i++)
        {
            Point2D other = list.get(i);
            double distanceSquared = p.distanceSq(other);
            if (distanceSquared < minDistanceSquared)
            {
                minDistanceSquared = distanceSquared;
                minDistanceIndex = i;
            }
        }
        return minDistanceIndex;
    }

    //=== Relevant part ends here ===========================================


    private static Shape createExampleShape()
    {
        Area a = new Area();
        a.add(new Area(new Ellipse2D.Double(200, 200, 200, 100)));
        a.add(new Area(new Ellipse2D.Double(260, 160, 100, 500)));
        a.add(new Area(new Ellipse2D.Double(220, 380, 180, 60)));
        a.add(new Area(new Rectangle2D.Double(180, 520, 260, 40)));
        return a;
    }

    private static List<Point2D> computePoints(Shape shape, double deviation)
    {
        List<Point2D> result = new ArrayList<Point2D>();
        PathIterator pi = shape.getPathIterator(null, deviation);
        double[] coords = new double[6];
        Point2D newPoint = null;
        Point2D previousMove = null;
        Point2D previousPoint = null;
        while (!pi.isDone())
        {
            int segment = pi.currentSegment(coords);
            switch (segment)
            {
            case PathIterator.SEG_MOVETO:
                previousPoint = new Point2D.Double(coords[0], coords[1]);
                previousMove = new Point2D.Double(coords[0], coords[1]);
                break;

            case PathIterator.SEG_CLOSE:
                createPoints(previousPoint, previousMove, result, deviation);
                break;

            case PathIterator.SEG_LINETO:
                newPoint = new Point2D.Double(coords[0], coords[1]);
                createPoints(previousPoint, newPoint, result, deviation);
                previousPoint = new Point2D.Double(coords[0], coords[1]);
                break;

            case PathIterator.SEG_QUADTO:
            case PathIterator.SEG_CUBICTO:
            default:
                // Should never occur
                throw new AssertionError("Invalid segment in flattened path!");
            }
            pi.next();
        }
        return result;
    }

    private static void createPoints(Point2D p0, Point2D p1,
        List<Point2D> result, double deviation)
    {
        double dx = p1.getX() - p0.getX();
        double dy = p1.getY() - p0.getY();
        double d = Math.hypot(dx, dy);
        int steps = (int) Math.ceil(d / deviation);
        for (int i = 0; i < steps; i++)
        {
            double alpha = (double) i / steps;
            double x = p0.getX() + alpha * dx;
            double y = p0.getY() + alpha * dy;
            result.add(new Point2D.Double(x, y));
        }
    }

    public static Path2D createPath(Iterable<? extends Point2D> points,
        boolean close)
    {
        Path2D path = new Path2D.Double();
        Iterator<? extends Point2D> iterator = points.iterator();
        boolean hasPoints = false;
        if (iterator.hasNext())
        {
            Point2D point = iterator.next();
            path.moveTo(point.getX(), point.getY());
            hasPoints = true;
        }
        while (iterator.hasNext())
        {
            Point2D point = iterator.next();
            path.lineTo(point.getX(), point.getY());
        }
        if (close && hasPoints)
        {
            path.closePath();
        }
        return path;
    }

}

class ShapePanel extends JPanel
{
    private final List<Point2D> points;
    private final Shape shape;

    public ShapePanel(List<Point2D> points, Shape shape)
    {
        this.points = points;
        this.shape = shape;
    }

    @Override
    protected void paintComponent(Graphics gr)
    {
        super.paintComponent(gr);
        Graphics2D g = (Graphics2D) gr;
        g.setRenderingHint(RenderingHints.KEY_ANTIALIASING,
            RenderingHints.VALUE_ANTIALIAS_ON);
        g.setColor(Color.RED);
        g.draw(shape);
        g.setColor(Color.BLACK);
        for (Point2D p : points)
        {
            g.fill(new Ellipse2D.Double(p.getX() - 1, p.getY() - 1, 2, 2));
        }
    }
}

#5

This is a pretty open ended question but if you want them stored in a certain way you need to define the ordering more than "So that they are next to each other in the array" You need to have a function where you can take two points and say, Point A is less than Point B or vice versa, or they are equal.

这是一个很开放的问题,但是如果你希望他们存储在一个特定的方式你需要定义订购超过“所以他们相邻数组中“你需要一个函数,你可以取两个点,点一个小于B点,反之亦然,或者他们是平等的。

If you have that, then the algorithm you need to sort them is already implemented and you can use it by implementing a Comparator as SANN3 said.

如果有，那么排序所需的算法已经实现，可以通过实现一个比较器来使用。

As a side note, you might not want to store a shape as a set of points. I think you might want to store them as a line? You can use a cubic spline to get almost any shape you want then you could save on storage...

作为补充说明，您可能不希望将形状存储为一组点。我想你可能想把它们作为一行存储?你可以用一个三次样条得到几乎任何你想要的形状，然后你可以节省储存…

#6

public class Point implements Comparable

公共类点实现可比

{ ...

{…

... @Override

…@Override

public int compareTo(Pointarg0) {

公共int compareTo(Pointarg0){

    ....

}

}

... }

…}

...

…