Как работает алгоритм объединения двух выпуклых оболочек с использованием их касательных на практике?
Я пытаюсь реализовать в C ++ алгоритм «разделяй и властвуй» для нахождения выпуклой оболочки из набора двумерных точек. Для простоты предположим, что все точки описаны целыми числами.
Самая важная часть алгоритма — это объединение двух выпуклых оболочек, которые вы вычислили из предыдущих рекурсивных вызовов. Эта часть включает в себя поиск нижней и верхней касательных двух выпуклых оболочек, а затем приступает к слиянию.
Объединение является тривиальным, если вы нашли четыре точки, описывающие касательные, то точки, которые не находятся внутри многоугольника, определяемого этими четырьмя точками, будут частью новой выпуклой оболочки.
Однако я понятия не имею, как найти эти четыре пункта.
Вот псевдокод, который большинство источников (этот от http://www.cs.wustl.edu/~pless/506/l3.html) предложить для нахождения нижней касательной выпуклой оболочки HA и выпуклой оболочки HB.
Finding the Lower Tangent
LowerTangent(HA ; HB ) :
(1) Let a be the rightmost point of HA .
(2) Let b be the leftmost point of HB .
(3) While ab is not a lower tangent for HA and HB do
(a) While ab is not a lower tangent to HA do a = a - 1 (move a clockwise).
(b) While ab is not a lower tangent to HB do b = b + 1 (move b counterCW).
(4) Return ab.
(1), (2)
Точки первоначально сортируются по их координате x, поэтому поиск самой правой точки HA и самой левой точки HB можно выполнить в O (1).
a = HA[HA.size-1]
b = HB[0]
Теперь я не могу понять следующие шаги.
Выбрав это ab отрезок, как мы можем проверить, если ab не является нижней касательной, поэтому мы можем войти в первый цикл while или нет?
А потом, как мы перемещаем точку a в a-1 следуя по часовой стрелке? Точки отсортированы по их координате х, и просто a = a-1 приведет к неправильным результатам.
Спасибо!
Решение
Ваша ссылка только кратко заявляет:
Более низкое касание — это условие, которое может быть проверено локально
тест ориентации двух вершин и соседних вершин на
корпус. (Это простое упражнение.)
и, кажется, не дает больше подробностей. я нашел эта ссылка который углубляется в детали того, как найти нижнее касание, включая пример кода.
Также обратите внимание, что вы не должны сортировать X-координаты для этой цели. Этот алгоритм основан на том, что точки находятся в их нормальном последовательном порядке, который определяет многоугольник. Сортировка по X только помогает вам найти начальные точки.
Псевдокод алгоритма нижнего касания из этой ссылки:
idx1 = (Rightmost point index of Poly1)
idx2 = (Leftmost point index of Poly2)
while (TRUE)
while (isLeft(Poly1[idx2], Poly2[idx1], Poly2[idx1+1]) <= 0)
++idx1;
end while
while (isLeft(Poly2[idx1], Poly1[idx2], Poly1[idx2-1]) >= 0)
--idx2;
done = FALSE;
end while
end while
// idx1/idx2 are now the two indices that form the lower tangent
isLeft() Код из той же ссылки:
float isLeft (Point P0, Point P1, Point P2)
{
return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
}
Другие решения
Если два выпуклых многоугольника пересекаются, то неверно предполагать, что есть только две касательные, которые соединяют два многоугольника.
Это зависит от того, как именно очки делятся. Если деление гарантирует, что результирующие выпуклые оболочки никогда не пересекаются, тогда можно сделать такое предположение. Но если разделение точек не гарантирует, что выпуклые оболочки не пересекаются, то алгоритм должен быть модифицирован для нахождения нескольких касательных.