为什么我的代码没有删除内部矩形

Question

请检查这段代码，看看@Arun R在如何计算覆盖另一个矩形的矩形面积中所说的算法有什么问题

为什么它没有删除其他内部的矩形

cdef class Ray:
    cdef public:
        Point2D p
        Point2D q
        list points

cdef class Boundbox:
    cdef public:
        Point2D minP
        Point2D maxP
        int componentID

        int getComponentID(self):
            return self.componentID
def __numeric_compare_by_x(self,Boundbox a,Boundbox b):
    cdef Point2D tempA,tempB
    tempA=a.minP
    tempB=b.minP
    return tempA.x-tempB.x

def __numeric_compare_by_y(self,Boundbox a,Boundbox b):
    cdef Point2D tempA,tempB
    tempA=a.minP
    tempB=b.minP
    return tempA.y-tempB.y

def isBoundbox_inside(self,b1,b2):
    if((b1.minP.x<=b2.minP.x and b1.minP.y<=b2.minP.y)and(b1.maxP.x>=b2.maxP.x and b1.maxP.y>=b2.maxP.y)):
        return True
    return False

def boundboxFilter(self,boundbox):

    cdef:
        int i
        int minx,miny,maxx,maxy
        list pointList=[]
        Boundbox p,b1,b2

    #for i in xrange(len(boundbox)):
    #    pointList.append(boundbox[i])

    pointList=boundbox
    pointList.sort(cmp=self.__numeric_compare_by_x)

    stack=[]
    stack.append(pointList[0])

    for p in pointList[1:]:
        top=len(stack)-1
        b1=stack[top]
        b2=p
        if(not(self.isBoundbox_inside(b1,b2))):
            stack.append(b2)

    pointList=stack
    pointList.sort(cmp=self.__numeric_compare_by_y)

    stack=[]
    stack.append(pointList[0])
    for p in pointList[1:]:
        top=len(stack)-1
        b1=stack[top]
        b2=p
        if(not(self.isBoundbox_inside(b1,b2))):
            stack.append(b2)

    return stack

Answer 1

问题出在你的过滤逻辑上。

outsiders = []
for rect in pointList:
    if not any(is_inside(rect, box) for box in pointlist if box is not rect):
        outsiders.append(rect)

其中，如果矩形在盒子内，则is_inside为真。您需要对照所有其他矩形检查每个矩形，如果它不在其中任何一个矩形中，请保存它。当然，您可以调整它以提高性能。

另一种需要较少比较的方法是考虑整个列表，删除其他列表中的矩形。但是你必须非常小心索引，把东西放在列表中间也很昂贵。