Разбиение многоугольника на прямоугольники

На входе есть набор прямоугольников, которые заданы в виде ЦЕЛОЧИСЛЕННЫХ координат ВерхнийЛевыйУгол, НижнийПравыйУгол. Все они либо соприкасаются либо перекрываются либо находятся внутри других прямоугольников. То есть общая их площадь не имеет разрывов. Хотя сама форма может быть и буквой Г и буквой Ш и как угодно. Картинка отображает один из вариантов.

Задача состоит в том, чтобы разбить общую площадь на прямоугольники, ТАК чтобы минимизировать их число и желательно за минимальное время (ну как обычно). На картинке приведен один из вариантов разбиения. Минимальная площадь будет 1 квадратный попугай. Квадрат размером 1х1.

Если будут предложения по алгоритмам, хорошо и быстро решающим эту задачу - буду благодарен.

Миниатюры

 

0

Сообщение от vantfiles просто для растрового есть весьма элементарный алгоритм, хотя и жрущий кучу памяти

Сообщение от QueryMonkey Собственно, программа.

Мне кажется, можно попробовать смасштабировать изображение - и тем самым ускорить алгоритм.

0

Вопрос в том как сделать это так, чтобы не стало в целом хуже ). Честно говоря я уже итак голову сломал в этих координатах, ненавижу подобные задачи. С лупой нужно сидеть выглядывать чтобы нигде циферкой не ошибиться. А при масштабировании - все станет еще хуже в этом плане ))

0

Растровый метод в принципе применим без физического растра.
Нужно определиь функцию GetBoundingRectangle для определения границ области, и GetPixel/FillRectangle чтобы растровый алгоритм работал.
Эти три функции можно реализовать на списке прямоугольников вместо растра.

Или растр хранить в сжатом легкодоступном виде, например RLE сжатие построчно.

Добавлено через 56 секунд
ra81, позвольте полюбопытствовать, какую задачу решаете ?

0

В приведенном примере координат размер растра абсолютно не критичен. 126*190 - это не много. И по словам ТС это характерные величины.

0

Для "игрушечных" размеров я даже с битовой маской не возился.

А вот для миллионных размеров простое построчное сжатие растра не только сэкономило бы память, но и позволило бы увеличить скорость.

0

Сообщение от QueryMonkey Для "игрушечных" размеров я даже с битовой маской не возился. А вот для миллионных размеров простое построчное сжатие растра не только сэкономило бы память, но и позволило бы увеличить скорость.

Тут я и спорить не буду. Но я работал именно с данными, приведенными ТС. Согласен, тут битовая маска - перебор. Чисто для себя написал на питоне реализацию, с тупым проходом по вертикали и сравнением строк растра. Потом, для проверки, еще и по горизонтали прошелся
Про оптимальный раскрой тут и речи, понятно, не идет, однако критерии оптимальности небыли сформулированы...

0

Сообщение от QueryMonkey ra81, позвольте полюбопытствовать, какую задачу решаете ?

собственно ее я озвучил уже. Есть у нас ЛУА интерфейс который позволяет опрашивать исходное приложение вызывая АПИ функции которые очень быстрые на Си. Задача поиска определенных элементов в наборе областей. Области как я описывал перекрываются и вызывать сто раз поиск в одних и тех же местах неправильно. Текущая реализация кушает слишком много и была сделана в лоб. Просто опрашиваем каждую область и все дела. При этом еще и разные сущности ищем разными запросами то есть каждая область по 3 раза опрашивается, что совсем борзота. Запрос я могу делать только на прямоугольник.
На выходе у меня будет список найденных сущностей с которыми будем работать. Первично вроде бы было все ок, пока число областей опроса не начало идти в рост. Кушать начало слишком много.
Для решения вопроса выбран такой маршрут: оптимизировать области, чтобы запрашивать только уникальные, без перекрытий. Так же опрос делать сразу на все виды сущностей, сократив число запросов. Ну и кэшировать полученные уникальные области, дабы не строить их каждый раз. Поэтому скорость первичного алгоритма разбиения на прямоугольники не является сверхкритичной. После изменения областей, будет вызвано лишь 1 раз, после чего закэширована. А кэшировать мы будем координаты прямоугольников, что не потребует особой памяти хранения.

Если назвать прям конкретно, то это мод для игры Факторио. А точнее доработка уже существующего, который не удовлетворяет по скорости работы.

Добавлено через 2 минуты

Сообщение от Parramon В приведенном примере координат размер растра абсолютно не критичен. 126*190 - это не много. И по словам ТС это характерные величины.

В целом да, стотыщ на стотыщ - скорее невероятно. И для таких случаев я заранее думаю сделать ветвление, если мы получим потенциальный размер будущего растра выше величины Х, расчет делать БЕЗ оптимизации, то есть лобовым способом, иначе случайно можно положить все что можно.

0

ra81, понятно.

На мой взгляд если дошли до растра, то это уже и есть ответ в вашем случае. Превращать обратно в список прямоугольников нет необходимости, растр даёт ответ напрямик.

0