重叠矩形_编程黑洞网

我今天在技术面试中（对于devops / SRE职位）收到以下问题：

编写一个函数，如果将两个矩形作为参数传递给它，则返回true如果在笛卡尔平面上绘制，则会重叠。保证
矩形与轴对齐，而不是任意旋转。

我几乎炸毁了整个思维过程，以解决问题I。我没有考虑过例如一个矩形可能完全被另一个矩形包围的情况，或者一个短而宽的矩形可能完全穿过一个较高，较窄的矩形而形成某种交叉的情况，所以我没有考虑—一个非生产性的正切的思考，一个矩形的任何一个角是否在另一个矩形的边界之内。

我自然一回到家，就让问题在我的脑海中得到了解决，能够写出看起来相当优雅并且似乎可以正常工作的东西（对于到目前为止我已经尝试过的测试用例）。

此图形（花了更长的时间才能完成）比代码创建，而且我什至不知道如何使Inkscape在保存的图像中显示网格线，因为它在我的工作画布中显示）显示了最简单的明显的情况：红色/浅绿色重叠一个角，蓝色完全包围紫红色，绿色/黄色重叠但彼此之间没有任何角落。我的测试代码使用红色/蓝色，蓝色/绿色和类似的组合作为不重叠的测试用例，包括那些仅在水平或垂直维度上重叠但在其他维度上清晰的组合。

我当我回到家并用键盘坐下时的思考过程如下：

最终我们只关心边缘。因此，我的Rect()类仅存储左右边缘的X标量，以及上下边缘的Y标量。

为了使矩形重叠，在水平和垂直方向上都必须有一些重叠。因此，仅测试第一个矩形参数的左边缘或右边缘是在另一个矩形的相对边缘的右还是左（分别）...顶部和底部也是如此就足够了。

这是创建点和矩形的代码。矩形仅使用角点实例化；点实际上是微不足道的，如果我倾斜则可以命名为元组。

#/usr/bin/env python
class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Rect(object):
    def __init__(self, p1, p2):
        '''Store the top, bottom, left and right values for points 
               p1 and p2 are the (corners) in either order
        '''
        self.left   = min(p1.x, p2.x)
        self.right  = max(p1.x, p2.x)
        self.bottom = min(p1.y, p2.y)
        self.top    = max(p1.y, p2.y)

请注意，我将左侧设置为两个x坐标中的最小值，右侧最大化，依此类推。我在这里没有对零面积矩形进行任何错误检查，它们对于该类将是完美有效的，并且可以说，对于相同的碰撞“重叠”功能也可能是有效的。对于我的代码，点和线只是无穷小的“矩形”。（但是，我的测试套件中没有这样的退化案例）。

这是重叠函数：

#/usr/bin/env python 

def overlap(r1,r2):
    '''Overlapping rectangles overlap both horizontally & vertically
    '''
    hoverlaps = True
    voverlaps = True
    if (r1.left > r2.right) or (r1.right < r2.left):
        hoverlaps = False
    if (r1.top < r2.bottom) or (r1.bottom > r2.top):
        voverlaps = False
    return hoverlaps and voverlaps

这似乎可行（对于我所有的测试用例），但对我来说也错了。我最初的尝试是将hoverlaps和voverlaps设为False，然后使用类似于所示的条件有选择地将它们设置为True（但不等式运算符反转了）。

因此，有什么更好的渲染方法？

是的，这是文件末尾的测试套件：

#!/usr/bin/env python
# if __name__ == '__main__':

p1 = Point(1,1)
p2 = Point(3,3)
r1 = Rect(p1,p2)
p3 = Point(2,2)
p4 = Point(4,4)
r2 = Rect(p3,p4)

print "r1 (red),r2 (aqua): Overlap in either direction:"
print overlap(r1,r2)
print overlap(r2,r1)

p5 = Point(3,6)     # overlaps horizontally but not vertically
p6 = Point(12,11)
r3 = Rect(p5,p6)

print "r1 (red),r3 (blue): Should not overlap, either way:"
print overlap(r1,r3)
print overlap(r3,r1)

print "r2 (aqua),r3 (blue: Same as that"
print overlap(r2,r3)
print overlap(r3,r2)

p7 = Point(7,7)
p8 = Point(11,10)
r4 = Rect(p7,p8)    # completely inside r3

print "r4 (fuschia) is totally enclosed in r3 (blue)"
print overlap(r3,r4)
print overlap(r4,r3)

print "r4 (fuschia) is nowhere near r1 (red) nor r2 (aqua)"
print overlap(r1,r4)

p09 = Point(13,11)
p10 = Point(19,13)
r5  = Rect(p09,p10)

p11 = Point(13,9)
p12 = Point(15,14)
r6  = Rect(p11,p12)

print "r5 (green) and r6 (yellow) cross without corner overlap"
print overlap(r5,r6)
print overlap(r6,r5)

顺便说一句，请原谅这张令人毛骨悚然的业余图片。我不是图形专家，不得不去Inkscape甚至在这里处理这种可悲的事情。

问题在于显式约束，即矩形将沿轴对齐。

顺便说一句，如果不是这样的话，矩形就不被约束为与轴对齐，那么我怀疑最明显的方法是一系列测试，求解每个（多边形）的每个顶点以找到被另一个包围的顶点（一系列，然后使每个线段彼此相对（任何交点均重叠）。第一个测试是针对一个完全包围另一个且所有测试都是线性/代数方程的解的情况。推广到所有平面多边形。

#1 楼

您有通用的代码，此外还有其他应用程序，因此您不应该将其引入函数中吗？然后，可以将overlap简化为

 def overlap(r1, r2):
    '''Overlapping rectangles overlap both horizontally & vertically
    '''
    return range_overlap(r1.left, r1.right, r2.left, r2.right) and range_overlap(r1.bottom, r1.top, r2.bottom, r2.top)

现在，range_overlap封装的关键条件是两个范围都不完全大于另一个范围。直接表达这种表达方式的方法是

 def range_overlap(a_min, a_max, b_min, b_max):
    '''Neither range is completely greater than the other
    '''
    overlapping = True
    if (a_min > b_max) or (a_max < b_min):
        overlapping = False
    return overlapping

我宁愿使用not而不是if-else分配。我还要重新排列第二个条件以更清楚地显示对称性：

def range_overlap(a_min, a_max, b_min, b_max):
    '''Neither range is completely greater than the other
    '''
    return not ((a_min > b_max) or (b_min > a_max))

当然，德摩根定律允许重写为

def range_overlap(a_min, a_max, b_min, b_max):
    '''Neither range is completely greater than the other
    '''
    return (a_min <= b_max) and (b_min <= a_max)

我认为其中的最后一个是最透明的，但这是一个美学问题，您可能会不同意。

请注意，我在整个过程中都假设，矩形是封闭的（即它们包含其边缘）。要打开它们，请将>更改为>=，将<=更改为<。

\ $ \ begingroup \ $
实际运用de Morgan的法则是获得这一赏金的决定性因素。（尽管链接和正确的拼写也很好）。我真的应该记得在尝试解开代码中更复杂的布尔表达式时要考虑的那些。
\ $ \ endgroup \ $
–吉姆·丹尼斯（Jim Dennis）
2013年9月26日10:32

\ $ \ begingroup \ $
@JimDennis，我不确定您对我的拼写有什么投诉。不过，链接上的公平点是：我不应该假设每个人都已经研究了形式逻辑。
\ $ \ endgroup \ $
– Peter Taylor
2013年9月26日上午11:12

\ $ \ begingroup \ $
与其说是真正的抱怨，不如说是挑逗的顽皮。我可能会发誓，您在“ de Morgan”中遗漏了“ de”。
\ $ \ endgroup \ $
–吉姆·丹尼斯（Jim Dennis）
2013年9月26日上午11:21

\ $ \ begingroup \ $
好的答案，但是此解决方案的一个问题是，很容易混淆range_overlap的参数（是amin，amax，bmin，bmax还是amin，bmin，amax，bmax或...？）
\ $ \ endgroup \ $
–mkrieger1
18年2月1日在11:32

#2 楼

我只是简单地应用逻辑转换。这是您原来的逐字记录：

def overlap(r1,r2):
    '''Overlapping rectangles overlap both horizontally & vertically
    '''
    hoverlaps = True
    voverlaps = True
    if (r1.left > r2.right) or (r1.right < r2.left):
        hoverlaps = False
    if (r1.top < r2.bottom) or (r1.bottom > r2.top):
        voverlaps = False
    return hoverlaps and voverlaps

除非将每个变量设置为False，否则每个变量都为True，因此可以对每个条件取反。

def overlap(r1,r2):
    hoverlaps = not((r1.left > r2.right) or (r1.right < r2.left))
    voverlaps = not((r1.top < r2.bottom) or (r1.bottom > r2.top))
    return hoverlaps and voverlaps

应用戴摩根定律…

def overlap(r1,r2):
    hoverlaps = not(r1.left > r2.right) and not(r1.right < r2.left)
    voverlaps = not(r1.top < r2.bottom) and not(r1.bottom > r2.top)
    return hoverlaps and voverlaps

可以通过逆转不等式来消除“不”。

def overlap(r1,r2):
    hoverlaps = (r1.left <= r2.right) and (r1.right >= r2.left)
    voverlaps = (r1.top >= r2.bottom) and (r1.bottom <= r2.top)
    return hoverlaps and voverlaps

就个人而言，我宁愿重新排列不等式的并行性。另外，我会将函数移到Rect类中。最终答案：

class Rect(object):
    def __init__(p1, p2):
        ...

    @staticmethod
    def overlap(r1, r2):
        '''Overlapping rectangles overlap both horizontally & vertically
        '''
        h_overlaps = (r1.left <= r2.right) and (r1.right >= r2.left)
        v_overlaps = (r1.bottom <= r2.top) and (r1.top >= r2.bottom)
        return h_overlaps and v_overlaps

我不愿意做更多的事情，因为我认为您会遇到收益递减的情况。

#3 楼

我只是玩了一点。解决方案在底部，但是我将展示我采取的步骤。

通过视觉确定两个矩形是否重叠。

对于重叠的矩形：

#1st rectangle
#  (x1,y1)
#  (x2,y2)
#x1,y1 < x2,y2

#2nd rectangle
#  (x3,y3)
#  (x4,y4)
#x3,y3 <x4y4

def rectangleOverlap():
  x1=2
  y1=3
  x2=111
  y2=99
  x3=41
  y3=1
  x4=90
  y4=121
#find largest x (X) and largest y (Y)
  if y4>y2:
    Y=y4
  else:
    Y=y2
  if x4>x2:
    X=x4
  else:
    X=x2
  pic = makeEmptyPicture (X,Y)
  for y in range (0,Y-1):
    for x in range (0,X-1):
      px = getPixel(pic, x,y)

      if (y>y1 and y<y2) and (x>x1 and x<x2):
        setColor(px,makeColor(255,255,0))
      if (y>y3 and y<y4) and (x>x3 and x<x4):
        setColor(px,makeColor(0,255,255))  
      if (y>y1 and y<y2) and (x>x1 and x<x2)  and (y>y3 and y<y4) and (x>x3 and x<x4):
        setColor(px,makeColor(255,0,0))

  show(pic)

重叠部分显然可以在这里看到红色。

对于矩形不要重叠：

def rectangleOverlap():
  x1=2
  y1=3
  x2=11
  y2=9
  x3=41
  y3=11
  x4=90
  y4=121
#find largest x (X) and largest y (Y)
  if y4>y2:
    Y=y4
  else:
    Y=y2
  if x4>x2:
    X=x4
  else:
    X=x2
  pic = makeEmptyPicture (X,Y)
  for y in range (0,Y-1):
    for x in range (0,X-1):
      px = getPixel(pic, x,y)
      if (y>y1 and y<y2) and (x>x1 and x<x2):
        setColor(px,makeColor(255,255,0))
      if (y>y3 and y<y4) and (x>x3 and x<x4):
        setColor(px,makeColor(0,255,255))  
      if (y>y1 and y<y2) and (x>x1 and x<x2)  and (y>y3 and y<y4) and (x>x3 and x<x4):
        setColor(px,makeColor(255,0,0))

   show(pic)

所以，如果我们关注重叠的部分：

if (y>y1 and y<y2) and (x>x1 and x<x2)  and (y>y3 and y<y4) and (x>x3 and x<x4):

缩小范围以优化代码。

def rectangleOverlap():

  for y in range (y1,y2):
    for x in range (x1,x2):

      if (y>y3 and y<y4) and (x>x3 and x<x4):
        print "overlap"
        return true

我不是专家，我喜欢python的这一方面。希望对您有帮助

\ $ \ begingroup \ $
Aaaargh！ JPEG！
\ $ \ endgroup \ $
–加雷斯·里斯（Gareth Rees）
2013年12月9日17:50

编程黑洞网

重叠矩形

评论

#1 楼

评论

#2 楼

#3 楼

评论