#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    43
    Rep 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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,850
    Rep Power
    481
    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(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 and Makefiles!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    484
    Rep Power
    33
    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 11:05 AM.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    43
    Rep 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)
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2012
    Posts
    43
    Rep 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:
    		#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=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

IMN logo majestic logo threadwatch logo seochat tools logo