Как сортировать коллекцию точек так, чтобы они настраивались один за другим?

Ответ 1

Я считаю, что вам сначала нужно математическое определение вашего заказа. Я предлагаю (обратите внимание, это определение не было ясным в исходном вопросе, оставленном здесь для полноты):

Начиная с размещения любой точки в последовательности, затем постоянно добавляйте к последовательности точку, ближайшую к текущей точке и которая еще не была добавлена ​​к последовательности, пока все точки не будут добавлены к последовательности.

Таким образом, с этим определением упорядочения вы можете получить простой алгоритм для этого

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));
}

Вышеприведенное довольно универсальное (независимо от алгоритма поиска следующей точки). Затем метод 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;
}

Обновление: Поскольку вопрос был пересмотрен, чтобы в значительной степени принять определение, которое я использовал, я взял некоторые из оговорок.

Ответ 2

Вот возможное решение для вас: наша цель - построить путь, который посещает каждый из точек в вашем списке ровно один раз, прежде чем он зациклится. Мы можем конструировать пути рекурсивно: мы можем выбрать любую точку из исходного списка в качестве отправной точки и сделать тривиальный путь, состоящий только из одного node. Затем мы можем расширить уже построенный путь, добавив точку, которую мы еще не посетили.

Затем мы предполагаем, что мы можем найти хороший порядок для исходного списка точек, убедившись, выбрав путь с наименьшей длиной. Здесь по длине я не имею в виду количество точек на пути, а общую сумму евклидова расстояния между каждой парой соседних точек на пути.

Единственная проблема заключается в следующем: учитывая такой путь, какой пункт мы должны добавить дальше? Теоретически нам нужно было бы попробовать все возможности, чтобы увидеть, какой из них ведет к лучшему общему пути.

Основной трюк, который используется в приведенном ниже коде, заключается в том, что он использует следующую эвристику: на каждом шаге, где мы должны добавить новую точку в построенный до сих пор путь, выберите точку, которая минимизирует среднее расстояние между двумя соседними точками.

Следует отметить, что было бы неплохо включить в это "расстояние цикла" между последней точкой пути и первой точкой: поскольку мы продолжаем добавлять точки, мы удаляемся от первой точки пути больше и более. Если бы мы включили расстояние между двумя конечными точками, это серьезно повлияло бы на среднее расстояние между всеми соседними парами и, таким образом, повредило бы нашу эвристику.

Вот простой вспомогательный класс для реализации конструкции пути, описанной выше:

/**
 * 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;
        }
    }
}

И вот настоящий алгоритм эвристического поиска.

/**
 * 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;
}

Если вы запустите этот код на примерах вашего вопроса, а затем соедините каждую смежную пару точек из возвращенного списка, вы получите следующее изображение:

Ответ 3

Это не алгоритм 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) - надеюсь, вам не нужно делать это миллионы раз.

Если вы хотите, чтобы точки отображались в предсказуемом порядке (скажем, самый левый в начале), вы можете добавить фальшивую точку в начале списка перед ее восстановлением и удалить ее после. Алгоритм всегда будет оставлять только одну точку.

Ответ 4

Я начал это вскоре после вопроса, но он был отложен из-за того, что вопрос был приостановлен. Это простой подход, который в то же время также упоминается в комментариях и других ответах, но я все равно отправлю его сюда:

Вот MCVE, показывающий самый простой и простой подход. Подход просто состоит в том, чтобы выбрать произвольную точку, а затем продолжить, всегда выбирая точку, которая ближе всего к предыдущей. Конечно, это имеет ограничения:

• Он может выбрать неправильную точку, когда есть острые углы или точки возврата.
• Это не очень эффективно, потому что он многократно выполняет поиск ближайшей точки

Одним из подходов к его ускорению может быть сортировка точек на основе x-координаты, а затем использование этого частичного упорядочения, чтобы пропустить большинство точек при поиске следующего соседа. Но пока вы не хотите применять это до десяти тысяч точек в критическом по времени контексте, это не должно быть проблемой.

Возможные двусмысленности, в свою очередь, могут быть проблемой, но, учитывая это, нужно сказать, что проблема ничем не определена. В некоторых случаях даже человек не мог решить, какой пункт является подходящей "следующей" точкой - по крайней мере, когда проблема не расширяется, чтобы обнаружить "внутреннюю/внешнюю" фигуры (это несколько похоже на проблему двусмысленности в алгоритме маршевого куба: Вы просто не знаете, что такое предполагаемый путь).

Обратите внимание, что большая часть кода не очень важна для вашего фактического вопроса, но... вы не обеспечили такую ​​ "заглушку". Соответствующая часть === 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

Это довольно открытый вопрос, но если вы хотите, чтобы они были сохранены определенным образом, вам нужно определить порядок больше, чем "чтобы они были рядом друг с другом в массиве". У вас должна быть функция, в которой вы можете возьмите две точки и скажите: точка A меньше точки B или наоборот, или они равны.

Если у вас это есть, то алгоритм, который вам нужен для их сортировки, уже реализован, и вы можете использовать его, реализовав Компаратор, как сказал SANN3.

В качестве побочной заметки вы можете не захотеть сохранять фигуру в виде набора точек. Думаю, вам захочется сохранить их как линию? Вы можете использовать кубический сплайн, чтобы получить практически любую фигуру, которую вы хотите, чтобы сохранить ее на хранение...

Ответ 6

public class Point реализует сравнимые

{ ...

... @Override

public int compareTo (Pointarg0) {

    ....

}

... }

...