Выпуклая оболочка 4 точек
Я хотел бы, чтобы алгоритм вычислил выпуклую оболочку 4 2D точек. Я посмотрел на алгоритмы для обобщенной проблемы, но интересно, существует ли простое решение для 4 точек.
3 ответа
Возьмите три точки, и определить, является ли их треугольник по часовой стрелке или против часовой стрелки ::
triangle_ABC= (A.y-B.y)*C.x + (B.x-A.x)*C.y + (A.x*B.y-B.x*A.y)
для правой системы координат, это значение будет положительным, если ABC против часовой стрелки , отрицательный по часовой стрелке и ноль, если они коллинеарны. Но следующее будет работать так же, как и для левосторонней системы координат, так как ориентация является родственником.
Вычислите сопоставимые значения для трех треугольников, содержащих четвертую точку:
triangle_ABD= (A.y-B.y)*D.x + (B.x-A.x)*D.y + (A.x*B.y-B.x*A.y)
triangle_BCD= (B.y-C.y)*D.x + (C.x-B.x)*D.y + (B.x*C.y-C.x*B.y)
triangle_CAD= (C.y-A.y)*D.x + (A.x-C.x)*D.y + (C.x*A.y-A.x*C.y)
, если все три {ABD, BCD, CAD} имеют одинаковый знак, что и ABC, то D находится внутри ABC, а корпус представляет собой треугольник ABC.
Если два из {ABD, BCD, CAD} имеют один и тот же знак, что и ABC, и у одного есть противоположный знак, то все четыре очка экстремально, а корпус четырехугольник ABCD.
Если один из {ABD, BCD, CAD} имеет тот же знак, что и ABC, а два имеют противоположный знак, то выпуклый корпус представляет собой треугольник с одинаковым знаком; Оставшаяся точка внутри нее.
Если какой-либо из ценностей треугольника равен нулю, три точки коллинера, а средняя точка не экстремальная. Если все четыре точка коллинеарны, все четыре значения должны быть ноль, а корпус будет либо в строке, либо точке. Остерегайтесь численных проблем устойчивости в этих случаях!
Для тех случаев, когда ABC является положительным:
ABC ABD BCD CAD hull
------------------------
+ + + + ABC
+ + + - ABCD
+ + - + ABDC
+ + - - ABD
+ - + + ADBC
+ - + - BCD
+ - - + CAD
+ - - - [should not happen]
Вот более эмиссионный алгоритм, специфичный до 4 баллов:
- Найти показатели точек с минимальными X, Maximum-X, минимум и максимум и получить Уникальные значения из этого. Например, индексы могут быть 0,2,1,2, а уникальные значения будут 0,2,1.
- Если есть 4 уникальных значения, то выпуклый корпус состоит из всех 4 точек.
- Если есть 3 уникальных значения, то эти 3 точки определенно в выпуклой корпусе. Проверьте, находится ли 4-й точка в пределах этого треугольника; Если нет, это также часть выпуклой корпуса.
- Если есть 2 уникальных значения, то эти 2 точка находятся на корпусе. Из остальных 2 очков точка, которая далее от этой линии, соединяющая эти 2 очка, определенно на корпусе. Проверьте, чтобы проверить ли тест треугольника, чтобы проверить, также находится в корпусе.
- Если есть 1 уникальное значение, то все 4 балла сопрекочены.
Некоторые вычисления требуются, если есть 4 очка, чтобы заказать их правильно, чтобы избежать получения галстук . Хммм .... Похоже, есть достаточно особых случаев, чтобы оправдать использование обобщенного алгоритма. Однако вы могли бы настроить это, чтобы работать быстрее, чем обобщенный алгоритм.