在轴对准矩形列表中的独特报告相交

Question

我有一个形成轴为-2D框的坐标列表（面向/面向ISO的矩形， rect s）。
我想看看有多少个盒子彼此相交而不重复。例如，我有盒子A，B和C。如果A与B相交，则B与A相交的相交仍将计算为一个交叉点，而不是 两个单独的。

我想的是抓住一个盒子，将其与所有盒子进行比较，然后将其扔掉，因为进行了比较，我不想重复。例如，回到A，B和C。如果我在A上，并且它与B相交，而不是CI进行了回合，因此不需要将其保持在循环中。因此，一旦我在B上，它就不会重新检查A。

我想不出更快的方法。这类似于使用线性搜索查找重复项，我认为最差的复杂性将为O（n^2）。我看不到如何使用二进制搜索，因为可能有多个交叉点。我也一直在研究排序算法，但是我需要一个不会返回并再次检查旧值的算法。

Answer 1

您可以在o（n log n）中解决此问题。由于您正在尝试在二维中解决 static 相交问题，因此一个常见的窍门是将问题转换为一个维度中的A dynamic 相交问题（即一个空间，一个空间维度变为时间维度）。

假设您有一个封闭的矩形，左下角（x1，y1）和右上角（x2，y2）。该矩形变成两个“间隔事件”：

Interval [y1, y2] inserted at time x1
Interval [y1, y2] removed after time x2

以这种方式将所有矩形转换为事件，然后按时间进行分类（与插入之前插入之前打破纽带）。

现在，您需要一个数据结构，使您可以添加和删除Intervals [a，b]，并且还查询数据结构中的间隔数量相交[a，b]。然后，您按顺序处理“间隔事件”，但请在插入每个间隔[a，b] 。

一个数据结构在o（log n）每次操作的时间是两个平衡的二进制搜索树：一个保持间隔的开始点，另一个保持间隔的结尾点。您还需要增加每个bst为订购统计树，以快速查询点小于或等于树上的某个值。

然后，找到当前数据结构中的几个间隔相交一个任意间隔[a，b]很简单；该计数是：

#(Intervals intersecting [A, B]) =

  #(values in the beginning-points tree that are <= B) 
- #(values in the ending-points tree that are < A)

您可以从两个间隔的定义相交的定义中正确检查：两个间隔都在另一个间隔结束后开始。

您还可以用前缀-SUMS的数据结构替换订单统计树，例如，对于相同的复杂性，需要更少的代码。

Answer 2

KCSquared算法的示例实现。您没有指定语言，所以我选择了Python，因为我熟悉它，并且是简短的可读代码。矩形的左下坐标（x，y）和右上坐标（x，y）。

def intersections(rects):
    events = []
    for A in rects:
        events.append((A.x, 'insert', A.y, A.Y))
        events.append((A.X, 'remove', A.y, A.Y))
    intersections = 0
    ys = SortedList()
    Ys = SortedList()
    for x, op, y, Y in sorted(events):
        if op == 'insert':
            intersections += ys.bisect_right(Y) - Ys.bisect_left(y)
            ys.add(y)
            Ys.add(Y)
        else:
            ys.remove(y)
            Ys.remove(Y)
    return intersections

对5,000个随机矩形列表的测试，针对O（n ² ）参考实现，显示了相交和运行时间的数量：

124257  5465 ms  reference
124257   127 ms  intersections

121166  5444 ms  reference
121166   124 ms  intersections

118980  5435 ms  reference
118980   124 ms  intersections

带有10,000个矩形：

489617  22342 ms  reference
489617    292 ms  intersections

489346  22491 ms  reference
489346    296 ms  intersections

489990  22302 ms  reference
489990    290 ms  intersections

完整代码：

def reference(rects):
    intersections = 0
    for A, B in combinations(rects, 2):
        if A.X >= B.x and A.x <= B.X and A.Y >= B.y and A.y <= B.Y:
            intersections += 1
    return intersections

def intersections(rects):
    events = []
    for A in rects:
        events.append((A.x, 'insert', A.y, A.Y))
        events.append((A.X, 'remove', A.y, A.Y))
    intersections = 0
    ys = SortedList()
    Ys = SortedList()
    for x, op, y, Y in sorted(events):
        if op == 'insert':
            intersections += ys.bisect_right(Y) - Ys.bisect_left(y)
            ys.add(y)
            Ys.add(Y)
        else:
            ys.remove(y)
            Ys.remove(Y)
    return intersections

from random import randint, randrange
from itertools import combinations
from timeit import default_timer as timer
from sortedcontainers import SortedList
from collections import namedtuple

Rect = namedtuple('Rect', 'x X y Y')

for _ in range(3):
    rects = [Rect(x, x + randint(1, 100), y, y + randint(1, 100))
             for _ in range(5000)
             for x, y in [(randrange(1000), randrange(1000))]]
    for func in reference, intersections:
        t0 = timer()
        result = func(rects)
        t1 = timer()
        print(result, '%4d ms' % ((t1 - t0) * 1e3), func.__name__)
    print()

Answer 3

您可以稍微降低平均复杂度，更准确地说是减少计算时间，但您总是会在n²中得到最坏的情况...因为，本质上，这是一个 O(n²) 算法，因为您必须每 N 个盒子测试两个乘两个盒子。

减少计算时间的一种方法是将其外接球体“附加”到每个盒子。计算起来非常简单：它的中心是长方体的 8 个顶点/矩形的 4 个顶点的重心，其半径是从该重心到一个顶点的任意距离。

诀窍是：给定两个盒子，如果它们的外接球体不相交（两个中心之间的距离大于两个半径之和），那么这些盒子不强>相交。
如果两个球体相交，那么盒子可能相交。

这个技巧并没有改变所有的复杂性，但它减少了很多计算时间，因为测试球体比测试盒子要快得多（特别是如果它们不平行于轴......）。并且它将减少列表大小，直至清空任何潜在的交叉点。此外，您还只有每个框的潜在交叉点的缩短（甚至是空）列表。

您可以通过使用框对列表进行精细测试、使用距离平方进行比较等来获得一些计算时间：虽然不是很多，但最终还是节省了一些时间。
然后，您可以用更少的框对来计算真实的框交叉点。

对于大量未与轴对齐的 3D 随机框，这将是一个显着的提升，并且对于少数与轴对齐的 2D 矩形来说，这将是一个显着的提升。在这两种情况下，您将始终处于 O(n²) 复杂度（即最坏的情况）。