Как определить, является ли треугольник Делоне внутренним или внешним?

Question

Я пишу программу, которая требует реализации извлечения медиальной оси, триангуляция Делоне является шагом. Внешняя медиальная ось нежелательна, поэтому соответствующие внешние треугольники предназначены для удаления. К счастью, я наткнулся на страницу с множеством диаграмм, а также намеком на метод определения внутренних и внешних треугольников Делоне («по периметру пунктирной линии»), но это всего лишь подсказка, без объяснение. Кто-нибудь знает алгоритм?

РЕДАКТИРОВАТЬ: я забыл упомянуть, что начальные точки отбираются от границы замкнутого многоугольника, я собираюсь определить, находится ли каждый треугольник Делоне внутри многоугольника.

Answer 1

Это решение предполагает, что у вас есть структура данных, которая представляет триангуляцию Делоне с использованием «виртуальной бесконечной вершины Делоне», как это делает CGAL ( подробности см. Здесь ).

Идея состоит в том, чтобы найти граничные ребра Делоне: ребра, соединяющие две последовательные точки выборки; а затем "затопить" через триангуляцию Делоне, чтобы классифицировать лица Делоне. Известно, что бесконечная вершина является внешней, поэтому ее соседей (и соседей соседей и т. Д.) Можно классифицировать как внешние, если только они не пересекают граничные ребра. Достигнув граничного края, можно просто пометить соседний треугольник как внутренний и продолжить аналогичным образом.

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

1. Рассчитайте триангуляцию Делоне ваших очков
2. Отметьте ребра Делоне, которые соединяют две последовательные точки отбора. (См. на стр. 4-5 этой статьи как это можно сделать с помощью локального теста на каждом краю Делоне)
3. Классифицируйте все бесконечные грани Делоне как ВНЕ и переместите их в очередь Q .
4. Пока Q не пусто
   1. Лицо Делоне f = Pop от Q
   2. Для каждого неклассифицированного соседнего треугольника t of f
      • , если отмечен край Делоне, общий для t и f , классифицировать t как противоположность f
      • еще классифицировать т так же, как f
      • push t до Q
5. Для каждого края Делоне e
   • , если два соседних треугольника Делоне d1 , d2 оба классифицированы как ИНТЕРЬЕР, выведите сегмент, соединяющий центр окружности d1 и d2 .

Для такого ввода

следующая аппроксимация средней оси может быть вычислена:

Вы можете проверить, как это приближение по средней оси ведет себя на практике, используя бесплатный двоичный файл windows Mesecina . Исходный код здесь .

Answer 2

Рассматривали ли вы использование другой формы триангуляции, которая не создает внешние треугольники? Однажды я взял курс, который проводил много времени, обсуждая теоретические аспекты триангуляции многоугольника. Может быть, просмотр сайта курса даст вам некоторое представление? http://cgm.cs.mcgill.ca/~godfried/teaching/cg-web.html#triangulation

Редактировать: На самом деле, я просто подумал о другом. Если у вас уже есть полигон, который вы пытаетесь триангулировать, вы можете использовать теорему Грина. Теорема Грина использует периметр многоугольника для вычисления его площади! Что еще более важно, в этом случае вы можете определить, находится ли точка на одной стороне линии или на другой, посмотрев на знак области. Теорема Грина про полигоны решает простую задачу вычитания. Поэтому возьмите любую точку, которую вы ЗНАЕТЕ, находится внутри многоугольника, и вычислите площадь у каждого края многоугольника. Это говорит о том, на какой стороне каждой линии должна быть ваша точка. Теперь просто возьмите точку внутри каждого треугольника и сделайте то же самое. Если какой-либо из признаков неправильный, тогда у вас есть внешний треугольник. (Примечание: в зависимости от формы вашего многоугольника это может на самом деле не работать. Для выпуклых многоугольников это должно работать нормально, но вогнутости могут привести к дополнительным сложностям.)

Answer 3

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

Использование предложенного алгоритма для невыпуклого многоугольника показывает, что он не всегда восстанавливает фактическую триангуляцию. http://www.cc.kyoto -su.ac.jp / ~ Ацуси / июнь / Темы / Teddy / изображения / example2_2.jpg

Answer 4

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

Почему бы просто не триангулировать многоугольник (используя монотонную декомпозицию или что-то подобное), чтобы вы никогда не создавали никаких внешних треугольников? Я полагаю, это может увеличить время выполнения (сначала выполнить триангуляцию во время O (nlogn), а затем создать триангуляцию Делоне за время O (n ^ 2)), но может быть более быстрый способ сделать это.