Сортировка четырех точек по часовой стрелке - PullRequest
29 голосов
/ 28 октября 2008

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

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

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

Ответы [ 16 ]

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

0 голосов
/ 28 октября 2008

если мы предположим, что точка 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();
        }
}
0 голосов
/ 28 октября 2008
if( (p2.x-p1.x)*(p3.y-p1.y) > (p3.x-p1.x)*(p2.y-p1.y) )
    swap( &p1, &p3 );

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

0 голосов
/ 28 октября 2008

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

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

Как это:

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

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

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

0 голосов
/ 28 октября 2008

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

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

Идеи? * * 1004

0 голосов
/ 28 октября 2008

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

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...