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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 8, средняя оценка - 4.75
max-gambit
0 / 0 / 0
Регистрация: 15.11.2013
Сообщений: 13
#1

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

14.07.2014, 16:25. Просмотров 1244. Ответов 8
Метки нет (Все метки)

Добрый день. Прошу помощи в выполнении задачи.
Дан список прямоугольников, которые задаются координатами верхней левой вершины и размерами (ширина, высота) (целые числа). Необходимо объединить пересекающиеся и соприкасающиеся прямоугольники таким образом, чтобы число полученных в результате объединения прямоугольников было минимально. Дополнительно приоритет желательно отдавать прямоугольникам, максимальная размерность которых (по ширине и высоте) меньше.(см. пример)

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

Даны стороны трех прямоугольников Найти периметры и площади этих прямоугольников - C++
1. S1=SSS(a1, b1); S2=SSS(a2, b2); S3=SSS(a3, b3); -------------------------------- int SSS(int a, int b) { return (a*b);...

Найти количество прямоугольников на листке в клеточку - C++
Здравствуйте!Есть задача.Смысл таков:вводим два числа A и B(0<A<=10^9,0<B<=10^9).Это размеры листка.Нужно найти количество прямоугольников...

Посчитать количество прямоугольников, заданных черным цветом - C++
С++ изучаю несколько месяцев и есть проблемы с синтаксисом и пониманием=) Не совсем понятно что от меня требуют? И не знаю как...

С++ Метод прямоугольников - C++
Помогите пожалуйсто с задачкой. Метод вроде понятен, но составить прграмму неполучается что-то. Составьте программу находящую значение...

метод прямоугольников - C++
помогите пожалуйста написать код программы. Составить алгоритм и записать программу, которая выполняет итерационной алгоритм метода...

Поиск прямоугольников. - C++
Есть такая задача: дан массив 100х100 состоящий из нулей и единиц. Из единиц построены прямоугольники, так, что они не могут совпадать и...

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

Вот прям совершенно первая попавшаяся мысль: сделать многопроходный алгоритм. То есть внешний третий цикл по числу прямоугольников, или даже просто по площади, по гипотетическому количеству ячеек. И на каждой итерации хранить либо два варианта слияний (предыдущую и текущую) и выбирать среди них более подходящую, имеющую меньшее количество прямоугольников, но с большим коэффициентом квадратности. Либо запомнить все варианты различных слияний и потом уже по ним пройтись и выяснить лучший.
0
max-gambit
0 / 0 / 0
Регистрация: 15.11.2013
Сообщений: 13
16.07.2014, 16:07  [ТС] #9
Сижу, думаю, не допру как найти все варианты сочетаний прямоугольников, чтобы сравнить их количество и определить минимальное((
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.07.2014, 16:07
Привет! Вот еще темы с ответами:

вложенность прямоугольников - C++
bool Intersects(Rect Obj1, Rect Obj2) { int x1 = Obj1.ItsLeftUpperGetX(); int y1 = Obj1.ItsLeftUpperGetY(); int x2 =...

Площади прямоугольников - C++
Здраствуйте!я начинающий на с/с++ написал программу которая вычисляет площадь пересечения прямоугольников,вылазит ошибка:scratch: ...

Метод прямоугольников - C++
Здравствуйте! Есть выражение: y = −2^2 + 3x + 6, y = x + 2. Использовать метод прямоугольников. Для построения прямоугольника...

Пересечение прямоугольников - C++
В прямоугольной системе координат (оси расположены слева направо и сверху вниз) заданы два прямоугольника (стороны параллельны осям). Найти...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
16.07.2014, 16:07
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru