Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
January 14th, 2013, 05:27 AM
 eliskan
Contributing User

Join Date: Nov 2012
Posts: 43
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 2
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 1-4, 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=ox1-ox2
dify=oy1-oy2
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

#2
January 14th, 2013, 09:29 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,214
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 7 m 36 sec
Reputation Power: 455
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))
return Vector(a+b for (a,b,) in zip(A,B,))
def __sub__(A,B):
return Vector(a-b 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.center-self.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!

#3
January 14th, 2013, 11:54 AM
 dwblas
Contributing User

Join Date: May 2009
Posts: 421
Time spent in forums: 5 Days 7 h 39 m 51 sec
Reputation Power: 32
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.

#4
January 14th, 2013, 05:22 PM
 eliskan
Contributing User

Join Date: Nov 2012
Posts: 43
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 2
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)

#5
January 14th, 2013, 09:21 PM
 eliskan
Contributing User

Join Date: Nov 2012
Posts: 43
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 2
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:
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=ox1-ox2
dify=oy1-oy2
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```

 Viewing: Dev Shed Forums > Programming Languages > Python Programming > Rectangle Hit Test