Форум программистов, компьютерный форум CyberForum.ru

Объединение прямоугольников (количество объединенных прямоугольников минимально) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.75
max-gambit
0 / 0 / 0
Регистрация: 15.11.2013
Сообщений: 13
14.07.2014, 16:25     Объединение прямоугольников (количество объединенных прямоугольников минимально) #1
Добрый день. Прошу помощи в выполнении задачи.
Дан список прямоугольников, которые задаются координатами верхней левой вершины и размерами (ширина, высота) (целые числа). Необходимо объединить пересекающиеся и соприкасающиеся прямоугольники таким образом, чтобы число полученных в результате объединения прямоугольников было минимально. Дополнительно приоритет желательно отдавать прямоугольникам, максимальная размерность которых (по ширине и высоте) меньше.(см. пример)

Однозначно нужно создать вектор координат Х и координат Y, которые являются вершинами прямоугольников и разбить все поле на ячейки получившейся сетки. Однако, потом как перебирать все варианты получившихся прямоугольников и выбрать требуемый не представляю как(((
Миниатюры
Объединение прямоугольников (количество объединенных прямоугольников минимально)  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.07.2014, 16:25     Объединение прямоугольников (количество объединенных прямоугольников минимально)
Посмотрите здесь:

C++ Поиск прямоугольников.
C++ Пересечение прямоугольников
C++ класс прямоугольников
C++ пересечение прямоугольников
Посчитать количество прямоугольников, заданных черным цветом C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
max-gambit
0 / 0 / 0
Регистрация: 15.11.2013
Сообщений: 13
15.07.2014, 09:04  [ТС]     Объединение прямоугольников (количество объединенных прямоугольников минимально) #2
никто не подскажет?((
Ilot
Модератор
Эксперт С++
1767 / 1142 / 223
Регистрация: 16.05.2013
Сообщений: 3,020
Записей в блоге: 5
Завершенные тесты: 1
15.07.2014, 09:49     Объединение прямоугольников (количество объединенных прямоугольников минимально) #3
Единственное, что приходит на ум поступить следующим образом. Предположим, что заданные прямоуголиники имеют кратные размеры. Тогда заданную комбинацию будем представлять не координатами углов, а массивом заполнения ячеек. Поступаем следующим образом: сперва берем наибольший прямоугольник, который вмещается в область, ограничивающую заданную комбинацию прямоугодльников, и проверяем может ли он вместиться в заданную комбинацию или нет (проверяется по ячейкам a[i][j] == true && b[i][j] == true). Если вхождение не возможно берем прямоугольник на одну строку меньше и так же проверяем. Породя реккурсию получим наибольший прямоугольник который можно вписать в область, а так же его координаты. Теперь проделываем ту же комбинацию, но уже в осавшейся области. Понятно, что алгоритм не идеален, но по крайней мере должен работать. Как то так...
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,334
Завершенные тесты: 1
15.07.2014, 09:51     Объединение прямоугольников (количество объединенных прямоугольников минимально) #4
Цитата Сообщение от max-gambit Посмотреть сообщение
как перебирать все варианты получившихся прямоугольников и выбрать требуемый
От начала прям вектора проходить и глядеть: если координата угла плюс длина стороны в этом направлении равна координате угла следующего прямоугольника, то объединять их. В один проход вообще все делается.
max-gambit
0 / 0 / 0
Регистрация: 15.11.2013
Сообщений: 13
15.07.2014, 10:46  [ТС]     Объединение прямоугольников (количество объединенных прямоугольников минимально) #5
SatanaXIII, здесь все сложнее. если тупо прибавлять прямоугольник к прямоугольнику, то не факт, что в результате получится минимальное количество прямоугольников, к тому же в задании есть пометка, что "Дополнительно приоритет желательно отдавать прямоугольникам, максимальная размерность которых (по ширине и высоте) меньше.(см. пример)". Т.е. из количества минимальных прямоугольников нужно выбрать тот вариант, который оптимален по данному критерию, а именно по минимуму периметров прямоугольников.
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,334
Завершенные тесты: 1
15.07.2014, 11:19     Объединение прямоугольников (количество объединенных прямоугольников минимально) #6
max-gambit, стандартный (уже) алгоритм:
Двойной цикл - обход каждого угла прямоугольников. От каждого угла вниз и вправо пройти до пустой ячейки. До этих границ проверить полученный сектор на отсутствие пустых ячеек. Сравнить где больше; проверить для вашего случая на наибольшую квадратность. Объединить.
max-gambit
0 / 0 / 0
Регистрация: 15.11.2013
Сообщений: 13
15.07.2014, 12:54  [ТС]     Объединение прямоугольников (количество объединенных прямоугольников минимально) #7
SatanaXIII, алгоритм шикарный, но не совсем верный для моей задачи. Нужно чтобы было минимальное количество прямоугольников, а нахождение самого большого это не обеспечит(( сижу, думаю дальше...
На рисунке: если мы виделим бОльший, то в результате получится 3 прямоугольника, а если выделим так, как по цвету указано - то два. И этот вариант верный..
Миниатюры
Объединение прямоугольников (количество объединенных прямоугольников минимально)  
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,334
Завершенные тесты: 1
15.07.2014, 13:03     Объединение прямоугольников (количество объединенных прямоугольников минимально) #8
max-gambit, тут однозначного решения не придумаешь. Я лишь предложил метод. Эвристика остается на ваше усмотрение.

Вот прям совершенно первая попавшаяся мысль: сделать многопроходный алгоритм. То есть внешний третий цикл по числу прямоугольников, или даже просто по площади, по гипотетическому количеству ячеек. И на каждой итерации хранить либо два варианта слияний (предыдущую и текущую) и выбирать среди них более подходящую, имеющую меньшее количество прямоугольников, но с большим коэффициентом квадратности. Либо запомнить все варианты различных слияний и потом уже по ним пройтись и выяснить лучший.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2014, 16:07     Объединение прямоугольников (количество объединенных прямоугольников минимально)
Еще ссылки по теме:

C++ вложенность прямоугольников
метод прямоугольников C++
Даны стороны трех прямоугольников Найти периметры и площади этих прямоугольников C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
max-gambit
0 / 0 / 0
Регистрация: 15.11.2013
Сообщений: 13
16.07.2014, 16:07  [ТС]     Объединение прямоугольников (количество объединенных прямоугольников минимально) #9
Сижу, думаю, не допру как найти все варианты сочетаний прямоугольников, чтобы сравнить их количество и определить минимальное((
Yandex
Объявления
16.07.2014, 16:07     Объединение прямоугольников (количество объединенных прямоугольников минимально)
Ответ Создать тему
Опции темы

Текущее время: 23:05. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru