динамическая простая триангуляция многоугольника

Как и в названии вопроса, как триангулировать простой многоугольник, который динамически растет, что сказывается всякий раз, когда новая вершина добавляется пользователем или компьютером динамически, полигон должен снова получить триангуляцию. Поэтому вместо того, чтобы запускать некоторый алгоритм триангуляции после добавления каждой новой вершины, есть ли какой-нибудь умный/эффективный (возможно, простой для реализации) способ для каждого нового ввода, который должен принять: < = O (n) время для триангуляции многоугольника. Новая добавленная вершина будет смежной с первой и последней вершинами текущего многоугольника.динамическая простая триангуляция многоугольника

источник

2015-12-28 mcertitude

Полигоны остаются выпуклыми? Затем, если добавить новую вершину C между A и B, просто добавьте ABC в дополнительный треугольник. – Henry

не обязательно, но это всегда простой полигон. – mcertitude

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

Я предполагаю, что на каждом шаге многоугольник дополняется вершиной C, удаляя сегмент AB и добавляя сегменты AC и CB. Я также не допускаю вырождений.

Если ветер ABC положительно (то есть полигон расширяется «наружу»), просто добавьте ABC к триангуляции.

В противном случае рассмотрим треугольник ABD в предыдущей триангуляции. Если C находится в этом треугольнике, удалите треугольник ABD и добавьте треугольники BDC и DAC. Если это не так, то оно находится в подполилоге на стороне AD или на стороне BD. Удалите ABD и запишите в соответствующий подполигон, добавив C к (скажем) сегменту BD. После завершения рекурсии добавьте треугольники BDC и ЦАП, как и раньше.

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

источник

2015-12-28 13:53:07 Sneftel

Когда вы вставляете новую вершину и заменяете ребро на два, образующийся треугольник может перекрывать несколько треугольников триангуляции. Наложенные треугольники образуют подполигон. Постройте контур этого многоугольника и вставьте новую вершину. Затем отредактируйте обновленный подполигон.

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

источник

2015-12-28 20:51:02

Это замечание верно, но нужно что-то более конкретное, спасибо в любом случае. – mcertitude

@mcertitude: это очень конкретный. Это показывает вам, что вам нужно в любой момент рединеализовать (иногда весь полигон) и сделать его быстрее иллюзорным в худшем случае. Это также показывает, что основным компонентом инкрементного решения является * стандартный * триангуляционный алгоритм. Последние замечания делают его очень близким к выполнимой реализации, которая не кажется настолько сложной. –

динамическая простая триангуляция многоугольника

ответ

Смежные вопросы