Как извлечь выпуклую оболочку множества точек из их диаграммы Вороного

Question

Мне нужен алгоритм для вычисления выпуклой оболочки набора точек из диаграммы Вороного точек в O (n).Диаграмма Вороного содержится в ограничительной рамке и хранится в виде двусвязного списка ребер.Ввод представляет собой половину ребра, начало которого находится в ограничительной рамке.

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

Answer 1

Если у вас достаточно большой ограничивающий прямоугольник, так что ограничивающие края имеют только бесконечные ячейки, задача не кажется сложной.Выполните итерацию через ограничивающие ребра, для каждого из них пройдите его вперед и назад, чтобы найти первые неограничивающие ребра F и B.Отметьте текущий и все ограничивающие ребра, найденные во время хода, как used.Края F и B будут бесконечными, если коробка не будет существовать.Таким образом, они касаются граней (fF и fB), чьи «центры» являются частью выпуклой оболочки (текущая грань C), а поперечная кромка C-to-F является частью выпуклой оболочки.Возьмите лицо fF и итерируйте от близнеца F вперед, чтобы найти следующий неограничивающий край, скажем, F1.Если он равен 'B'-близнецу (или его ограничивающие ребра были used), мы закончили.Если нет, перейдите к следующему соседу ('fF1').

Answer 2

Я полагаю, что можно вычислить выпуклую оболочку диаграммы Вороного за O (n) раз.

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

Здесь отсутствует только одна теория, смотрите далее ...

В соответствии с «Вычислительной геометрией» книги Спрингера M4, теорема 7.4: точка q является вершиной Vor (P), еслии только если его самый большой пустой круг C_p (q) содержит три или более сайтов на его границе.Это означает, что сайты, которые необходимо проверять на каждой итерации, выполняются в O (1), что означает, что вам нужно только перебирать O (n) сайтов.

Согласно теореме 7.3 число вершин на диаграмме Вороного системы из n точек в плоскости равняется не более 2n-5 (линейный порядок).

Таким образом, можно вычислить диаграмму СН Вороного за O (n) время.