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

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

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

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

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

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

Идеи?

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

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

Здесь стоит подумать о паре мыслей;

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

• Если у вас есть четыре точки, 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. Если нет, я бы отсортировал по подшипнику соединения между каждой точкой и исходной точкой в ​​соответствии с ответом Wedges.

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

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

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

Ответ Wedge правильный.

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

Нравится:

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

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

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

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

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

если мы предположим, что точка 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 точек

В нашем случае есть 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 треугольника.

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

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», что означает, что четыре точки уже отсортированы.) Последнее 'if' меняет ориентацию всякий раз, когда оно вращается против часовой стрелки.

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

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

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

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

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

1. А Б В Г
2. А Б Г В
3. А В Б Г
4. А В Г Б
5. А Г Б В
6. А Г В Б

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

1. А Б В Г
2. А Б Г В
3. А Б В Г
4. А Б Г В
5. А Г Б В
6. А Г Б В

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

1. А Б В Г
2. А Б Г В
3. А Б В Г
4. А Б Г В
5. А Б Г В
6. А Б Г В

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

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

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

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

top-left > top-right > bottom-right > bottom-left

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

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

Расположите углы по рядам, а затем расположите пары углов по столбцам.

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

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.info(arr);

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

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

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

если вам просто нужно иметь дело с 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]]