Определение порядка вершин для формирования четырехугольника

Question

Предположим, у меня есть 4 вершины в 2D-пространстве.Знает ли что-нибудь об эффективном алгоритме, который даст мне порядок вершин, который соответствует простому четырехугольнику?То есть он будет помечать вершины 1, 2, 3, 4, так что если я буду следовать 1-2, 2-3, 3-4, я буду отслеживать простой (то есть непересекающийся) четырехугольник.

Просто предоставив имя стандартного алгоритма, который я могуGoogle будет хорошо.

Answer 1

Вы можете просто Google для сортировки точек по часовой стрелке, и вы получите, например:

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

Answer 2

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

Answer 3

Если ваша форма выпуклая, вы можете идти в порядке намотки вокруг барицентра ваших точек (то есть центра тяжести или «среднего»):

B = (X_1 + X_2 + X_3 + X_4) / 4

Обе координаты каждой вершины будутлибо выше, либо ниже соответствующей координаты барицентра:

 (-,+)                   (+,+)
   X                       X

              B
      X
    (-,-)               X
                      (+,-)

Итак, начиная с любой точки, просто перейдите к одной точке, для которой изменяется только один из двух знаков, но не оба.

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

Примечаниечто для невыпуклого набора точек (т. е. набора, в котором одна точка содержится в открытой внутренней части выпуклой оболочки множества), может быть более одного четырехугольника с этими точками в качестве вершин (представьте себе все путисоединяя внутреннюю вершину с двумя внешними). ​​

Answer 4

Существует решение, которое не требует вычисления "центра", включает в себя только несколько умножений и сложений и изящно обрабатывает вырожденные случаи (например, все точки коллинеарны).

Рассмотрим четырехугольник с углами ABCD(то есть есть линии AB, BC, CD и DA).

Рассмотрим четыре треугольника ABC, ABD, ACD, BCD

Существует простая формула для определения площади каждоготреугольник, см. http://www.cs.princeton.edu/~rs/AlgsDS07/16Geometric.pdf стр. 9, если вершины (Ax, Ay), (Bx, By), (Cx, Cy)

Area = (Bx - Ax) (Cy - Ay) - (By - Ay) (Cx - Ax)

Если область, если положительные точки направлены против часовой стрелки, отрицательные - по часовой стрелке, нулевые - коллинеарны.

Это возможно длянепересекающийся четырехугольник, имеющий три коллинеарные точки.Таким образом, один из треугольников ABC, ABD, ACD, BCD может иметь нулевую область.Но если два из них имеют нулевую площадь, это означает, что ABCD должен быть коллинеарным, и поэтому все четыре треугольника имеют нулевую площадь.В этом случае непересекающееся расположение невозможно.

Поэтому вычислите области, соответствующие ABC, ABD и ACD (вам нужно учитывать только три треугольника).

Если два из них имеют нольобласти, все три будут иметь нулевую область, четыре точки ABCD коллинеарны.

Если одна из них имеет нулевую область, выберите две другие области.

Если ни одна из них не имеет нулевой области,просто выберите любые две из трех областей.

Если четырехугольник не пересекается, то эти два треугольника должны вращаться одинаково, то есть оба по часовой стрелке или оба против часовой стрелки.Это означает, что произведение двух областей должно быть положительным (положительным положительным или отрицательным отрицательным).Так что просто сформируйте произведение двух областей, обе из которых отличны от нуля, чтобы получить ненулевой результат.Если произведение площадей больше нуля, четырехугольник не пересекает сам себя, если он меньше нуля, он самопересекается.

Answer 5

Кривая Мортона или Z-кривой доставит его.Но я предлагаю кривую Гильберта или кривую Мура из-за лучших атрибутов заполнения пространства.