Collision of rotated rectangles without pygame

[Steve Holden]

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/