Сортировка четырех точек по часовой стрелке

Question

Четыре 2D точки в массиве. Мне нужно отсортировать их по часовой стрелке. Я думаю, что это можно сделать всего одной операцией подкачки, но я не смог официально это сформулировать.

Редактировать: четыре точки в моем случае - выпуклый многоугольник.

Редактировать: четыре точки являются вершинами выпуклого многоугольника. Они не должны быть в порядке.

Answer 1

Если вы хотите принять более математическую перспективу, мы можем рассмотреть перестановки 4 баллов

В нашем случае есть 4 перестановки, которые расположены по часовой стрелке

A B C D
B C D A
C D A B
D A B C

Все другие возможные перестановки могут быть преобразованы в одну из этих форм с заменой 0 или 1. (Я буду рассматривать только перестановки, начинающиеся с A, поскольку они симметричны)

1. A B C D - сделано
2. A B D C - поменять местами C и D
3. A C B D - поменять местами B и C
4. A C D B - поменять местами A и B
5. A D B C - поменять местами A и D
6. A D C B - поменять местами B и D

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

Глядя на первые три точки и проверяя знак области ABC со знаком, мы можем определить, по часовой стрелке они или нет. Если они по часовой стрелке, то мы в случае 1 2 или 5

чтобы различать эти случаи, мы должны проверить еще два треугольника - если ACD по часовой стрелке, то мы можем сузить это до случая 1, в противном случае мы должны быть в случае 2 или 5.

Для выбора между случаями 2 и 5 мы можем проверить ABD

Аналогичным образом мы можем проверить случай ABC против часовой стрелки.

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

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

Answer 2

Пара мыслей, которые стоит рассмотреть здесь;

• По часовой стрелке имеет смысл только в отношении происхождения. Я склонен думать о происхождении как о центре тяжести множества точек. например По часовой стрелке относительно точки в среднем положении четырех точек, а не в возможно очень отдаленном начале.

• Если у вас есть четыре точки a, b, c, d, существует множество порядков этих точек по часовой стрелке вокруг вашего источника. Например, если (a, b, c, d) сформировано упорядочение по часовой стрелке, то (b, c, d, a), (c, d, a, b) и (d, a, b, c)

• Ваши четыре точки уже образуют многоугольник? Если это так, то это вопрос проверки и изменения намотки, а не сортировки точек, например, a, b, c, d становится d, c, b, a. Если нет, я бы отсортировал на основе отношения соединения между каждой точкой и началом координат согласно ответу Клинья.

Редактировать: относительно ваших комментариев, на какие пункты свопить;

В случае треугольника (a, b, c) мы можем сказать, что это по часовой стрелке, если третья точка c находится с правой стороны линии ab . Я использую следующую побочную функцию, чтобы определить это на основе координат точки:

int side(double x1,double y1,double x2,double y2,double px,double py)
{
 double dx1,dx2,dy1,dy2;
 double o;

 dx1 = x2 - x1;
 dy1 = y2 - y1;
 dx2 = px - x1;
 dy2 = py - y1;
 o = (dx1*dy2)-(dy1*dx2);
 if (o > 0.0) return(LEFT_SIDE);
 if (o < 0.0) return(RIGHT_SIDE);
 return(COLINEAR);
}

Если у меня есть четырехточечный выпуклый многоугольник, (a, b, c, d), я могу рассматривать это как два треугольника, (a, b, c) и (c, d, a). Если (a, b, c) против часовой стрелки, я изменяю обмотку (a, b, c, d) на (a, d, c, b), чтобы изменить обмотку многоугольника в целом по часовой стрелке. *

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

Answer 3

Если кому-то интересно, вот мое быстрое и грязное решение похожей проблемы.

Моя проблема состояла в том, чтобы мои прямоугольные углы были упорядочены в следующем порядке:

верхний левый> верхний правый> нижний правый> нижний левый

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

Идея алгоритма такова:

Упорядочить углы по строкам, а затем упорядочить пары углов по столбцам.

// top-left = 0; top-right = 1; 
// right-bottom = 2; left-bottom = 3;
List<Point> orderRectCorners(List<Point> corners) {    
    if(corners.size() == 4) {    
        ordCorners = orderPointsByRows(corners);

        if(ordCorners.get(0).x > ordCorners.get(1).x) { // swap points
            Point tmp = ordCorners.get(0);
            ordCorners.set(0, ordCorners.get(1));
            ordCorners.set(1, tmp);
        }

        if(ordCorners.get(2).x < ordCorners.get(3).x) { // swap points
            Point tmp = ordCorners.get(2);
            ordCorners.set(2, ordCorners.get(3));
            ordCorners.set(3, tmp);
        }               
        return ordCorners;
    }    
    return empty list or something;
}

List<Point> orderPointsByRows(List<Point> points) {
    Collections.sort(points, new Comparator<Point>() {
        public int compare(Point p1, Point p2) {
        if (p1.y < p2.y) return -1;
        if (p1.y > p2.y) return 1;
        return 0;
        }
    });
    return points;
}

Answer 4

Оливер прав. Этот код (wikified сообщество) генерирует и сортирует все возможные комбинации массива из 4 точек.

#include <cstdio>
#include <algorithm>

struct PointF {
    float x;
    float y;
};

// Returns the z-component of the cross product of a and b
inline double CrossProductZ(const PointF &a, const PointF &b) {
    return a.x * b.y - a.y * b.x;
}

// Orientation is positive if abc is counterclockwise, negative if clockwise.
// (It is actually twice the area of triangle abc, calculated using the
// Shoelace formula: http://en.wikipedia.org/wiki/Shoelace_formula .)
inline double Orientation(const PointF &a, const PointF &b, const PointF &c) {
    return CrossProductZ(a, b) + CrossProductZ(b, c) + CrossProductZ(c, a);
}

void Sort4PointsClockwise(PointF points[4]){
    PointF& a = points[0];
    PointF& b = points[1];
    PointF& c = points[2];
    PointF& d = points[3];

    if (Orientation(a, b, c) < 0.0) {
        // Triangle abc is already clockwise.  Where does d fit?
        if (Orientation(a, c, d) < 0.0) {
            return;           // Cool!
        } else if (Orientation(a, b, d) < 0.0) {
            std::swap(d, c);
        } else {
            std::swap(a, d);
        }
    } else if (Orientation(a, c, d) < 0.0) {
        // Triangle abc is counterclockwise, i.e. acb is clockwise.
        // Also, acd is clockwise.
        if (Orientation(a, b, d) < 0.0) {
            std::swap(b, c);
        } else {
            std::swap(a, b);
        }
    } else {
        // Triangle abc is counterclockwise, and acd is counterclockwise.
        // Therefore, abcd is counterclockwise.
        std::swap(a, c);
    }
}

void PrintPoints(const char *caption, const PointF points[4]){
    printf("%s: (%f,%f),(%f,%f),(%f,%f),(%f,%f)\n", caption,
        points[0].x, points[0].y, points[1].x, points[1].y,
        points[2].x, points[2].y, points[3].x, points[3].y);
}

int main(){
    PointF points[] = {
        {5.0f, 20.0f},
        {5.0f, 5.0f},
        {20.0f, 20.0f},
        {20.0f, 5.0f}
    };

    for(int i = 0; i < 4; i++){
        for(int j = 0; j < 4; j++){
            if(j == i)  continue;
            for(int k = 0; k < 4; k++){
                if(j == k || i == k) continue;
                for(int l = 0; l < 4; l++){
                    if(j == l || i == l || k == l) continue;
                    PointF sample[4];
                    sample[0] = points[i];
                    sample[1] = points[j];
                    sample[2] = points[k];
                    sample[3] = points[l];

                    PrintPoints("input: ", sample);
                    Sort4PointsClockwise(sample);
                    PrintPoints("output: ", sample);
                    printf("\n");
                }
            }
        }
    }

    return 0;
}

Answer 5

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

Answer 6

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

1. сортировка по значению y

2. верхняя строка - первые две точки, нижняя строка - остальные 2 точки

3. для верхнего и нижнего ряда, сортируйте их по значению x

.

corners.sort(key=lambda ii: ii[1], reverse=True)
topRow = corners[0:2]
bottomRow = corners[2:]

topRow.sort(key=lambda ii: ii[0])
bottomRow.sort(key=lambda ii: ii[0])
# clockwise
return [topRow[0], topRow[1], bottomRow[1], bottomRow[0]]

Answer 7

var arr = [{x:3,y:3},{x:4,y:1},{x:0,y:2},{x:5,y:2},{x:1,y:1}];
var reference = {x:2,y:2};
arr.sort(function(a,b)  {
    var aTanA = Math.atan2((a.y - reference.y),(a.x - reference.x));
    var aTanB = Math.atan2((b.y - reference.y),(b.x - reference.x));
    if (aTanA < aTanB) return -1;
    else if (aTanB < aTanA) return 1;
    return 0;
});
console.log(arr);

Где контрольная точка лежит внутри многоугольника.

Больше информации на этом сайте

Answer 8

У меня есть еще одно улучшение, чтобы добавить к моему предыдущему ответу

помните - в таких случаях мы можем быть.

1. A B C D
2. A B D C
3. A C B D
4. A C D B
5. A D B C
6. A D C B

Если ABC против часовой стрелки (имеет отрицательную подписанную область), то мы находимся в случаях 3, 4, 6. Если в этом случае мы поменяем местами B & C, то у нас останутся следующие возможности:

1. A B C D
2. A B D C
3. A B C D
4. A B D C
5. A D B C
6. A D B C

Затем мы можем проверить ABD и поменять местами B & D, если оно против часовой стрелки (случаи 5, 6)

1. A B C D
2. A B D C
3. A B C D
4. A B D C
5. A B D C
6. A B D C

Наконец, нам нужно проверить ACD и поменять местами C & D, если ACD против часовой стрелки. Теперь мы знаем, что у нас все в порядке.

Этот метод не так эффективен, как мой предыдущий метод - для этого требуется 3 проверки каждый раз и более одного обмена; но код был бы намного проще.

Answer 9

Проработайте это долго, а затем оптимизируйте.

Более конкретной проблемой будет сортировка координат путем уменьшения угла относительно положительной оси x. Этот угол в радианах будет определяться этой функцией:

x>0
    AND y >= 0
       angle = arctan(y/x)
    AND y < 0
       angle = arctan(y/x) + 2*pi
x==0
    AND y >= 0
       angle = 0
    AND y < 0
       angle = 3*pi/2
x<0
    angle = arctan(y/x) + pi

Тогда, конечно, это просто вопрос сортировки координат по углу. Обратите внимание, что arctan (w)> arctan (z) тогда и только тогда, когда x> z, поэтому вы можете оптимизировать функцию, которая довольно легко сравнивает углы друг с другом.

Сортировка так, что угол монотонно уменьшается по окну (или так, что он увеличивается не более одного раза), немного отличается.

Вместо обширного доказательства я упомяну, что я проверил, что одна операция свопинга будет сортировать 4 2D точки по часовой стрелке. Определить, какая операция подкачки необходима, - это, конечно, хитрость.

Answer 10

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

p.s: Это может быть излишним за 4 очка, но если количество очков увеличится, это может быть интересно