Алгоритм для деления прямоугольника к меньшим перепутаницам?
Что алгоритм должен разделить прямоугольник (c struct с 4 ints) к случайному числу меньших прямоугольников (возвращают список structs)? Еще лучше, если макс. размером и минимальным размером меньших прямоугольников может управлять параметр.
например.
+----------+ +-------+--+
| | | | |
| | | | |
| | --> |---+---+--| (good)
| | | | |
| | +---+ |
| | | | |
+----------+ +---+------+
меньшие формы должны быть 4-сторонними, следующее не хорошо:
+----------+ +-------+--+
| | | | |
| | | | |
| | --> |---+---+--| (not good)
| | | |
| | +---+ |
| | | | |
+----------+ +---+------+
Спасибо!
Приложение: (прямоугольник для обсуждения Идиота)
+----+--------+
| | |
| +---+----+
| | | | (rectangle-chase)
+----+---+ |
| | |
+--------+----+
3 ответа
Выберите случайную точку p на одном крае и разделите там прямоугольник линией на противоположном крае. Затем вы можете выполнять рекурсию на обеих половинах, останавливая рекурсию случайным образом или с указанным пределом.
Немного странно задавать этот вопрос, не уточняя, при каких условиях разбиваются прямоугольники.
Однако я подозреваю, что то, что вы ищете, - это kd-дерево. kd-дерево - это двоичное дерево, в котором узлы разделяются с двумя результирующими дочерними узлами на основе условия. http://en.wikipedia.org/wiki/Kd-tree
Существует также квадродерево, которое может быть немного проще в реализации. Оно предполагает разбиение узлов на 4 равных по размеру дочерних узла. Каждый дочерний узел рекурсивно делится таким образом до некоторого условия остановки. http://en.wikipedia.org/wiki/Quadtree
[Edit: Updated in response to op's edits]. Для того, что вы делаете, может быть проще начать с деления прямоугольника на ровную сетку и решить, какие элементы нужно объединить? По сути, подход "снизу вверх": просто выберите один и начните объединять соседние ячейки случайным образом. Не делайте этого для клеток, которые уже были пройдены, и объединенная структура должна иметь ширину и высоту так, чтобы при расширении сетки из 2x1 клеток она расширялась до 2x2 или 3x1, чтобы постоянно сохранять форму 4-стороннего прямоугольника для объединенного узла.
Если вы хотите более сложный подход, вы можете подойти к этому как к kd-дереву и построить его сверху вниз, но вам придется объединять целые поддеревья, поскольку вы разделяете их, основываясь на случайных условиях и параметрах минимальной/максимальной ширины/высоты.