Collision of rotated rectangles without pygame

[Martin Manns]

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.

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

#set self.rect's theta to 0
self.deg = 0

#transform rect's theta by the transtheta amount
rect.deg -= transdeg

#determine which vertice is min/max x/y NOTE:
# a = left/right, b = top/bottom
if (sin_table[rect.deg] * cos_table[rect.deg]) > 0:
#a = extreme left/right, b = extreme top/bottom
a, b = rect.topright, rect.topleft
else:
a, b = rect.topleft, rect.topright

#determine if a.x is min/max
if sin_table[rect.deg] < 0:
#ensure a is always max
a = -a[0], -a[1]
a_x = a[0]
negb = -b[0], -b[1]

#check that range of rect (-a.x, a.x) overlaps range of
#self.rect (self.left, self.right)

if (a_x >= self.left) and (self.right >= -a_x):
#get the first extremity
xt1 = self.rotoxt(a, b)

#get the other extermity
xt2 = self.rotoxt(a, negb)

#check for an intersection between the two extremities and
#self.rect's top/bottom

col = (((xt1 >= self.top) and (self.bottom >= xt2)) or
((xt2 >= self.top) and (self.bottom >= xt1)))

#retransform rect.center
rect.center = transplane

#retransform self.rect.center
self.center = (self.centerx + transplane[0],
self.centery + transplane[1])

#retransform self.theta
self.deg = transdeg

#retransform rect.theta
rect.deg += transdeg

#return results of collision test
return col

@property
def rotox(self):
return self.rotate(self.topleft)[0]
@property
def rotoy(self):
return self.rotate(self.topleft)[1]
@property
def rotoleft(self):
return self.rotate(self.left)
@property
def rotoright(self):
return self.rotate(self.right)
@property
def rototop(self):
return self.rotate(self.top)
@property
def rotobottom(self):
return self.rotate(self.bottom)
@property
def rototopleft(self):
return self.rotate(self.topleft)
@property
def rototopright(self):
return self.rotate(self.topright)
@property
def rotobottomright(self):
return self.rotate(self.bottomright)
@property
def rotobottomleft(self):
return self.rotate(self.bottomleft)
@property
def rotomidleft(self):
return self.rotate(self.midleft)
@property
def rotomidright(self):
return self.rotate(self.midright)
@property
def rotomidtop(self):
return self.rotate(self.midtop)
@property
def rotomidbottom(self):
return self.rotate(self.midbottom)

 

[Martin Manns]

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

 

[John Nagle]

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

 

[Martin Manns]

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

 

[Steve Holden]

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:
.... x = random.random()
.... return math.sin(x)
........ x = random.random()
.... return x in d
....
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

 

[Ian]

0.55200004577636719

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(1000000)])")
t1.timeit(1000000)

0.45154733352978838

t2 = timeit.Timer("d[x.next()]", "import math, random; x = iter([random.randrange(360) for i in xrange(1000000)]); d = dict((i, math.sin(math.radians(i))) for i in xrange(360))")
t2.timeit(1000000)

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