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

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

Возможно, «>» повернуто не в ту сторону, но вы поняли.

Answer 4

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

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

Как это:

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

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

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

Answer 5

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

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

Идеи? * * 1004

Answer 6

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

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

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