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

Question

Может кто-нибудь помочь мне в том, как нарисовать прямоугольники для пространства в области ограничительной рамки с 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

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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