Алгоритм генерации непересекающихся многоугольников

[lonelyass]

Для создания тестов к другой геометрической задаче мне нужен алгоритм гереации огромного числа непересекающихся простых многоугольников (simple polygons) на ограниченной плоскости (экране). Например, чтобы по входным параметрам N, K генерировалось N многоугольников с K вершинами каждый, и чтобы они не накладывались один на другой. И желательно делать не только выпуклые многоугольники...
Никогда не встречал подобных алгоритмов и не знаю как подобраться к задаче. Делать перебором по типу "генерируем что-то, а потом проверяем не пересекает ли оно всё остальное" как-то не хочется.

[venco]

lonelyass в сообщении #325532 писал(а):

Делать перебором по типу "генерируем что-то, а потом проверяем не пересекает ли оно всё остальное" как-то не хочется.

Я думаю, ничего лучше нет. Надо только соптимизировать проверку пересечений.

[Circiter]

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

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

Теперь достаточно каждый из полученных многоугольников слегка уменьшить (возможно со случайным коэффициентом масштабирования). А можно ещё что-нибудь с каждым многоугольником проделать, например поотсекать (поудалять) от него отдельные фрагменты... Примерно так...