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

Question

[Сергей Соколов]

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

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

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

Хочется, чтобы имела шанс появиться, например, такая форма:

Полезные ссылки из комментариев @myjcom

• генерация внешнего контура массива точек
  
• генерация игровых ландшафтов (но с возможными дырками и островами) на Хабре и оригинал на англ.
  
• список алгоритмов генерации уровней для игр, Random Walk и производные (Drunkard Walk) – интересны, но допускают дырки и острова.
  

Comments

[Даниил Басманов]

Сергей Соколов, Под какую платформу?

[Сергей Соколов]

Даниил Басманов, web, JS.

Answer 1

[Павел Язовских]

У меня первая мысль была такая:
1. Создать треугольник. Добавить все его рёбра в список.
2. Взять случайное ребро из списка, оно будет основанием нового треугольника.
3. Сгенерировать точку так, чтобы получился новый треугольник, ни одно из рёбер которого не пересекает рёбра из списка. Два новых ребра добавить в список, основание убрать.
4. Повторять с п.2 пока не будет достигнута требуемая площадь многоугольника.

Comments

[Сергей Соколов]

Хороший способ, гарантирует отсутствие оторванных островов, т.к. строим от предыдущего.
Список всегда будет содержать внешний контур.
При добавлении точки, получившийся треугольник может содержать в себе мЕньший предыдущий (или несколько). Рёбра не пересекутся. Но это простое для проверки условие.

[Павел Язовских]

Сергей Соколов, тогда нужно будет ещё проверять, чтобы медиана не пересекала других рёбер. Мне кажется, хорошим вариантом будет строить равнобедренный треугольник.
Ещё остаётся случай, если новый будет меньше предыдущего и целиком лежать в нём.

[Павел Язовских]

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

[Павел Язовских]

Можно усложнить алгоритм, чтобы получить многоугольник, больше напоминающий сеть пещер. Для этого, кроме одного списка с рёбрами всего многоугольника нужно завести несколько списков с "генерирующими" рёбрами. После добавления очередного трегольника, в генерирующий список заносится только одно случайное ребро из двух и увеличивается счётчик для этого списка. После достижения какого-либо количества сгенерированных с помощью этого списка треугольников, на очередной итерации заводится ещё один список, в который кладётся второе ребро, т.е. получится "развилка".

[Сергей Соколов]

unepic, генерация в «неправильную» сторону допустима, наверное: почему бы не «выедать» из площади существующего треугольника мЕньший треугольник?

Answer 2

[Griboks]

1. создаёте много простых многоугольников
2. помечаете точки соединения
3. накладываете ограничения на соседние многоугольники
4. генерируете несколько многоугольников с разными соединениями

Comments

[Сергей Соколов]

не понял пункт 3

накладываете ограничения на соседние многоугольники

[Griboks]

Сергей Соколов, например, что бы не пересекались соседние комнаты, если они разной формы. Или что бы не повторялись.