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

Question

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

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

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

Пересечение определяется с помощью

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

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

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

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

Answer 1

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

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

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

По сути, вам нужен контейнер для самих прямоугольников (не должен перераспределять прямоугольники при изменении, следовательно, может работать std :: list) и две std :: maps (для отображения horz и vert), имеющие пары place / size в качестве ключа и итератор списка (может быть указателем в виде прямоугольника, полученного из &*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 - это просто итеративный список прямоугольников в контейнере. Каждый субрегион составляет одну сотую часть всего региона, который может содержать прямоугольники. При добавлении прямоугольника указатели на него добавляются к всем подобластям, к которым соприкасается прямоугольник. Когда прямоугольник удаляется, его указатели удаляются из всех подобластей, к которым соприкасается прямоугольник. Движение - это удаление, обновление прямоугольника, а затем добавление.

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