Алгоритм деления прямоугольника на более мелкие треугольники?

Question

Какой алгоритм делит прямоугольник (c struct с 4 int s) на случайное количество меньших прямоугольников (возвращает список struct s)?Еще лучше, если максимальным и минимальным размером меньших прямоугольников можно управлять с помощью параметра.

Например,

+----------+            +-------+--+
|          |            |       |  |
|          |            |       |  |
|          |    -->     |---+---+--| (good)
|          |            |   |      |
|          |            +---+      |
|          |            |   |      |
+----------+            +---+------+

Для меньших фигур следует использовать 4-сторонние формы, следующее не годится:

+----------+            +-------+--+
|          |            |       |  |
|          |            |       |  |
|          |    -->     |---+---+--| (not good)
|          |            |          |
|          |            +---+      |
|          |            |   |      |
+----------+            +---+------+

Спасибо!

Приложение: (прямоугольник для обсуждения Морон)

  +----+--------+
  |    |        |
  |    +---+----+
  |    |   |    | (rectangle-chase)
  +----+---+    |
  |        |    |
  +--------+----+

Answer 1

Разделите прямоугольник на две части. Recurse.

Answer 2

Немного странно задавать этот вопрос, не указывая, при каких условиях прямоугольники делятся.

Однако я подозреваю, что вы ищете kd-дерево.Kd-дерево - это двоичное дерево, в котором узлы разделены двумя результирующими дочерними узлами на основе условия.http://en.wikipedia.org/wiki/Kd-tree

Существует также квад-дерево, которое может быть немного проще в реализации.Он включает в себя разбиение узлов на 4 равных по размеру детей.Каждый ребенок рекурсивно разделяется таким образом до некоторого состояния остановки.http://en.wikipedia.org/wiki/Quadtree

[Редактировать: Обновлено в ответ на изменения в операциях.] Может быть проще начать с разделения прямоугольника на четную сетку и решить, какие элементы объединить?В основном подход снизу вверх: просто выберите один и начните случайное объединение соседних ячеек.Не делайте этого для ячеек, которые уже были пройдены, и объединенная структура должна иметь ширину и высоту, чтобы расширение сетки из 2х1 ячеек расширилось до 2х2 или 3х1, чтобы обеспечить постоянное сохранение четырехугольной формы прямоугольникаобъединенный узел.

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

Answer 3

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