Как построить диаграмму Вороного внутри многоугольника?

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

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

Проблема в том, что проверка случайных точек и отсечение краев — это O(n^2).

Можно ли это сделать в boost, или есть другая небольшая библиотека или что-то еще?


c++ boost algorithm voronoi
person Community    schedule 23.05.2014    source источник
comment
это похоже на работу для триангуляции Делоне   -  person UmNyobe    schedule 23.05.2014

Ответы (1)


arrow_upward
1
arrow_downward

Я предполагаю, что с «дырами» вы сталкиваетесь с самопересечениями одного замкнутого многоугольника.

Сначала выполните триангуляцию Делоне вашего многоугольника:

  • Рассчитать точки сечения между сегментами; добавьте эти точки, разделите сегменты и перестройте ввод так, чтобы «внутри» всегда находились на одной и той же стороне края при пересечении точек многоугольника.
  • Трангулируйте все точки вашего многоугольника.
  • Удалите треугольники, которые лежат за пределами вашего полигона. Это будут вогнутости и отверстия, созданные самопересечениями. Вы можете идентифицировать их, пройдясь по вашему многоугольнику и удалив все треугольники, лежащие за пределами ребра. Вам нужна связность ребер, но это побочный продукт триангуляции.

Теперь у вас есть отправная точка для дальнейшей триангуляции с помощью алгоритма Бойера-Ватсона, который выполняет триангуляцию, последовательно добавляя точки к родительскому треугольнику. Итак, чтобы добавить случайную точку, мы можем выбрать точку и обновить триангуляцию за один раз:

  • Выберите случайный треугольник, где вероятность того, что каждый треугольник будет выбран, пропорциональна его площади.

  • Выберите случайное место внутри этого треугольника, выбрав барицентрические координаты s in [0, 1], t in[0, 1]and withs + т ‹ 1`. Тогда ваша новая точка:

    {P} = s * ({N2} - {N1}) + t * ({N3} - {N1})

  • Добавьте свою точку и повторите триангуляцию родительского треугольника и других треугольников, описанная окружность которых содержит новую точку.

  • Набор треугольников для выбора теперь изменился.

Теперь у вас есть триангуляция Делоне, но вам нужна диаграмма Вороного, которую можно легко получить, соединив центры всех описанных окружностей соседних треугольников. Опять же, триангуляция Делоне предоставляет вам информацию о описанных окружностях и о том, какие треугольники являются смежными.

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

Мне неизвестны какие-либо библиотеки триангуляции для C++, но этот вопрос может чтобы вы начали.

person M Oehm    schedule 23.05.2014