# 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()
My tech exploits. Nah... closer to a tech diary, and work log, so if I forget something, but know I forgot, I'll maybe be able to look it up here. And as a bonus, perhaps someone out there will find it useful or interesting. As is only fair, being nearly all the information put here was gleaned from elsewhere on the web.
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.
Subscribe to:
Post Comments (Atom)
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?
ReplyDeleteIntersection = Max(left), Min(right), Max(top), Min(bottom) - fail if w/h negative?
ReplyDelete