Saturday, May 28, 2011

basic rectangle intersection algorithm

I was sifting through LWUIT sourcecode, and came upon a function for determining if 2 rectangular areas intersect at any region. I stared for a painfully long time at the simple task and simple algorithm to figure out why it worked. It works by comparing the lower right and top left point of each rectangle. For there to be an intersection by rectangles r1 and r2, the top left of r1 is inside the quadrant described by the lower right of r2, and vice versa. If either of these is not true, it means r1 lies entirely outside a quadrant described by one of the corners of r2, which means the rectangles do not intersect ie, they are disjoint.
# intersect.py
# check if rectangles intersect
# rectangles defined by
# (tx,ty, tw=width, th=height)
# (x,y, width, height)

def intersects(tx, ty, tw, th, x, y, width, height):
        rw = width
        rh = height

        if (rw <= 0 or rh <= 0 or tw <= 0 or th <= 0): 
            return false
        
        rx = x
        ry = y
        rw += rx
        rh += ry
        tw += tx
        th += ty

        # The first sub-test checks if rw/rh/tw/th overflowed, meaning wrapped around to value < rx/ry/tw/ry
        return ((rw < rx or rw > tx) and
                (rh < ry or rh > ty) and
                (tw < tx or tw > rx) and
                (th < ty or th > ry))

def main():
 print(intersects(1,1,4,5,3,3,1,1))
 print(intersects(3,3,1,1,1,1,4,5))

main()


2 comments:

  1. can I know how do I find out the points of intersection for the intersecting rectangles? I tried doing manually and it seems very time consuming as there are many cases to be considered. Is there a general formula that can get me that?

    ReplyDelete
  2. Intersection = Max(left), Min(right), Max(top), Min(bottom) - fail if w/h negative?

    ReplyDelete