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

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

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

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

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

Общее количество максимальных горизонтальных прямоугольников пространства в этом случае должно быть 7 или вообще 3n+2 (где n — количество препятствий): 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< /а>

Щелкните для просмотра изображений: 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


area algorithm tcl
person Community    schedule 14.03.2009    source источник

Ответы (3)


arrow_upward
1
arrow_downward

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

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

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

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

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

person SPWorley    schedule 14.03.2009
comment
Да, я ищу оптимально наименьшее количество разделенных прямоугольников. Теперь для каждого препятствия выполните итерацию по списку прямоугольников. Если прямоугольник пересекается с препятствием, удалите прямоугольник из списка и вставьте новые, меньшие прямоугольники, которые избегают препятствия. Вы можете уточнить? - person ; 14.03.2009

arrow_upward
0
arrow_downward

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

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

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

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

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

person Community    schedule 14.03.2009
comment
Это должны быть комментарии к его ответу, а не другой ответ - person Sparr; 14.03.2009

arrow_upward
0
arrow_downward

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

person Trey Jackson    schedule 14.03.2009
comment
Я попытался применить алгоритм сшивания углов с помощью iTCL, но я думаю, что моя реализация неверна, потому что она на самом деле не работает. из нижнего левого региона и итерации вправо и вверх? Можете ли вы помочь? - person ; 14.03.2009
comment
Алгоритм довольно сложен для правильной реализации, простых советов нет. Это также не связано с холстом. Это просто структура данных (как дерево - вы можете сделать то же самое с четырехъядерным деревом, оно просто другое). - person Trey Jackson; 14.03.2009