Как построить диаграмму вороного внутри многоугольника?
Мне нужен алгоритм, который заполняет двумерный невыпуклый многоугольник, который может иметь дырки с точками случайным образом, а затем строит диаграмму вороного на них. Диаграмма должна быть ограничена многоугольником, а алгоритм должен работать в O(n log n),
Моя идея состояла в том, чтобы заполнить полигон, протестировав случайные точки внутри ограничивающей рамки polys, и взяв только точки внутри полигона, а затем выстроив на них вороной, а затем обрезая края диаграммы, выходящие из полигона.
Проблема в том, что тестирование случайных точек и обрезание краев O(n^2),
Можно ли это сделать в boost, или есть другая небольшая библиотека, или что-то еще на самом деле?
Решение
Я думаю, с «дырками» вы, человек, пересечете один замкнутый многоугольник.
Сначала сделайте триангуляцию Делоне для вашего многоугольника:
- Рассчитать точки сечения между сегментами; Добавьте эти точки, разделите сегменты и переставьте входные данные таким образом, чтобы при прохождении точек многоугольника «внутри» всегда было на одной стороне края.
- Пройдите все точки в вашем многоугольнике.
- Удалите треугольники, которые лежат вне вашего многоугольника. Это будут вогнутости и дыры, созданные самопересечениями. Вы можете идентифицировать их, идя по вашему многоугольнику и удаляя все треугольники, которые лежат вне края. Вам нужно связность ребер, но это побочный продукт триангуляции.
Теперь у вас есть отправная точка для дальнейшей триангуляции с Алгоритм Боуера-Ватсона, который триангулирует путем последовательного добавления точек в родительский треугольник. Итак, чтобы добавить случайную точку, мы можем выбрать точку и обновить триангуляцию за один раз:
- Выберите случайный треугольник, где вероятность каждого треугольника, который будет выбран, пропорциональна его площади.
-
Выберите случайное место внутри этого прямоугольника, выбирая барицентрические координаты
s in [0, 1],t in[0, 1]and withс + т < 1`. Ваша новая точка зрения тогда:{P} = s * ({N2} - {N1}) + t * ({N3} - {N1}) -
Добавьте свою точку и повторите триангуляцию родительского треугольника и других треугольников, окружность которых содержит новую точку.
- Набор треугольников для выбора теперь изменился.
Теперь у вас есть триангуляция Делоне, но вам нужна диаграмма Вороного, которую вы можете легко получить, соединив центры всех окружностей соседних треугольников. Опять же, триангуляция Делоне дает вам информацию о окружностях и о том, какие треугольники находятся рядом.
Вы можете использовать алгоритм Бойера-Ватсона в своей первоначальной триангуляции, когда создаете большой фиктивный треугольник, который охватывает все ваши точки.
Я не знаю ни о каких библиотеках триангуляции для C ++, но этот вопрос может начать вас
Другие решения