Простой многоугольник из неупорядоченных точек

Question

Я пытался создать алгоритм для нахождения порядка точек в простом многоугольнике. Цель состоит в том, чтобы при заданных точках на 2D-плоскости (между прочим, всегда можно сформировать простой многоугольник) я выводил порядок точек в допустимом простом многоугольнике. Все точки должны быть частью указанного многоугольника.

Я в некоторой степени достиг этого, но в некоторых тестах это не удается. Я сделал это, найдя геометрический центр

int centerX = (lowX + highX) / 2;
            int centerY = (lowY + highY) / 2;

            Point center = new Point(centerX, centerY, -1);

и затем отсортировав все точки по их полярному углу.

Collections.sort(points, (a, b) -> {
                if(a == b || a.equals(b)) {
                    return 0;
                }
                double aTheta = Math.atan2((long)a.y - center.y, (long)a.x - center.x);
                double bTheta = Math.atan2((long)b.y - center.y, (long)b.x - center.x);
                if(aTheta < bTheta) {
                    return -1;
                }
                else if(aTheta > bTheta) {
                    return 1;
                }
                else {
                    double aDist = Math.sqrt((((long)center.x - a.x) * ((long)center.x - a.x)) +
                                            (((long)center.y - a.y) * ((long)center.y - a.y)));

                    double bDist = Math.sqrt((((long)center.x - b.x) * ((long)center.x - b.x)) +
                                            (((long)center.y - b.y) * ((long)center.y - b.y)));

                    if (aDist < bDist) {
                        return -1;
                    } 
                    else {
                        return 1;
                    }
                }    
            });

Я пытаюсь выяснить, что делает этот разрыв для некоторых тестовых случаев. Любая помощь или указатели очень ценятся! Также интересно, есть ли эффективные, но не слишком сложные алгоритмы, которые могут выполнить это.

ОБНОВЛЕНИЕ

Я обнаружил один из неудачных тестовых случаев: При заданных точках (101, 101), (100, 100), (105, 100), (103, 100), (107, 100), (102, 100), (109, 100) Отмечены от 0 до 9 соответственно

Моя программа выводит 2 4 6 0 3 5 1 но это недопустимый простой многоугольник

Это должна быть перестановка 1 0 6 4 2 3 5

Answer 1

Вот Java реализация красивого ответа , уже предоставленного Reblochon Masque .

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

Кроме того, когда есть ie в зависимости от ориентации, поскольку точка min и две точки коллинеарны, мы разбиваем t ie, учитывая относительное упорядочение двух точек. Это означает, что мы будем посещать точки по порядку, без «обратных ключей», что, на мой взгляд, предпочтительнее.

static List<Point2D> simplePolygon(Collection<Point2D> points)
{       
    final Point2D min = minPoint2D(points);

    List<Point2D> simple = new ArrayList<>(points);
    Collections.sort(simple, (p1, p2) ->
    {
        int cmp = orient2D(min, p2, p1); 
        if(cmp == 0) 
            cmp = order2D(p1, p2);
        return cmp;
    });

    return simple;
}

// return lowest, leftmost point
static Point2D minPoint2D(Collection<Point2D> points)
{
    Point2D min = null;
    for(Point2D p : points)
        if(min == null || order2D(p, min) < 0) min = p;
    return min;
}

// order points by increasing y, break ties by increasing x
static int order2D(Point2D p1, Point2D p2)
{
    if(p1.getY() < p2.getY()) return -1;
    else if(p1.getY() > p2.getY()) return 1;
    else if(p1.getX() < p2.getX()) return -1;
    else if(p1.getX() > p2.getX()) return 1;
    else return 0;
}

// Does p involve a CCW(+1), CW(-1) or No(0) turn from the line p1-p2
static int orient2D(Point2D p1, Point2D p2, Point2D p)
{
    double dx = p2.getX() - p1.getX();
    double dy = p2.getY() - p1.getY();      
    double px = p.getX() - p1.getX();
    double py = p.getY() - p1.getY();       
    double dot = py * dx - px * dy;     
    return dot < 0 ? -1 : dot > 0 ? 1 : 0;
}

Тест:

int[] a = {101, 101, 100, 100, 105, 100, 103, 100, 107, 100, 102, 100, 109, 100};

List<Point2D> points = new ArrayList<>();
for(int i=0; i<a.length; i+=2) 
    points.add(new Point2D.Double(a[i], a[i+1]));

List<Point2D> simple = simplePolygon(points);       
for(Point2D p : simple) System.out.println(p);

Вывод:

Point2D.Double[100.0, 100.0]
Point2D.Double[102.0, 100.0]
Point2D.Double[103.0, 100.0]
Point2D.Double[105.0, 100.0]
Point2D.Double[107.0, 100.0]
Point2D.Double[109.0, 100.0]
Point2D.Double[101.0, 101.0]

Что я считаю правильным.

Answer 2

- это простой в реализации алгоритм O(n logn), который гарантированно создаст простой многоугольник (без пересечений ребер).

1 - найдите точку на юге (и на западе, если у вас ie со значениями y).

2 - Сортировка всех точек на основе их угла между этой самой южной точкой и горизонтальной линией.

3 - упорядоченная последовательность представляет собой простой многоугольник ,

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