Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Нужен алгоритм объединения vector<rect>
Форум на CrossPlatform.RU > Курилка > Алгоритмы, задачи по программированию, логические игры
SandySandy
есть много rect в массиве, это области для обновления, отрисовка на КПК медленная, и естественно хочется выкинуть лишнее.
на какие алгоритмы стоит обратить внимание?


kwisp
SandySandy,
требуется уточнение - что собрался выбрасывать, что лишнее?
тема вообще называется "Нужен алгоритм объединения vector<rect>"
если по теме и vector это std::vector то методов куча от алгоритма merge до методов insert append и проч...
если по вопросу про "лишнее" - не понятно.
Iron Bug
очевидно, имелось в виду объединение прямоугольников в одну общую площадь (точнее, их может быть и несколько), с отбрасыванием "перекрывающихся" прямоугольников.
в голове вертится книга, где про это было подробно написано, но вспомнить название не могу, так как читала я её ещё во времена студенчества.
kwisp
Iron Bug,
как ты проницательна - ни за что бы по посту не догадался что имеется ввиду.:) по-моему, могу ошибаться, даже на форуме было что-то подобное
SandySandy
да вы правы, нужно объединение прямоугольников в минимально возможное по количеству не перекрывающихся прямоугольников
SandySandy
Цитата(SandySandy @ 30.9.2010, 13:37) *
да вы правы, нужно объединение прямоугольников в минимально возможное по количеству не перекрывающихся прямоугольников

пока придумал вот такую "грубую" реализацию, разбиваю экран на области например 4х4, создаю bitset например для экрана 320х240 будет 4800 областей, далее цикл по входному вектору с установкой битов, и на основании результатов bitset генерируется новый vector<rect>.
Алексей1153
Цитата(SandySandy @ 1.10.2010, 13:03) *
создаю bitset например для экрана 320х240 будет 4800 областей,

лучше тогда bitset<4*4> и создавать - зачем столько озу в КПК съедать ? Границы областей известны - экран, разбитый на 4 части по горизонтали и вертикали.

Твоё решение, кстати, даже побыстрее будет, чем крутой алгоритм объединения прямоугольников ) Только не 4*4, а помельче, наверное, надо. Это - определить экспериментально
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Форум IP.Board © 2001-2022 IPS, Inc.