Вид четыре точки в по часовой стрелке заказывает

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

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' вводит четыре точки по часовой стрелке или против часовой стрелки порядок. (Так как Ваш полигон выпукл, единственная другая альтернатива 'пересечения' является 'перекрестным BD AC', что означает, что четыре точки уже отсортированы.) Последнее, 'если' ориентация инвертирования каждый раз, когда это против часовой стрелки.

Ответ Wedge’s корректен.

Для реализации его легко я думаю тот же путь как smacl: необходимо найти, что boundary’s центрируют и переводят точки в тот центр.

Как это:

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

Затем уменьшите centerPointX и centerPointY от каждого poin для перевода его в boundary’s источник.

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

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

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

Идеи?

Необходимо смотреть на Сканирование Graham. Конечно, необходимо будет адаптировать его, так как это находит к точкам против часовой стрелки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Несколько мыслей достойных рассмотрения здесь;

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

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

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

Работа это длинный путь тогда оптимизирует его.

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