Эффективный способ найти перекрытие N прямоугольников

Ответ 1

Во-первых: Как и во многих проблемах из вычислительной геометрии, необходимо указать параметры для анализа порядка роста: вызывая длины списков m и n, наихудший случай только в этих параметрах - Ω (m × n), так как все области могут перекрываться (в этом отношении алгоритм из вопроса асимптотически оптимален). Обычно указывается размер вывода: t = f (m, n, o) (чувствительный к выходу алгоритм).
Тривиально, f ∈ Ω (m + n +o) для поставленной задачи.

Line Sweep - это парадигма для уменьшения геометрических задач одним измерением - в его первоначальном виде, от 2D до 1D, от плоскости к линии.

Представьте себе все прямоугольники в плоскости, разные цвета для списков.
Теперь проведите линию по этой плоскости - слева направо, условно и бесконечно дальше вправо "для низких y-координат" (обрабатывайте координаты при увеличении x-порядка, увеличивая y-порядок для равного x).
Для всей этой развертки (или сканирования) для каждого цвета сохраняются один набор, представляющий "y-интервалы" всех прямоугольников в текущей x-координате, начиная пустой. (В структуре данных, поддерживающей вставку, удаление и перечисление всех интервалов, которые перекрывают интервал запроса: см. Ниже.)
Встречая левую часть прямоугольника, добавьте сегмент в структуру данных для его цвета. Отображать перекрывающиеся интервалы/прямоугольники в любом другом цвете.
С правой стороны удалите сегмент.
В зависимости от определения "перекрытия", обрабатывайте левую сторону перед правыми сторонами - или наоборот.

Существует много структур данных, поддерживающих вставку и удаление интервалов, и поиск всех интервалов, которые перекрывают интервал запроса. В настоящее время я думаю, что расширенные поисковые деревья могут быть проще всего понять, реализовать, протестировать, проанализировать...
Используя это, перечисляя все о пересекающихся пар оси выровнен прямоугольников (а, б) из listA и listB должно быть возможным в O (журнал (т + п) (M + N) +o) времени и O (M + N ) пространство. Для значительных экземпляров проблем избегайте структур данных, требующих больше, чем линейного пространства ((оригинальные) сегментные деревья, например, для перекрытия интервалов).

Другая парадигма в дизайне алгоритма - Divide & Conquer: с задачей вычислительной геометрии, выберите одно измерение, в котором проблему можно разделить на независимые части, а координата такая, что подзадачи для "координат ниже" и "координаты выше" близки ожидаемое время выполнения. Вполне возможно, что необходимо решить другую (и другую) подзадачу "включая координату". Это, как правило, выгодно, когда: а) время выполнения решения подсуммов является "супер-логарифмически линейным", и б) существует дешевый (линейный) способ построения общего решения из решений для подзадач,
Это поддается совместному решению проблем и может использоваться с любым другим подходом для подзадач, включая линейную развертку.

Будет много способов настроить каждый подход, начиная с игнорирования входных элементов, которые не могут внести вклад в вывод. Чтобы "честно" сравнивать реализации алгоритмов подобного порядка роста, не стремиться к справедливому "уровню изменчивости": старайтесь инвестировать справедливое количество времени для настройки.

Ответ 2

Несколько возможных незначительных улучшений эффективности. Во-первых, исправьте функцию overlap(), она потенциально не требует вычислений:

def overlap(r1, r2):

    if r1.left > r2.right or r1.right < r2.left:
        return False

    if r1.top < r2.bottom or r1.bottom > r2.top:
        return False

    return True

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

def containing_rectangle(rectangles):
    return Rectangle(min(rectangles, key=lambda r: r.left).left,
        max(rectangles, key=lambda r: r.right).right,
        min(rectangles, key=lambda r: r.bottom).bottom,
        max(rectangles, key=lambda r: r.top).top
    )

c = containing_rectangle(listA)

for b in listB:
    if b.overlap(c):
        for a in listA:
            if b.overlap(a):

В моем тестировании с сотнями случайных прямоугольников это избегало сравнений по порядку отдельных цифр (например, 2% или 3%) и иногда увеличивало количество сравнений. Однако, по-видимому, ваши данные не являются случайными и могут быть лучше с этим типом скрининга.

В зависимости от характера ваших данных вы можете разбить это на проверку прямоугольника контейнера для каждой партии из 10K прямоугольников из 50K или того, что когда-либо среза дает максимальную эффективность. Возможно, предварительно отредактируйте прямоугольники (например, их центрами), прежде чем назначать их партиям контейнеров.

Мы можем разбить и запустить оба списка с прямоугольниками контейнеров:

listAA = [listA[x:x + 10] for x in range(0, len(listA), 10)]

for i, arrays in enumerate(listAA):
    listAA[i] = [containing_rectangle(arrays)] + arrays

listBB = [listB[x:x + 10] for x in range(0, len(listB), 10)]

for i, arrays in enumerate(listBB):
    listBB[i] = [containing_rectangle(arrays)] + arrays

for bb in listBB:
    for aa in listAA:
        if bb[0].overlap(aa[0]):
            for b in bb[1:]:
                if b.overlap(aa[0]):
                    for a in aa[1:]:
                        if b.overlap(a):

С моими случайными данными это уменьшало сравнение порядка 15% до 20%, даже считая сравнения прямоугольников контейнеров. Выделение прямоугольников выше произвольно, и вы, вероятно, сможете сделать лучше.

Ответ 3

Исключение, которое вы получаете, исходит из последней строки кода, который вы показываете. Список выражений list[rect] недопустим, поскольку list является классом, а синтаксис [] в этом контексте пытается его проиндексировать. Вероятно, вы хотите просто [rect] (который создает новый список, содержащий единственный элемент rect).

Есть еще несколько основных проблем с вашим кодом. Например, ваш метод Rect.__init__ не устанавливает left атрибут, который, как вы ожидаете, в методе тестирования столкновений. Вы также использовали разную капитализацию для r1 и r2 в разных частях метода overlap (Python не считает, что r1 будет таким же, как R1).

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

list_of_rects = [rect1, rect2, rect3, rect4] # assume these are defined elsewhere

for a, b in itertools.combinations(list_of_rects, 2):
    if a.overlap(b):
        # do whatever you want to do when two rectangles overlap here

Ответ 4

Очевидно, что если ваш список (по крайней мере listB) отсортирован по r2.xmin, вы можете выполнить поиск r1.xmax в listB и прекратить тестирование перекрытия r1 в этом спискеB (остальное будет направо). Это будет O (n · log (n)).

Сортированный вектор имеет более быстрый доступ, чем отсортированный список.

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

Также исправьте функцию overlap() как объяснил cdlane.

Ответ 5

Эта реализация с использованием numpy примерно в 35-40 раз быстрее в соответствии с тестом, который я сделал. Для 2 списков, каждый из которых содержит 10000 случайных прямоугольников, этот метод занял 2,5 секунды, а метод в вопросе занял ~ 90 секунд. С точки зрения сложности это еще O (N ^ 2), как метод в вопросе.

import numpy as np

rects1=[
    [0,10,0,10],
    [0,100,0,100],
]

rects2=[
    [20,50,20,50],
    [200,500,200,500],
    [0,12,0,12]
]

data=np.asarray(rects2)


def find_overlaps(rect,data):
    data=data[data[::,0]<rect[1]]
    data=data[data[::,1]>rect[0]]
    data=data[data[::,2]<rect[3]]
    data=data[data[::,3]>rect[2]]
    return data


for rect in rects1:
    overlaps = find_overlaps(rect,data)
    for overlap in overlaps:
        pass#do something here

Ответ 6

Если вы знаете верхний и нижний пределы для координат, вы можете сузить поиск, разделив координатное пространство на квадраты, например, 100x100.

• Сделайте один "набор" на квадрат координаты.
• Проходите через все квадраты, помещая их в "набор" любого квадрата, который они перекрывают.

См. Также Tiled Rendering, которая использует разделы для ускорения графических операций.

    // Stores rectangles which overlap (x, y)..(x+w-1, y+h-1)
    public class RectangleSet
    {
       private List<Rectangle> _overlaps;

       public RectangleSet(int x, int y, int w, int h);
    }

    // Partitions the coordinate space into squares
    public class CoordinateArea
    {
       private const int SquareSize = 100;

       public List<RectangleSet> Squares = new List<RectangleSet>();

       public CoordinateArea(int xmin, int ymin, int xmax, int ymax)
       {
          for (int x = xmin; x <= xmax; x += SquareSize)
          for (int y = ymin; y <= ymax; y += SquareSize)
          {
              Squares.Add(new RectangleSet(x, y, SquareSize, SquareSize);
          }
       }

       // Adds a list of rectangles to the coordinate space
       public void AddRectangles(IEnumerable<Rectangle> list)
       {
          foreach (Rectangle r in list)
          {
              foreach (RectangleSet set in Squares)
              {
                  if (r.Overlaps(set))
                      set.Add(r);
              }
          }
       }
    }

Теперь у вас есть намного меньший набор прямоугольников для сравнения, который должен ускорить процесс.

CoordinateArea A = new CoordinateArea(-500, -500, +1000, +1000);
CoordinateArea B = new CoordinateArea(-500, -500, +1000, +1000);  // same limits for A, B

A.AddRectangles(listA);
B.AddRectangles(listB);

for (int i = 0; i < listA.Squares.Count; i++)
{
    RectangleSet setA = A[i];
    RectangleSet setB = B[i];

    // *** small number of rectangles, which you can now check thoroghly for overlaps ***

}

Ответ 7

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

Смотрите также:

• https://en.wikipedia.org/wiki/Spatial_database
• Пространственный индекс для прямоугольников с быстрой вставкой
• найти алгоритм перекрывающихся прямоугольников