Пересечения прямоугольников

Предполагая систему координат слева направо / сверху вниз, пересечением двух прямоугольников является прямоугольник, вершина которого является самой нижней из вершин, нижняя часть является самой верхней из низов, левая, если самая правая из левых и правая является самым левым из правых.

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

Альтернативой может быть использование ключа (для карты), представляющего собой пару x/delta с оператором‹, который учитывает a<b везде, где a.x+a.delta < b.x, и то же самое для y. Необработанная точка — это просто прямоугольник размера 1.

По сути, вам нужен контейнер для самого прямоугольника (не должен перераспределять прямоугольники при изменении, поэтому может работать std::list) и два std::maps (для сопоставления horz и vert), имеющие пары место/размер в качестве ключа и итератор списка (может быть прямоугольным указателем, полученным из &*iter) в качестве значения.

Моя рекомендация была бы контейнером, смутно похожим на:

class region {
    typedef std::vector<vector*> subregion;
    std::array<std::array<subregion, 100>, 100> locations;
    std::vector<rectangle> children;
public:
    std::vector<rectangle>::iterator add(rectangle addme);
    void remove(std::vector<rectangle>::iterator deleteme);
    void move(std::vector<rectangle>::iterator moveme, point to);
    void intersect(std::vector<rectangle>::iterator left, 
                   std::vector<rectangle>::iterator right);
};

Член children — это просто повторяющийся список прямоугольников в контейнере. Каждая подобласть составляет одну сотую от общей области, которая может содержать прямоугольники. При добавлении прямоугольника указатели на него добавляются ко всем подобластям, которых касается прямоугольник. Когда прямоугольник удаляется, его указатели удаляются из всех подобластей, которых касается прямоугольник. Ход фактически представляет собой удаление, обновление прямоугольника, а затем добавление.

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