January 14th, 2013, 05:27 AM

Rectangle Hit Test
I have been working on this problem for over an hour now and I have to say I am stumped. I have a few IDEAS on how to solve it but surely nothing very efficient.
My problem is I have two rectangular objects and I want a function that can tell if they're hitting eachother, and return which side object1 is being hit from.
I wrote a function that works wonderfully with perfect squares, but it has a problem when I try to use rectangles (because it bases its hit test off the centers of the squares, not the actual perimiters).
The function uses locations x and y, and size x and y, for two objects. It returns 14, depending on which side it gets hit. It can already detect if it's hitting a rectangle, but because of the way it functions it's really unable to return the required output of which SIDE the first object is being hit by..
Please forgive the whitespace, Pythonista (the iPad app I'm writing this in) uses the true tab not just 4 spaces..
Code:
def hitTest2(loc1,size1,loc2,size2,output=0):
if loc1.x+size1.x>=loc2.x and loc1.x<=loc2.x+size2.x:
if loc1.y+size1.y>=loc2.y and loc1.y<=loc2.y+size2.y:
output=1
if output:
#Calculate origins/centers
ox1=loc1.x+size1.x/2
oy1=loc1.y+size1.y/2
ox2=loc2.x+size2.x/2
oy2=loc2.y+size2.y/2
#Difference between origins to locate the direction
difx=ox1ox2
dify=oy1oy2
if difx<=0: output1=1#hit from r
else: output1=2#hit from l
if dify<=0: output2=1#hit from t
else: output2=2#hit from b
#check which is most important
if dify<0:dify*=1
if difx<0:difx*=1
if difx>dify: output=output1
else: output=output2+2
return output
What I need help on, is how to detect which side object1 gets hit, even if one or both objects are rectangular?
This is really a geometry problem and while I love geometry this one is making my brain hurt.. Any help would be GREATLY appreciated.
edit: I doubt it will help (since this code only will work on Pythonista app for iPad), but here is the game code I am using this in. The function in question is hitTest2: https://gist.github.com/278158f70872b37f70df
January 14th, 2013, 09:29 AM

Maybe you can figure out from the coordinates_of_overlap list which edges "hit".
Code:
'''
Please draw the rectangles to convince
yourself that the assertions are true.
'''
import numbers
class Vector(list):
def __str__(self):
return 'Vector(%s)'%(list.__str__(self))
def __add__(A,B):
return Vector(a+b for (a,b,) in zip(A,B,))
def __sub__(A,B):
return Vector(ab for (a,b,) in zip(A,B,))
def __mul__(A,B):
if isinstance(B,numbers.Number):
return Vector(a*B for a in A)
try:
return Vector(a*b for (a,b,) in zip(A,B,))
except:
raise TypeError('Cannot multiply Vector by %s'%(B.__class__.__name__))
class Rectangle:
def __init__(self,center,size,**kwargs):
self.center = center
self.size = size
self.__dict__.update(kwargs)
def min(self):
return Vector(self.centerself.size*0.5)
def max(self):
return Vector(self.center+self.size*0.5)
def __repr__(self):
return 'Rectangle(center=%s,size=%s)'%(self.center,self.size)
def __str__(self):
if hasattr(self,'name'):
return str(self.name)
return __repr__(self)
def V(*args):
return Vector(args)
def overlap(A,B): # written for generalized hyperrectangle
return all(coordinates_of_overlap(A,B))
def coordinates_of_overlap(A,B): # written for generalized hyperrectangle
An = A.min()
Ax = A.max()
Bn = B.min()
Bx = B.max()
return list(max(An[i],Bn[i]) <= min(Ax[i],Bx[i]) for i in range(len(An)))
R = Rectangle
A = R(V(0,0.0),V(1.1,2))
B = R(V(1,0.9),V(1.1,2))
C = R(V(7,1.0),V(1.1,2))
D = R(V(0,0.0),V(1.1,2)*0.1,name='enclosed by A')
assert overlap(A,A)
assert overlap(A,B)
assert not overlap(A,C)
assert overlap(A,D)
assert [False, True] == coordinates_of_overlap(A,C)
[code]
Code tags[/code] are essential for python code and Makefiles!
January 14th, 2013, 11:54 AM

The statements "if difx<=0: output1=1#hit from r" etc. calculate a hit but which side would come from the relationship of loc1.x to loc2.x and loc1.y to loc2.y, or the ox1=loc1.x+size1.x/2 calcs depending on which area of the rectangle you want to use (< or >) unless I am missing something.
Last edited by dwblas; January 14th, 2013 at 12:05 PM.
January 14th, 2013, 05:22 PM

Thank you both for the replies.
@b49P23TIvg  That is an interesting solution and I am going to play with it in Pythonista and see if it works. However I am wondering if a simpler more elegant function is possible, like something which can run inside of a single function? I have to admit your coding style is too advanced for me to understand >.<
@dwblas  When working with squares the function works wonderfully but when working with rectangles, it reacts like this:
Where, if the square hits the rectangle on the long sides of the rectangle it thinks it's hitting it from a different side.
I agree that a simple solution by checking loc1.x to loc2.x might work but the problem is knowing which side is more important, without comparing the differences between the two origins of the boxes.
I will play around with b49P23TIvg's script and see if I can get it to work in my Pythonista game. Thanks again for the input guys and more feedback is very welcome.
edit: Inspired a bit by b4's post I am going to mess around with a simplified version of that which checks the corners of the object. If two of the corners are inside the other box we know it's being hit from that side. If I wanted to prevent overlapping two objects I could always give the objects a slightly boosted size so the hitTest occurs immediately before collision.
The only problem with this is corners, and it mainly applies to a very large box hitting a very small box, but I plan on using it in reverse so the accuracy should be favorable for my uses; I want to use the large rectangular objects for the layouts of levels in the game.. I will post the code once I write it (lol the concept's on paper untested right now)
January 14th, 2013, 09:21 PM

I have solved the problem. The code could still use simplification but the essential requirement works 100% to my satisfaction. If the object it's checking isn't a square, it uses the new calculation which is based on checking two corners of the first box to see if they hit the second box.
If it doesn't return anything, or if it's a box, it continues to the old 'box vs box' calculation.
Code:
def hitCorner(loc1,loc2,size2):
if loc1.x>loc2.x and loc1.x<loc2.x+size2.x:
if loc1.y>loc2.y and loc1.y<loc2.y+size2.y:
return True
def hitTest2(loc1,size1,loc2,size2,output=0):
if loc1.x+size1.x>=loc2.x and loc1.x<=loc2.x+size2.x:
if loc1.y+size1.y>=loc2.y and loc1.y<=loc2.y+size2.y:
output=1
if output:
#Rectangle alert
if size2.x!=size2.y:
c1=hitCorner(loc1,loc2,size2)
c2=hitCorner(Point(loc1.x,loc1.y+size1.y),loc2,size2)
c3=hitCorner(Point(loc1.x+size1.x,loc1.y+size1.y),loc2,size2)
c4=hitCorner(Point(loc1.x+size1.x,loc1.y),loc2,size2)
if c1 and c2: return 2#l
elif c2 and c3: return 3#t
elif c3 and c4: return 1#r
elif c4 and c1: return 4#b
#Calculate origins
ox1=loc1.x+size1.x/2
oy1=loc1.y+size1.y/2
ox2=loc2.x+size2.x/2
oy2=loc2.y+size2.y/2
#Difference between origins to locate the direction
difx=ox1ox2
dify=oy1oy2
if difx<=0: output1=1#hit from r
else: output1=2#hit from l
if dify<=0: output2=1#hit from t
else: output2=2#hit from b
#check which is most important
if dify<0:dify*=1
if difx<0:difx*=1
if difx>dify: output=output1
else: output=output2+2
#output=output2+2
return output