Здравствуйте, коллеги
Столкнулся с такой задачей в некую функцию добавляют/ удаляют прямоугольники заданный двумя точками X1Y1 (верхний, левый) и X2Y2 (нижний правый).

void Add(X1, Y1, X2, Y2);
void Remove(X1, Y1, X2, Y2);

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

Здравствуйте, Аноним, Вы писали:

А>Столкнулся с такой задачей в некую функцию добавляют/ удаляют прямоугольники заданный двумя точками X1Y1 (верхний, левый) и X2Y2 (нижний правый).

А>void Add(X1, Y1, X2, Y2);
А>void Remove(X1, Y1, X2, Y2);


Удаляются только те прямоугольники, которые уже были добавлены? Если это так, то просто заведи пару сбалансированных деревьев поиска, например. При добавлении прямоугольника добавляешь в одно дерево ключи x1 и x2, а в другое дерево ключи y1 и y2. При удалении просто исключаешь из деревьев соответствующие ключи. Обрамляющий прямоугольник находится из наименьшего и наибольшего значения ключей из обоих деревьев. Дублирующиеся ключи в деревьях можно хранить либо многократно, либо в комбинации "уникальный ключ" + счётчик.
Если удаляться могут не только добавленные прямоугольники, и нужно определять такую ситуацию (например, сообщая об невозможности удаления), то можно несложно изменить структуру данных и для такого случая — в дереве сделать ключи уникальными, а в данных, связанных с ключом, хранить множество уникальных идентификаторов для добавленных прямоугольников. Тогда при вызове удаления можно будет определить, добавлялся ранее такой прямоугольник или нет.

Здравствуйте, watchmaker, Вы писали:

W>Если удаляться могут не только добавленные прямоугольники, и нужно определять такую ситуацию (например, сообщая об невозможности удаления), то можно несложно изменить структуру данных и для такого случая — в дереве сделать ключи уникальными, а в данных, связанных с ключом, хранить множество уникальных идентификаторов для добавленных прямоугольников. Тогда при вызове удаления можно будет определить, добавлялся ранее такой прямоугольник или нет.

Проще говоря, сделать (хеш)-таблицу с ключами — 4-элементными векторами.
Добавляем прямоугольник — добавляем в его таблицу (кстати, проверяем, не был ли он добавлен ранее; что делать с дубликатами?) и добавляем его габариты в мультимножества.
Удаляем — соответственно, проверяем наличие в таблице, удаляем оттуда, и вычёркиваем по одному вхождению из мультимножеств.


А если удаляться могут произвольные прямоугольники (вырезаться из существующего покрытия), то придётся сделать quad-tree.

Здравствуйте, Аноним, Вы писали:
А>И собственно задача постоянно поддерживать максимальный обрамляющий прямоугольник, над всеми добавленными, ну при одном добавлении в этом нет ник каких проблем, просто расширяем экстент и все, сложности начинаются когда прямоугольники удаляют.
простенькое решение — завести 4 кучи (heap). в C++ кстати ф-ии есть в стандартной библиотеке для работы с ними.
каждая куча — координата соотв-но x, y левого верхнего угла и x, y правого нижнего

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

Здравствуйте, __kot2, Вы писали:

__>простенькое решение — завести 4 кучи (heap). в C++ кстати ф-ии есть в стандартной библиотеке для работы с ними.
__>каждая куча — координата соотв-но x, y левого верхнего угла и x, y правого нижнего
Куча плоха тем, что из неё удалить элемент по значению можно только почти полным просмотром. Уж если ограничивать себя стандартной библиотекой C++, то std::map или std::multiset куда лучше себя ведут по мере увеличения числа прямоугольников.

Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, __kot2, Вы писали:
__>>простенькое решение — завести 4 кучи (heap). в C++ кстати ф-ии есть в стандартной библиотеке для работы с ними.
__>>каждая куча — координата соотв-но x, y левого верхнего угла и x, y правого нижнего
W>Куча плоха тем, что из неё удалить элемент по значению можно только почти полным просмотром. Уж если ограничивать себя стандартной библиотекой C++, то std::map или std::multiset куда лучше себя ведут по мере увеличения числа прямоугольников.
че-то не подумал. в общем, да, 4 дерева получается лучше. правда нужные элементы не на вершине будут лежать, а будут самыми левыми или правыми листьями, но тоже ничего страшного

Здравствуйте, Аноним, Вы писали:

А>И собственно задача постоянно поддерживать максимальный обрамляющий прямоугольник

коллеги, я чтото непонял? неужели для этой задачи недостаточно после каждого Add/Remove банально мин и мах координаты определять?

Здравствуйте, __kot2, Вы писали:

__> 4 дерева получается лучше. правда нужные элементы не на вершине будут лежать, а будут самыми левыми или правыми листьями, но тоже ничего страшного
Зачем четыре-то? :)
Сам же сказал, что элементы будут левыми или правыми листьями.

Здравствуйте, pik, Вы писали:

pik>Здравствуйте, Аноним, Вы писали:

А>>И собственно задача постоянно поддерживать максимальный обрамляющий прямоугольник

pik>коллеги, я чтото непонял? неужели для этой задачи недостаточно после каждого Add/Remove банально мин и мах координаты определять?

Достаточно. Просто это может быть сложнее или проще сделать. Как именно устроена задача из формулировки непонятно. Если там под удалением прямоугольника подразумевается csg, то даже с самой подзадачей определения минимальной координаты возникнут некоторые сложности (хотя, конечно, на плоскости да с прямыми параллельными осям всё проще). К сожалению из исходного сообщения не ясно, нужно ли csg рассматривать или требуется что-то другое.

Здравствуйте, watchmaker, Вы писали:

W>Достаточно. Просто это может быть сложнее или проще сделать. Как именно устроена задача из формулировки непонятно. Если там под удалением прямоугольника подразумевается csg, то даже с самой подзадачей определения минимальной координаты возникнут некоторые сложности (хотя, конечно, на плоскости да с прямыми параллельными осям всё проще). К сожалению из исходного сообщения не ясно, нужно ли csg рассматривать или требуется что-то другое.

по сообщению ТС можно понять что это простая задача на определение минлево-верх и макс право-низ, как при добавлении так и изятии.
не надо из этого докрорскую работу писать

в некую функцию добавляют/ удаляют прямоугольники заданный двумя точками X1Y1 (верхний, левый) и X2Y2 (нижний правый).

Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, __kot2, Вы писали:

__>> 4 дерева получается лучше. правда нужные элементы не на вершине будут лежать, а будут самыми левыми или правыми листьями, но тоже ничего страшного
W>Зачем четыре-то?
W>Сам же сказал, что элементы будут левыми или правыми листьями.
да, с деревом можно двумя обойтись — отдельно для x и для y