唯一报告轴对齐矩形列表中的交叉点

Question

我有一个坐标列表，这些坐标形成轴对齐的二维框（axis-oriented/iso-oriented 矩形，rects）。
我想看看有多少个盒子相互交叉而不重复。例如，我有盒子 A、B 和 C。如果 A 与 B 相交，B 与 A 相交仍将算作 one 交集，而不是 two 分开的。

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

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

Answer 1

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

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

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

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

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

这将是一个显着的提升，因为很多 3D 随机框未与轴对齐，而且很少有 2D 矩形与轴对齐。在这两种情况下，您总是会遇到 O(n²) 复杂性（即最坏的情况）。

Answer 2

您可以在 O(n log n) 中解决这个问题。由于您正在尝试解决二维的 static 交叉问题，因此一个常见的技巧是将问题转换为 dynamic 交叉问题维度（即，一个 space 维度成为时间维度）。

假设您有一个左下角 (x1, y1) 和右上角 (x2, y2) 的闭合矩形。这个矩形变成了两个“间隔事件”：

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

以这种方式将所有矩形转换为事件，然后按时间排序（打破与删除之前的插入）。

现在，您需要一个数据结构，可以让您添加和删除间隔 [A, B]，还可以查询数据结构中与 [A, B] 相交的间隔数。然后按排序顺序处理“间隔事件”，但在插入每个间隔 [A, B].

之前保留运行当前间隔与 [A, B] 相交的总和

在每个操作 O(log n) 时间内执行此操作的一个数据结构是使用两个 balanced binary search trees: one holding beginning-points of intervals, and the other holding ending-points of intervals. You'll also need to augment each BST to be an Order Statistic Tree，以快速查询树中小于或等于特定值的点数。

然后，找出当前数据结构中有多少区间与任意区间相交 [A, B] 很简单；该计数是：

#(Intervals intersecting [A, B]) =

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

您可以根据两个相交区间的定义来检查它是否正确：两个区间都在另一个区间结束后开始。

您还可以将订单统计树替换为 prefix-sums 的数据结构，例如 Fenwick tree，对于相同的复杂性，它需要更少的代码。

Answer 3

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

针对 O(n²) 参考实现对 5,000 个随机矩形的列表进行测试，显示交叉点数和运行时间：

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()

唯一报告轴对齐矩形列表中的交叉点

uniquely reporting intersections in a list of axis-aligned rectangles

algorithm

sorting

search

computational-geometry

intersection