Версия для печати темы

Автор: SandySandy 25.9.2010, 10:50

есть много rect в массиве, это области для обновления, отрисовка на КПК медленная, и естественно хочется выкинуть лишнее.
на какие алгоритмы стоит обратить внимание?

Автор: kwisp 25.9.2010, 10:59

SandySandy,
требуется уточнение - что собрался выбрасывать, что лишнее?
тема вообще называется "Нужен алгоритм объединения vector<rect>"
если по теме и vector это std::vector то методов куча от алгоритма merge до методов insert append и проч...
если по вопросу про "лишнее" - не понятно.

Автор: Iron Bug 26.9.2010, 22:02

очевидно, имелось в виду объединение прямоугольников в одну общую площадь (точнее, их может быть и несколько), с отбрасыванием "перекрывающихся" прямоугольников.
в голове вертится книга, где про это было подробно написано, но вспомнить название не могу, так как читала я её ещё во времена студенчества.

Автор: kwisp 26.9.2010, 23:12

Iron Bug,
как ты проницательна - ни за что бы по посту не догадался что имеется ввиду. по-моему, могу ошибаться, даже на форуме было что-то подобное

Автор: SandySandy 30.9.2010, 13:37

да вы правы, нужно объединение прямоугольников в минимально возможное по количеству не перекрывающихся прямоугольников

Автор: SandySandy 1.10.2010, 10:03

пока придумал вот такую "грубую" реализацию, разбиваю экран на области например 4х4, создаю bitset например для экрана 320х240 будет 4800 областей, далее цикл по входному вектору с установкой битов, и на основании результатов bitset генерируется новый vector<rect>.

Автор: Алексей1153 1.10.2010, 10:09

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

Твоё решение, кстати, даже побыстрее будет, чем крутой алгоритм объединения прямоугольников ) Только не 4*4, а помельче, наверное, надо. Это - определить экспериментально