Как и в заголовке вопроса, как триангулировать простой многоугольник, который динамически растет, то есть, когда новая вершина добавляется пользователем или компьютером динамически, многоугольник должен снова триангулироваться. Таким образом, вместо того, чтобы запускать какой-либо алгоритм триангуляции после добавления каждой новой вершины, есть ли какой-либо умный / эффективный (возможно, простой в реализации) способ для каждого нового ввода, который должен занять, скажем, ‹= O (n) времени, чтобы триангулировать многоугольник. Вновь добавленная вершина будет смежной с первой и последней вершинами текущего многоугольника.
динамическая триангуляция простого многоугольника
comment
Многоугольник остается выпуклым? Затем, если новая вершина C добавляется между A и B, просто сделайте ABC дополнительным треугольником.
- person Henry schedule 28.12.2015
comment
не обязательно, но это всегда простой многоугольник.
- person mcertitude schedule 28.12.2015
comment
ну, когда новая вершина добавляет треугольник, это довольно просто, но если она «вычитает» его (т.е. когда вершина находится внутри существующего многоугольника), это может очень сильно изменить внутреннюю подготовку, и я сомневаюсь, что есть способ упростить тот. так что, возможно, вы обрабатываете сложение только как частный случай.
- person Anton Knyazyev schedule 28.12.2015
comment
как насчет y-монотонности? скажем, если многоугольник динамически делится на y-монотонные многоугольники, будет ли добавление новой вершины потребовать более O (n) времени для изменения структуры?
- person mcertitude schedule 28.12.2015
comment
Если я прав, бывают ситуации, когда добавление вершины заставляет вас переделывать всю триангуляцию (если новые ребра пересекают все диагонали).
- person Yves Daoust schedule 28.12.2015
Ответы (2)
Когда вы вставляете новую вершину и заменяете ребро двумя, треугольник, который они образуют, может перекрывать несколько треугольников триангуляции. Перекрывающиеся треугольники образуют субполигон. Постройте контур этого многоугольника и вставьте новую вершину. Затем перетриангулируйте обновленный субполигон.
Я предполагаю, что перекрывающиеся треугольники можно эффективно найти, рекурсивно исследуя соседей начального треугольника и проверяя их на перекрытие. Контур субполигона образован краями, не являющимися общими для двух треугольников.
person
Yves Daoust
schedule
28.12.2015
это наблюдение верное, но хотелось чего-то более конкретного, в любом случае спасибо.
- person mcertitude; 29.12.2015
@mcertitude: это очень конкретно. Он показывает вам, что вам все равно нужно ретриангулировать (иногда весь многоугольник), и ускорение процесса в худшем случае является иллюзией. Это также показывает вам, что основным компонентом инкрементного решения является стандартный алгоритм триангуляции. Последние замечания делают его очень близким к работоспособной реализации, которая не кажется такой сложной.
- person Yves Daoust; 29.12.2015
Я предполагаю, что многоугольник увеличивается на каждом шаге, добавляя вершину C, удаляя сегмент AB и добавляя сегменты AC и CB. Я также не предполагаю никаких вырождений.
Если ABC наматывается положительно (то есть многоугольник расширяется «наружу»), просто добавьте ABC к триангуляции.
В противном случае рассмотрим треугольник ABD из предыдущей триангуляции. Если C находится в этом треугольнике, удалите треугольник ABD и добавьте треугольники BDC и DAC. Если это не так, то он находится в субполигоне на стороне AD или на стороне BD. Удалите ABD и перейдите в соответствующий субполигон, добавив C (скажем) к сегменту BD. После завершения рекурсии добавьте треугольники BDC и DAC, как и раньше.
Это решение основывается на простоте как старого, так и нового многоугольника (несамопересечения). В противном случае добавление треугольников после рекурсивного шага может оказаться недопустимым.
person
Sneftel
schedule
28.12.2015
