浮点区间交集

Question

我有两个矩形。我需要检查它们是否重叠，以及重叠的部分在哪里。

方法一： 1) 分别找出每个矩形的范围和域。 2) 使用类似数学公式的计算方法：

x1 < a < x2

我用Python写了这个：

if x1[0] > x2[0] and x1[0] < x2[1] or x1[1] > x2[0] and x1[1] < x2[1]: return True

问题是： 这个方法是用来检测重叠的，它通过比较边界来实现。然而，它假设矩形x1的边界点会在x2里面。如果x1的边界x1[0]和x1[1]比x2的边界x2[0]和x2[1]还要大，那么它会返回false，这就表示没有重叠，但实际上这两个点之间的范围是会相交的。

方法二： 使用set()数据类型及其内置函数：

   def containsRectangle(self,Rectangle):
        x1 = range(self.x_interval[0],self.x_interval[1])
        x2 = range(Rectangle.x_interval[0],Rectangle.x_interval[1])
        set_x1 = set(x1)
        set_x2 = set(x2)
        if set_x1.intersection(x2):
            return True

问题是： 我必须使用浮点数，因为我需要计算的精确度。Python不允许我对浮点数进行迭代。

我现在没有其他想法了，大家有什么建议吗？非常感谢！

Answer 1

其实，你的第二种方法是对的。不过，从某种角度来看，你必须在集合中有明确的值。如果你想要连续的值，那么比较交集的边界就可以了，就像你在第一个例子中做的那样。

既然已经确定两个矩形的交集是一个多边形，你可以使用任何一种判断点是否在多边形内的方法：

def point_inside_polygon(x,y,poly):
    """ Assume poly is the intersection of the two rectangles and (x,y) is the point to check 
    """
    n = len(poly)
    inside =False

    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if x <= max(p1x,p2x):
                    if p1y != p2y:
                        xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x,p1y = p2x,p2y
    return inside