График Вороного, связанный круговым туром

У меня возникает следующая проблема:
Мне дано облако точек P и подмножество этого облака точек B. Узлы b в B составляют границу (цельной) точки облако P. (Фактически, B задается как замкнутый ориентированный круговой тур). Теперь я хотел бы вычислить диаграмму Вороного P, пересекаемую B, и извлечь область каждого (пересекающегося) многоугольника Вороного. Вот иллюстрация ситуации: http://f.666kb.com/i/cshix1s881107ghfw.png
В принципе, я бы хотел пересечь голубые полигоны с зелеными сегментами. На мои вопросы:График Вороного, связанный круговым туром

Есть ли, по возможности, библиотека C, которая решает эту проблему?
Если нет, есть ли лучший способ решить эту проблему, а затем вычислить диаграмму Вороного с помощью некоторой библиотеки, а затем явно пересечь (зеленые) сегменты с полигонами из выходных данных библиотеки? Может быть, используя ограниченную триангуляцию Делоне?

PS: Я знаю, что этот подвиг, вероятно, будет возможен с использованием CGAL. Однако, никогда не использовав CGAL, CGAL кажется довольно сложным и адаптируемым. Пример кода, такого как this, кажется далеким от прямого. Кроме того, я бы предпочел решение в C.

источник

2014-10-08 Matthias

Вы можете попробовать alphashape. Его треугольная триангуляция без краев, превышающих альфа. – Bytemain

Можете ли вы немного подумать о том, как можно использовать формы альфа для моей цели? – Matthias

: Вы также можете удалить края бесконечности, но с альфа-символами у вас есть альфа-значение, с которым вы можете играть. Но я думаю, что вам нужно ограниченное vd, даже пересечение неточно, не так ли? – Bytemain

Итак, я решил пойти против альфа-форм, так как я уже знаю точную границу и не хочу точно настраивать альфа-значение, чтобы избежать отверстий в интерьере. Вместо этого я использовал комментарий Ante, чтобы придумать реализацию в CGAL. Если кто-то заинтересован, его можно найти here. Мое использование CGAL, вероятно, действительно неуклюжие, и можно сказать, что я родом из мира C, но это начало. Тестовый ввод можно найти here (in.txt) и here (bnd_ind.txt). Визуализация выходного сигнала (выделенные грани поверхности на границе) http://666kb.com/i/csphx8ow43habobik.gif:

источник

2014-10-16 12:15:30 Matthias

: Можете ли вы загрузить изображение? Я был осторожен, потому что ограничение vd может дать другой результат? Алгоритм отличается? Можете ли вы уточнить? – Bytemain

Могу ли я загрузить изображение чего? Вы можете проверить исходный код, который я получил из ссылки в моем ответе. – Matthias

: Я просто спрашиваю. Вы можете загрузить изображение vd? Я считаю, что cdv решает другие проблемы, но я не знаю, как доказать. – Bytemain

График Вороного, связанный круговым туром

ответ

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