Как сгенерировать случайный многоугольник без взаимопересечений?

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

  1. Первая мысль: просто накидать случайных точек и соединить в порядке генерации. Часто получаются взаимопересечения.
  2. Вторая мысль: поделить поле на N равных секторов из центра. Очередную точку создавать в своём секторе. Получатся кривые колёса. Но ни одной формы, например, толстой буквы «С». Да и пересечения иногда возникают.
  3. Интуиция подсказывает, что нужно накидать случайных точек, построить триангуляцию Делоне, и выпилить некоторые из граней, так, чтобы не потерять связность и не насоздавать островов и озёр.

Наверное, в разработке игр это типовая задача при создании карт уровней. Как там создают фигуры непростой случайной формы с отсутствием дырок-островов?

Хочется, чтобы имела шанс появиться, например, такая форма: 5b899a73431ab131453344.png
Полезные ссылки из комментариев @myjcom
  • Вопрос задан
  • 627 просмотров
Пригласить эксперта
Ответы на вопрос 2
У меня первая мысль была такая:
1. Создать треугольник. Добавить все его рёбра в список.
2. Взять случайное ребро из списка, оно будет основанием нового треугольника.
3. Сгенерировать точку так, чтобы получился новый треугольник, ни одно из рёбер которого не пересекает рёбра из списка. Два новых ребра добавить в список, основание убрать.
4. Повторять с п.2 пока не будет достигнута требуемая площадь многоугольника.
Ответ написан
Griboks
@Griboks
1. создаёте много простых многоугольников
2. помечаете точки соединения
3. накладываете ограничения на соседние многоугольники
4. генерируете несколько многоугольников с разными соединениями
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы