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

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

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

• Если у вас есть четыре точки, 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), чтобы изменить обмотку многоугольника в целом по часовой стрелке.

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

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

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

Верхнее левое > верхнее правое > нижнее правое > нижнее левое

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

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

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

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

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

Оливер прав. Этот код (сообщество викифицировано) генерирует и сортирует все возможные комбинации массива из 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;
}

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

Более конкретной задачей будет сортировка координат путем уменьшения угла относительно положительной оси 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 точки по часовой стрелке. Определение того, какая операция свопа необходима, - это, конечно, трюк.

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

Помните-это те случаи, в которых мы можем быть.

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 проверок каждый раз, и более одного своп; но код был бы намного проще.

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

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

Подробнее на этом сайте

Я полагаю, что вы правы, что один своп может гарантировать, что многоугольник, представленный четырьмя точками на плоскости, выпукл. Вопросы, на которые еще предстоит ответить:

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

При дальнейшем размышлении я думаю, что единственный ответ на второй вопрос выше - это "два средних".

Как насчет этого?

// Take signed area of ABC.
// If negative,
//     Swap B and C.
// Otherwise,
//     Take signed area of ACD.
//     If negative, swap C and D.

Идеи?

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

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

if AB crosses CD
   swap B,C
elif AD crosses BC
   swap C,D

if area (ABC) > 0
   swap B,D

(I mean area(ABC) > 0 when A->B->C is counter-clockwise).
Let p*x + q*y + r = 0 be the straight line that joins A and B.
Then AB crosses CD if  p*Cx + q*Cy + r  and  p*Dx + q*Dy + r
have different sign, i.e. their product is negative.

Первое "if/elif" приводит четыре точки по часовой стрелке или против часовой стрелки. (Поскольку ваш многоугольник выпуклый, единственной альтернативой "пересечения" является "AC пересекает BD", что означает, что четыре точки уже отсортированы.) Последнее "если" меняет ориентацию всякий раз, когда оно против часовой стрелки.

Если мы предположим, что точка x больше точки y, если угол, который она имеет с точкой (0,0) больше, то мы можем реализовать это таким образом в c#

    class Point : IComparable<Point>
    {
        public int X { set; get; }
        public int Y { set; get; }

        public double Angle
        {
            get
            {
                return Math.Atan2(X, Y);
            }
        }

        #region IComparable<Point> Members

        public int CompareTo(Point other)
        {
            return this.Angle.CompareTo(other.Angle);
        }

        #endregion

        public static List<Point>  Sort(List<Point> points)
        {
            return points.Sort();
        }
}

Если вам просто нужно разобраться с 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]]

Ответ Веджа верен.

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

Вот так:

centerPonintX = Min(x) + (  (Max(x) – Min(x)) / 2  )
centerPonintY = Min(y) + (  (Max(y) – Min(y)) / 2  )

Затем уменьшите centerPointX и centerPointY от каждой точки, чтобы перевести ее в начало границы.

Наконец, примените решение Веджа только с одним поворотом: получите абсолютное значение arctan (x/y) для каждого экземпляра (работал для меня таким образом).

if( (p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y) )
    swap( &p1, &p3 );

" > " может быть обращено не в ту сторону, но вы поняли идею.