Очевидно, что вам нужно сгенерировать диаграмму Вороного с учетом ограничений большого многоугольника.Несмотря на то, что вы называете его полигоном, я заметил, что у вашего примера диаграммы есть сплайновые ребра.Давайте забудем об этом сейчас.
Что вы хотите сделать, это убедиться, что вы начинаете с содержащего многоугольника (сгенерированного вами или из другого источника), имеющего ребра довольно равной длины;фактор дисперсии сделал бы это более естественным.Вероятно, я бы выбрал дисперсию в 10-20%.
Теперь, когда ваш содержащийся многоугольник ограничен отрезками линий приблизительно равной длины, у вас есть основа, с которой можно начать генерировать диаграмму Вороного.Для каждого ребра в вашем контейнере:
- Определите нормаль ребра (линия perp, выступающая внутрь от центра этого сегмента).
- Используйте нормаль ребра в качестве скользящей шкалы, на которой нужно разместитьновый узел Вороного узла.Расстояние от самого края будет зависеть от того, каким должен быть ваш средний «диаметр» ячейки Вороного, если бы все они были взяты в виде кругов.В вашем примере это выглядит примерно на 30 пикселей (или каков бы ни был эквивалент в ваших мировых единицах).Опять же, вы должны применить к этому коэффициент дисперсии, чтобы не каждый центр ячейки располагался на равном расстоянии от края его источника.
- Создайте ячейку Вороного для вновь созданного центра.
- Сохраните ячейку Вороногоисходная точка в списке.
По мере того, как вы постепенно генерируете каждую точку, вы должны начать видеть, что алгоритм подразделяет каждую выпуклую "составляющую область" вашего вогнутого контейнера в радиальном направлении.
Возможно, вам интереснодля чего этот списокНу, очевидно, вы еще не закончили, вы сгенерировали только часть общего тесселяции Вороного, которую вы хотите.После того как вы создали эти «граничные» ячейки вашего вогнутого пространства, вы не хотите, чтобы новые ячейки создавались ближе к границе, чем уже есть граничные ячейки, вы хотите, чтобы они были только внутри этой области.Поддерживая список исходных точек граничных ячеек, вы можете гарантировать, что любые дополнительные точки, которые вы создаете, находятся внутри этой области.Это немного похоже на взятие внутренней суммы Минковского, чтобы убедиться, что у вас есть буферная зона.Теперь вы можете рандомизировать оставшиеся ячейки в этом производном вогнутом пространстве до завершения.
(Предостережение emptor: вам нужно быть осторожным с этим предыдущим шагом. Если какие-либо области «прохода» слишком узкие, тограницы этого производного пространства будут перекрываться, у вас будет непростой многоугольник, и вы можете оказаться в неправильных местах, несмотря на ваши усилия. Решение состоит в том, чтобы обеспечить максимальное расстояние от краевбольше половины вашей минимальной ширины прохода ... или используйте другие геометрические средства, в том числе суммирование Минковского, чтобы убедиться, что вы не получите вырожденный многоугольник. Вполне возможно, что вы закончите с мультиполигоном,то есть фрагменты.)
Я сам еще не применял этот метод, но, хотя, безусловно, будут ошибки, с которыми я буду работать, я думаю, что общая идея поможет вам начать в правильном направлении.