python - 如何检测矩形中的矩形？

Question

我有一个矩形列表的左上角和右下角的坐标，比如 (a,b) 和 (c,d)。我想检测并删除矩形内的矩形。重叠的矩形可以保留。

我有一个包含 10,000 个矩形的数据集，我想要一种有效的方法来解决这个问题。

目前我是这样做的，

import pandas

data = pd.read_csv('dataset.csv')

l = list(range(len(data)-1))

for i in range(len(data)):
    length = len(l)
    if i >= length:
        break
    for j in range(i+1, length):
        if j >= len(l):
           break
        if (data.iloc[l[i]]['a'] >= data.iloc[l[j]]['a']) and (data.iloc[l[i]]['b'] <= data.iloc[l[j]]['b']) and (data.iloc[l[i]]['c'] <= data.iloc[l[j]]['c']) and (data.iloc[l[i]]['d'] >= data.iloc[l[j]]['d']):
           l.pop(j)

我在按矩形面积的降序对数据集进行排序后实现了此算法，因为面积较大的矩形不适合面积较小的矩形。在这里，我在检测它是否在另一个矩形内后从列表 l 中弹出矩形的索引。每次弹出一个元素时，它都会减少迭代次数。

这需要几个小时才能解决，我需要一种有效的方法来解决它，即使是十万个样本也是如此。

请帮忙!

Answer 1

这是一个您可以尝试的分而治之的小算法。

我假设只要你能快速枚举出每一对碰撞矩形，您还可以检查一个是否完全在常数时间内包含在另一个中。

因此，我们只需找到碰撞的矩形。

首先，概括如下:假设你有两个集合矩形 A和 B ，并且您只想找到对 (a, b)这样的矩形 a来自A , b来自B ,和 a和 b相交。

首先，理念。考虑以下示例两组A和 B部分矩形用水平线分隔 L :

      +----+                    +-----+
      | A1 |                    |  B1 |
      |    |     +-----+        +-----+
      +----+     |  A2 |
                 +-----+     +-----+
                             |  A3 |
_____________________________|_____|________ L
                             |     |
         +-------------------+##+  |
         |                   |##|  |
         |     B2            +##|--+    
         |                      |
         +----------------------+

行L分割集合 A和 B分为三个子集:

A above L: {A1, A2}         (short: A>L)
A intersects L: {A3}        (short: A=L)
A below L: {}               (short: A<L)


B above L: {B1}             (B>L)
B intersects L: {}          (B=L)
B below L: {B2}             (B<L)

观察只有来自以下组的矩形可以碰撞:

         A<L    A=L    A>L
B<L       y      y      N
B=L       y      y      y
B>L       N      y      y

也就是说，如果我们想找到 A 之间的所有碰撞和 B , 一旦我们已经找到合适的线路L ，我们可以忽略之间的碰撞 A<L与 B>L和 A>L与 B<L .因此，我们得到以下分治算法: while A和 B不为空，找到一条合适的线(大致)最大化消除碰撞检查的数量，分割 A和 B每组分成三组，递归进行七个子组碰撞，忽略两个子组组合。

假设如果矩形是“小的”，并且组 A=L和 B=L大部分都是空的，这将(粗略地)在每一步中将集合的大小减半，因此我们获得了一个平均运行类似于 O(n*log(n)) 的算法。而不是 O(n*n) .

一旦你有了任意 A 的一般情况和 B , 取整组矩形 R并使用 A = R; B = R 运行算法.

这是 Python 中的粗略草图:

def isSubinterval(aStart, aEnd, bStart, bEnd):
  return aStart >= bStart and aEnd <= bEnd

def intersects(aStart, aEnd, bStart, bEnd):
  return not (aEnd < bStart or aStart > bEnd)

class Rectangle:
  def __init__(self, l, r, b, t):
    self.left = l
    self.right = r
    self.bottom = b
    self.top = t

  def isSubrectangle(self, other):
    return (
      isSubinterval(self.left, self.right, other.left, other.right) and
      isSubinterval(self.bottom, self.top, other.bottom, other.top)
    )

  def intersects(self, other):
    return (
      intersects(self.left, self.right, other.left, other.right) and
      intersects(self.bottom, self.top, other.bottom, other.top)
    )

  def __repr__(self):
    return ("[%f,%f]x[%f,%f]" % (self.left, self.right, self.bottom, self.top))

def boundingBox(rects):
  infty = float('inf')
  b = infty
  t = - infty
  l = infty
  r = - infty
  for rect in rects:
    b = min(b, rect.bottom)
    l = min(l, rect.left)
    r = max(r, rect.right)
    t = max(t, rect.top)
  return Rectangle(l, r, b, t)

class DividingLine:
  def __init__(self, isHorizontal, position):
    self.isHorizontal = isHorizontal
    self.position = position

  def isAbove(self, rectangle):
    if self.isHorizontal:
      return rectangle.bottom > self.position
    else:
      return rectangle.left > self.position

  def isBelow(self, rectangle):
    if self.isHorizontal:
      return rectangle.top < self.position
    else:
      return rectangle.right < self.position

def enumeratePossibleLines(boundingBox):
  NUM_TRIED_LINES = 5
  for i in range(1, NUM_TRIED_LINES + 1):
    w = boundingBox.right - boundingBox.left
    yield DividingLine(False, boundingBox.left + w / float(NUM_TRIED_LINES + 1) * i)
    h = boundingBox.top - boundingBox.bottom
    yield DividingLine(True, boundingBox.bottom + h / float(NUM_TRIED_LINES + 1) * i)

def findGoodDividingLine(rects_1, rects_2):
  bb = boundingBox(rects_1 + rects_2)
  bestLine = None
  bestGain = 0
  for line in enumeratePossibleLines(bb):
    above_1 = len([r for r in rects_1 if line.isAbove(r)])
    below_1 = len([r for r in rects_1 if line.isBelow(r)])
    above_2 = len([r for r in rects_2 if line.isAbove(r)])
    below_2 = len([r for r in rects_2 if line.isBelow(r)])

    # These groups are separated by the line, no need to 
    # perform all-vs-all collision checks on those groups!
    gain = above_1 * below_2 + above_2 * below_1
    if gain > bestGain:
      bestGain = gain
      bestLine = line
  return bestLine

# Collides all rectangles from list `rects_1` with 
# all rectangles from list `rects_2`, and invokes
# `onCollision(a, b)` on every colliding `a` and `b`.
def collideAllVsAll(rects_1, rects_2, onCollision):
  if rects_1 and rects_2: # if one list empty, no collisions
    line = findGoodDividingLine(rects_1, rects_2)
    if line:
      above_1 = [r for r in rects_1 if line.isAbove(r)]
      below_1 = [r for r in rects_1 if line.isBelow(r)]
      above_2 = [r for r in rects_2 if line.isAbove(r)]
      below_2 = [r for r in rects_2 if line.isBelow(r)]
      intersect_1 = [r for r in rects_1 if not (line.isAbove(r) or line.isBelow(r))]
      intersect_2 = [r for r in rects_2 if not (line.isAbove(r) or line.isBelow(r))]
      collideAllVsAll(above_1, above_2, onCollision)
      collideAllVsAll(above_1, intersect_2, onCollision)
      collideAllVsAll(intersect_1, above_2, onCollision)
      collideAllVsAll(intersect_1, intersect_2, onCollision)
      collideAllVsAll(intersect_1, below_2, onCollision)
      collideAllVsAll(below_1, intersect_2, onCollision)
      collideAllVsAll(below_1, below_2, onCollision)
    else:
      for r1 in rects_1:
        for r2 in rects_2:
          if r1.intersects(r2):
            onCollision(r1, r2)

这是一个小演示:

rects = [
  Rectangle(1,6,9,10),
  Rectangle(4,7,6,10),
  Rectangle(1,5,6,7),
  Rectangle(8,9,8,10),
  Rectangle(6,9,5,7),
  Rectangle(8,9,1,6),
  Rectangle(7,9,2,4),
  Rectangle(2,8,2,3),
  Rectangle(1,3,1,4)
]

def showInterestingCollision(a, b):
  if a is not b:
    if a.left < b.left:
      print("%r <-> %r collision" % (a, b))

collideAllVsAll(rects, rects, showInterestingCollision)

至少在这种情况下，它确实检测到了所有有趣的碰撞:

[1.000000,6.000000]x[9.000000,10.000000] <-> [4.000000,7.000000]x[6.000000,10.000000] collision
[1.000000,5.000000]x[6.000000,7.000000] <-> [4.000000,7.000000]x[6.000000,10.000000] collision
[4.000000,7.000000]x[6.000000,10.000000] <-> [6.000000,9.000000]x[5.000000,7.000000] collision
[6.000000,9.000000]x[5.000000,7.000000] <-> [8.000000,9.000000]x[1.000000,6.000000] collision
[7.000000,9.000000]x[2.000000,4.000000] <-> [8.000000,9.000000]x[1.000000,6.000000] collision
[2.000000,8.000000]x[2.000000,3.000000] <-> [8.000000,9.000000]x[1.000000,6.000000] collision
[2.000000,8.000000]x[2.000000,3.000000] <-> [7.000000,9.000000]x[2.000000,4.000000] collision
[1.000000,3.000000]x[1.000000,4.000000] <-> [2.000000,8.000000]x[2.000000,3.000000] collision

---

这是一个更真实的演示:

from random import random
from matplotlib import pyplot as plt

def randomRect():
  w = random() * 0.1
  h = random() * 0.1
  centerX = random() * (1 - w)
  centerY = random() * (1 - h)
  return Rectangle(
    centerX - w/2, centerX + w/2,
    centerY - h/2, centerY + h/2
  )

randomRects = [randomRect() for _ in range(0, 500)]

for r in randomRects:
  plt.fill(
    [r.left, r.right, r.right, r.left], 
    [r.bottom, r.bottom, r.top, r.top],
    'b-',
    color = 'k',
    fill = False
  )

def markSubrectanglesRed(a, b):
  if a is not b:
    if a.isSubrectangle(b):
      plt.fill(
        [a.left, a.right, a.right, a.left], 
        [a.bottom, a.bottom, a.top, a.top],
        'b-',
        color = 'r',
        alpha = 0.4
      )
      plt.fill(
        [b.left, b.right, b.right, b.left], 
        [b.bottom, b.bottom, b.top, b.top],
        'b-',
        color = 'b',
        fill = False
      )

collideAllVsAll(randomRects, randomRects, markSubrectanglesRed)

plt.show()

该图以红色显示所有消除的矩形，以蓝色显示封闭矩形:

这是一个具有单次碰撞的小示例的准二元空间划分的边界框(黄色)和选择的分界线(青色)的可视化:

对于 10000 个“合理大小”的随机矩形(相交率与图像中大致相同)，它会在 18 秒内计算出所有碰撞，即使代码远未优化。