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

Question

Может ли кто-нибудь помочь мне в рисовании прямоугольников для пространства в области ограниченной области с n прямоугольными препятствиями? Может быть любое количество параллельных параллельных прямоугольных препятствий, это не единственный случай, поэтому необходимо учитывать различные угловые случаи. Лучше всего использовать алгоритм максимальной горизонтальной полосы? И как?

Описание проблемы:

1.SUB1 и SUB2 препятствия и не будет касаться внутренней из SUB1 и SUB2, вам нужно найти все свободные зоны снаружи всех СУБ и создавать прямоугольники из них.

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

Общее количество максимальных горизонтальных пространственных прямоугольников в этом случае должно быть 7 или в общем случае, 3n + 2 (где п является числом препятствий): alt text http://img25.imageshack.us/img25/452/pic1gts.png

alt text http://img22.imageshack.us/img22/3417/pic2h.png

alt text http://img16.imageshack.us/img16/5818/pic3h.png

alt text http://img13.imageshack.us/img13/2151/pic4.png

Нажмите для просмотра изображения: http://img25.imageshack.us/img25/452/pic1gts.png http://img22.imageshack.us/img22/3417/pic2h.png http://img16.imageshack.us/img16/5818/pic3h.png http://img13.imageshack.us/img13/2151/pic4.png

Answer 1

Вы ищете простейшего алгоритма, или тот, который находит оптимальное наименьшее количество расщепленных прямоугольники?

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

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

Теперь, для каждого препятствия, итерации по списку прямоугольников. Если прямоугольник пересекается с препятствием, удалите прямоугольник из списка и вставьте новые меньшие прямоугольники, которые избегают препятствия. Это небольшая подзадача, которую легко решить, просто посмотрев, какая часть препятствия пересекает прямоугольник. Вы можете получить 0, 1, 2, 3 или 4 новых субэлемента. (рассмотрим шесть случаев, когда препятствие пересекает один угол, два угла, все углы, без углов и без края, без углов и 1 край, без углов и 2 края.)

Повторите все препятствия, и вы слева со списком разделенных прямоугольников, которые покрывают ваш район, не ударяя о препятствия. Это не оптимально мало, но это хорошее место для начала и 10 минут для кодирования.

Answer 2

Да, я ищу, чтобы найти оптимально меньше разрезанных прямоугольников.

Я хотел бы получить немного разъяснений по вашему предложению. «Инициализируйте свой список прямоугольников, чтобы включить только один, прямоугольник экрана».

По экрану прямоугольника, вы имеете в виду внешнее ограничивающее полотно? Тогда у меня будет только один прямоугольник в списке прямоугольников.

«Теперь, для каждого препятствия, итерации по списку прямоугольников.Если прямоугольник пересекается с препятствием, удалите прямоугольник из списка и вставьте новые, меньшие прямоугольники, которые избегают препятствия ».

Чтобы продолжить, следует сделать сравнение на основе каждого коллинеарного края препятствий (4 ребра - левая, правая, верхняя, нижняя)? Значение каждого края SUB1 и SUB2 в 4-х угловых точках проверяются на то, пересекаются ли они друг с другом или с ограничивающей рамкой холста. Правильно ли это?

Answer 3

Структура данных с угловыми строчками может сделать это для вас. Однако я не знаю каких-либо реализаций с открытым исходным кодом. Оригинальная или, по крайней мере, каноническая бумага для этого - Ousterhout (из Tcl fame): http://www.eecs.berkeley.edu/Pubs/TechRpts/1983/6352.html