Python Programming
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed ForumsProgramming LanguagesPython Programming

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old January 14th, 2013, 04:27 AM
eliskan eliskan is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Nov 2012
Posts: 43 eliskan User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 1
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

Reply With Quote
  #2  
Old January 14th, 2013, 08:29 AM
b49P23TIvg's Avatar
b49P23TIvg b49P23TIvg is offline
Contributing User
Dev Shed Loyal (3000 - 3499 posts)
 
Join Date: Aug 2011
Posts: 3,389 b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level) 
Time spent in forums: 1 Month 2 Weeks 3 Days 14 h 22 m 25 sec
Reputation Power: 383
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!

Reply With Quote
  #3  
Old January 14th, 2013, 10:54 AM
dwblas dwblas is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: May 2009
Posts: 294 dwblas User rank is Corporal (100 - 500 Reputation Level)dwblas User rank is Corporal (100 - 500 Reputation Level)dwblas User rank is Corporal (100 - 500 Reputation Level)dwblas User rank is Corporal (100 - 500 Reputation Level) 
Time spent in forums: 3 Days 18 h 55 m 54 sec
Reputation Power: 7
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.

Reply With Quote
  #4  
Old January 14th, 2013, 04:22 PM
eliskan eliskan is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Nov 2012
Posts: 43 eliskan User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 1
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)

Reply With Quote
  #5  
Old January 14th, 2013, 08:21 PM
eliskan eliskan is offline
Contributing User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Nov 2012
Posts: 43 eliskan User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 15 h 59 m 28 sec
Reputation Power: 1
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

Reply With Quote
Reply

Viewing: Dev Shed ForumsProgramming LanguagesPython Programming > Rectangle Hit Test

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

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


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap