Разбейте прямоугольник на многоугольники произвольной формы

Question

Как и в заголовке, мне нужно разбить прямоугольник на многоугольники произвольной формы.

Пример с 7 полигонами:

+--------+--------+
|\       |   2    |
| \  1   |''--..__|
|  ------|  5     |
| 3  /   \________|
|   /    /\   6   |
|__/ 4  /  \______|
|      /  7       |
+-----+-----------+

Я не знаю, есть ли уже алгоритм для этого, но я не могу разобраться с этим.

Меня не волнует, на каком языке вы отвечаете, но я буду реализовывать на Java / Swing.

Answer 1

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

Вот реализация Java / Swing.

Я сделал несколько примеров (но с использованием Mathematica , а не вышереализация)

HTH!

Answer 2

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

Редактировать: Таким образом, для вашего образца это было бы так после добавления линий:

+----+---+----+---+
|\'--.\_/|   /    |
| \    X |''/-..__|
|--\--+-\+-/------|
|___\/___\/_______|
|   /\   /\       |
|__/__\_/|_\______|
| /    X |  \     |
++----+-++---+----+