Collision of rotated rectangles without pygame

Discussion in 'Python' started by Martin Manns, Dec 5, 2010.

  1. Martin Manns

    Martin Manns Guest

    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

    #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, Dec 5, 2010
    #1
    1. Advertising

  2. Martin Manns

    Martin Manns Guest

    On Sun, 5 Dec 2010 23:49:36 +0100
    Martin Manns <> 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
    Martin Manns, Dec 5, 2010
    #2
    1. Advertising

  3. Martin Manns

    John Nagle Guest

    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
    John Nagle, Dec 7, 2010
    #3
  4. Martin Manns

    Martin Manns Guest

    On Tue, 07 Dec 2010 00:53:27 -0800
    John Nagle <> 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
    Martin Manns, Dec 7, 2010
    #4
  5. Martin Manns

    Steve Holden Guest

    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.55200004577636719
    >>>


    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/
    Steve Holden, Dec 7, 2010
    #5
  6. Martin Manns

    Ian Guest

    On Dec 7, 4:11 pm, Steve Holden <> wrote:
    > >>> timeit.timeit(fm)

    > 0.58099985122680664
    > >>> timeit.timeit(fd)

    > 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
    Ian, Dec 8, 2010
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    507
  2. Jae

    Rotated text in a datagrid

    Jae, Nov 21, 2003, in forum: ASP .Net
    Replies:
    2
    Views:
    1,435
    vMike
    Nov 22, 2003
  3. Ajay Patil
    Replies:
    0
    Views:
    444
    Ajay Patil
    Dec 10, 2003
  4. Abs
    Replies:
    4
    Views:
    8,407
    Jesper Nordenberg
    May 14, 2004
  5. rantingrick

    [pygame-bug] Pygame.cdrom bug

    rantingrick, Jan 30, 2011, in forum: Python
    Replies:
    1
    Views:
    304
    Benjamin Kaplan
    Jan 30, 2011
Loading...

Share This Page