我有一组坐标，它们形成轴对齐的二维框（轴向/等向矩形，rects）。
我想知道有多少个盒子相互交错，而不会重复计数。例如，我有A、B和C三个盒子。如果A与B相交，B与A相交仍然只算作一个交叉而不是两个。
我的思路是挑出一个盒子，与其余所有盒子进行比较，然后将其舍弃，因为比较已经完成，我不想重复。例如，回到A、B和C，如果我正在处理A并且它与B相交但不与C相交，那么我已经完成了A的比较，因此就不需要在循环中保留它。 因此，一旦我开始处理B，它就不会重新检查A。
我想不出更快的方法。这类似于使用线性搜索查找重复项，我认为最坏情况下的复杂度将是O(n^2)。我不知道如何使用二分搜索，因为可能会有多个交点。我还看了排序算法，但我需要一个不会再次回溯检查旧值的算法。
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)时间复杂度的数据结构是使用两个平衡二叉搜索树：一个保存区间起始点，另一个保存区间终点。您还需要增强每个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)
这是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(n2)参考实现进行比较，显示交点数量和运行时间：
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()
你可以在一定程度上减少平均复杂度，更准确地说是计算时间，但最坏情况下仍然会得到一个 n² 的复杂度... 因为本质上这是一个 O(n²) 的算法，因为你必须逐个测试每个 N 个盒子。
减少计算时间的一种方法是“附加”每个盒子的外接球。这很容易计算：它的中心是盒子/矩形的8个顶点的重心，其半径是从该重心到一个顶点的任意距离。
诀窍是：给定两个盒子，如果它们的外接球不相交（两个中心之间的距离大于两个半径之和），则这两个盒子就不可能相交。 如果两个球相交，则这两个盒子可能相交。
这个技巧并没有改变复杂度，但它大大减少了计算时间，因为测试球体比测试盒子要快得多（特别是如果它们不平行于轴线...）。它还将减少列表大小，直到对任何潜在交点都为空。此外，每个盒子也只有一个缩短的（甚至是空的）潜在交点列表。
您可以通过使用盒子对列表进行精细测试、使用距离平方进行比较等方式来节省一些计算时间：虽然不是很多，但最终仍然可以节省一些时间。然后，您可以使用更少的盒子对计算实际的盒子交集。
这将显著提高与轴不对齐的许多3D随机盒子的性能，并且与轴对齐的少数2D矩形的性能则不会。在两种情况下，您始终会面临O(n²)的复杂度（即最坏情况）。