Re: Collision of rotated rectangles without pygame
On 12/5/2010 2:49 PM, Martin Manns wrote: Hello, I am looking for a Python library for 2D collision checks of rotated rectangles. Currently, I have found vizier 0.5b that is based on pygame. Since I do not want to add a pygame dependency to my app, I replaced the pygame.rect.Rect by a wxPython wx.Rect (see code below). However, collision checks do not work correctly, i. e. identical rects are not found to be colliding: Probably because you seem to be trying to compute the intersection point for coincident lines, which is not well-defined. I don't have time to debug this, but you might want to get some basic books on game programming and graphics. Incidentally, a dictionary lookup in Python is far more expensive than computing trig functions. If you need to speed this up for large numbers of rectangles, there are algorithms that are several orders of magnitude faster. Realistically, though, this is the kind of problem that runs slow in CPython. This is why you don't write your own collision library. (I once did, for 3D, but that was in 1996, when it was cutting-edge technology.) John Nagle -- http://mail.python.org/mailman/listinfo/python-list
Re: Collision of rotated rectangles without pygame
On Tue, 07 Dec 2010 00:53:27 -0800 John Nagle na...@animats.com wrote: On 12/5/2010 2:49 PM, Martin Manns wrote: Probably because you seem to be trying to compute the intersection point for coincident lines, which is not well-defined. I found the problem: pygame returns one pixel more for the right border than wx. Incidentally, a dictionary lookup in Python is far more expensive than computing trig functions. If you need to speed this up for large numbers of rectangles, there are algorithms that are several orders of magnitude faster. Realistically, though, this is the kind of problem that runs slow in CPython. This was taken from the vizier code. I fixed it. This is why you don't write your own collision library. (I once did, for 3D, but that was in 1996, when it was cutting-edge technology.) Is there a pure Python collision library other than vizier? Martin -- http://mail.python.org/mailman/listinfo/python-list
Re: Collision of rotated rectangles without pygame
On 12/7/2010 9:53 AM, John Nagle wrote: On 12/5/2010 2:49 PM, Martin Manns wrote: Hello, I am looking for a Python library for 2D collision checks of rotated rectangles. Currently, I have found vizier 0.5b that is based on pygame. Since I do not want to add a pygame dependency to my app, I replaced the pygame.rect.Rect by a wxPython wx.Rect (see code below). However, collision checks do not work correctly, i. e. identical rects are not found to be colliding: Probably because you seem to be trying to compute the intersection point for coincident lines, which is not well-defined. I don't have time to debug this, but you might want to get some basic books on game programming and graphics. Incidentally, a dictionary lookup in Python is far more expensive than computing trig functions. If you need to speed this up for large numbers of rectangles, there are algorithms that are several orders of magnitude faster. Realistically, though, this is the kind of problem that runs slow in CPython. That appears to be (from a rather limited investigation) a wild-assed assertion unjustified by anything other than preconceptions. With d as a dict containing 100 random numbers from (0,1) I see this: def fm(): ... x = random.random() ... return math.sin(x) ... def fd(): ... x = random.random() ... return x in d ... timeit.timeit(fm) 0.58099985122680664 timeit.timeit(fd) 0.5524577636719 Of course it's possible that the random number generation is dominating, but I'd still like to see some proof. I know for a fact that dict lookup has been extensively optimized, and while I am no longer involved in numerical computing it seems to me there's still a lot to do to compute a sin unless your CPU will do it for you. regards Steve This is why you don't write your own collision library. (I once did, for 3D, but that was in 1996, when it was cutting-edge technology.) John Nagle -- Steve Holden +1 571 484 6266 +1 800 494 3119 PyCon 2011 Atlanta March 9-17 http://us.pycon.org/ See Python Video! http://python.mirocommunity.org/ Holden Web LLC http://www.holdenweb.com/ -- http://mail.python.org/mailman/listinfo/python-list
Re: Collision of rotated rectangles without pygame
On Dec 7, 4:11 pm, Steve Holden st...@holdenweb.com wrote: timeit.timeit(fm) 0.58099985122680664 timeit.timeit(fd) 0.5524577636719 Of course it's possible that the random number generation is dominating, I think that it is. Moving the random number generation out into setup: t1 = timeit.Timer(sin(x.next()), from math import sin, radians; import random; x = iter([random.random() for i in xrange(100)])) t1.timeit(100) 0.45154733352978838 t2 = timeit.Timer(d[x.next()], import math, random; x = iter([random.randrange(360) for i in xrange(100)]); d = dict((i, math.sin(math.radians(i))) for i in xrange(360))) t2.timeit(100) 0.21765364033694823 Of course, the dict approach assumes that all angles will be an integer number of degrees. One could add precision, but looking up specific float values in a dict is dicey, so then one has to switch to decimal math, and that's going to add extra overhead -- probably enough to tip the scales in favor of math.sin. Cheers, Ian -- http://mail.python.org/mailman/listinfo/python-list
Collision of rotated rectangles without pygame
Hello,
I am looking for a Python library for 2D collision checks of rotated
rectangles. Currently, I have found vizier 0.5b that is based on pygame.
Since I do not want to add a pygame dependency to my app, I replaced the
pygame.rect.Rect by a wxPython wx.Rect (see code below).
However, collision checks do not work correctly, i. e. identical rects
are not found to be colliding:
$ python
Python 2.6.6 (r266:84292, Nov 28 2010, 18:42:58)
[GCC 4.4.5] on linux2
Type help, copyright, credits or license for more information.
import xrect
r=xrect.RotoRect(10,10,30,20,angle=34)
s=xrect.RotoRect(10,10,30,20,angle=34)
r.rotocollide(s)
False
Is my replacement of the rectangle object wrong or is vizier not
working correctly with pygame as well?
Do you know of any other pure Python library for rotated rectangle
collision checks?
Cheers
Martin
from __future__ import division
import math
import wx
##
cos_table = dict([(deg, math.cos(math.radians(deg))) for deg in xrange(360)])
sin_table = dict([(deg, math.sin(math.radians(deg))) for deg in xrange(360)])
class RotoRect(wx.Rect):
def __init__(self, *a, **kw):
self.deg = kw.pop('angle')
wx.Rect.__init__(self, *a, **kw)
# pygame rect compatibility for wx.Rect
def get_center(self):
return self.centerx, self.centery
def set_center(self, center):
self.centerx, self.centery = center
def get_centerx(self):
return self.x + self.width / 2
def set_centerx(self, centerx):
self.SetX(centerx - self.width / 2)
def get_centery(self):
return self.y + self.height / 2
def set_centery(self, centery):
self.SetY(centery - self.height / 2)
def get_topleft(self):
return self.GetTopLeft()
def set_topleft(self, p):
self.SetTopLeft(p)
def get_topright(self):
return self.GetTopRight()
def set_topright(self, p):
self.SetTopRight(p)
center = property(get_center, set_center)
centerx = property(get_centerx, set_centerx)
centery = property(get_centery, set_centery)
topleft = property(get_topleft, set_topleft)
topright = property(get_topright, set_topright)
# Now for the vizier code
def rotate(self, point, origin = 0):
Returns coords of point p rotated self.theta radians with
the rectangle around its center
if not origin: origin = self.center
p_x = point[0]
p_y = point[1]
o_x = origin[0]
o_y = origin[1]
costheta = cos_table[self.deg]
sintheta = sin_table[self.deg]
return ((o_x + costheta * (p_x - o_x)) - (sintheta * (p_y - o_y)),
(o_y + sintheta * (p_x - o_x)) + (costheta * (p_y - o_y)))
def rotoxt(self, a, b):
Returns the y extremity xt of rect between self.rect
a_x = a[0]
a_y = a[1]
b_x = b[0]
b_y = b[1]
#calculate difference between self.left and b_x
dxl = self.left - b_x
#calculate difference between self.right and b_x
dxr = self.right - b_x
#if b_x isn't between self.left and self.right
if (dxl * dxr) 0:
#if dxl 1, b_x is on the right
if (dxl 0):
#xt = (m * dxr) + b_y
xt = b_y - (-a_y)) / (b_x - (-a_x))) * dxr) + b_y)
else:
#else b_x is on the left
#xt = (m * dxl) + b_y
xt = b_y - a_y) / (b_x - a_x)) * dxl) + b_y)
return xt
else:
#else b_x is between self.left and self.right, and xt = b_y
return b_y
def rotocollide(self, rect):
Check for collision between self.rect and rect
#initialize collision to False
col = False
#transforming the plane to set rect's center to the origin
transplane = rect.center
#set rect's center to the origin
rect.center = (0, 0)
#transform self.rect's center by the transplane amount
self.center = (self.centerx - transplane[0],
self.centery - transplane[1])
#transforming the plane to set self.rect's theta to 0
transdeg = self.deg
Re: Collision of rotated rectangles without pygame
On Sun, 5 Dec 2010 23:49:36 +0100 Martin Manns mma...@gmx.net wrote: Is my replacement of the rectangle object wrong or is vizier not working correctly with pygame as well? Answering my first question: Vizier works O.K. with pygame. I am unsure what I did wrong in the rect replacement though. Cheers Martin -- http://mail.python.org/mailman/listinfo/python-list
