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

Question

У меня есть список прямоугольников, и мне нужно создать список прямоугольников, которые пересекаются.
Прямоугольники определяются с помощью

• Точка
• Размер
• Boolean, может ли прямоугольник двигаться
• Boolean ли прямоугольник может быть удален

Нет прямоугольниками не может быть перемещен, но не может быть удален

Пересечение определено usin г

• Указатель на первый прямоугольник
• Указатель на второй прямоугольник
• Список точек первого прямоугольника, которые находятся во втором
• Список точек второго прямоугольника, которые находятся в первом

Мне нужен контейнер для этого, так как прямоугольники можно добавлять, удалять или перемещать. Операции, которые мне нужны:

1. Вставка прямоугольника
2. Вытащите прямоугольника (возможно только для тех, кто отмечен для него)
3. Изменение положения прямоугольника (не размер, возможно только с теми, кто помечаются для it)
4. Создание набора пересечений.

Как я могу реализовать такой контейнер? Я могу сделать это легко, используя метод перекрестной проверки, но это будет далеко не оптимизировано.
Я думал о сохранении карты прямоугольника -> пересечения, а затем всякий раз, когда добавляется прямоугольник, проверяйте, пересекается ли что-либо и добавляет пересечение к карте, а когда оно удалено, удалите ключ с карты, но я не знаю как проверить, пересекает ли он что-либо быстро, или как перемещать прямоугольники без удаления и повторного ввода.
Я могу использовать C++ 11.

Answer 1

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

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

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

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

Answer 2

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

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 член просто повторяющийся список прямоугольников в контейнере. Каждая подобласть составляет одну одну стоту от общей области, которая может содержать прямоугольники. Когда добавляется прямоугольник, указатели на него добавляются к всем субрегионам, к которым прикасается прямоугольник. Когда прямоугольник удален, его указатели удаляются из всех субрегионов, к которым касается прямоугольник. Первым шагом является удаление, обновление прямоугольника, затем добавление.

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