Detecting collision when rotating

Question

I have a chain of squares represented in pygame. I have some code that lets me rotate parts of the chain, as follows.

#!/usr/bin/python
import pygame

def draw(square):
    (x,y) = square
    pygame.draw.rect(screen, black, (100+x*20,100+y*20,20,20), 1) 

def rotate(chain, index, direction):
    (pivotx, pivoty) = chain[index]
    if (direction == 1):
        newchain = chain[:index]+[(y-pivoty+pivotx, (x-pivotx)+pivoty) for (x,y) in chain[index:]]
    else:
        newchain = chain[:index]+[(y-pivoty+pivotx, -(x-pivotx)+pivoty) for (x,y) in chain[index:]]
    return newchain

pygame.init()

size = [600, 600]
screen = pygame.display.set_mode(size)
white = (255,255,255)
black = (0,0,0)

n = 20
chain = [(i,0) for i in xrange(n)]

screen.fill(white)
for square in chain:
    draw(square)

pygame.display.flip()
raw_input("Press Enter to continue...")
newchain = rotate(chain, 5, 1)
print chain
print newchain
screen.fill(white)
for square in newchain:
    draw(square)

pygame.display.flip()
raw_input("Press Enter to continue...")

screen.fill(white)
newchain = rotate(newchain, 10,0)
for square in newchain:
    draw(square)

pygame.display.flip()
raw_input("Press Enter to continue...")
pygame.quit()

The function rotate takes an index of a square in the chain and rotates the whole chain after that square by 90 degrees, pivoting around the initial square. The problem is that this is meant to mimic a physical toy so it is not allowed to collide with itself. I can check to see if two squares are on top of each other after a rotation but how can I make sure they wouldn't collide temporarily during a rotation?

Answer 1

It sounds like you already know how to know if they're overlapping once you do the rotation, unless I am misunderstanding. If that's the case, then it would be relatively easy to define a function to answer that question given a potential rotation in the chain by adding a check to the end of your comprehension:

if (direction == 1):
    newchain = chain[:index]+[(y-pivoty+pivotx, (x-pivotx)+pivoty) for (x,y) in chain[index:] if not overlapping(x, y, pivotx, pivoty)]
else:
    newchain = chain[:index]+[(y-pivoty+pivotx, -(x-pivotx)+pivoty) for (x,y) in chain[index:] if not overlapping(x, y, pivotx, pivoty)]

And of course relying on some kind of:

def overlapping(x, y, px, py):
    if (some logic that determins if this is bad):
        raise Exception('Overlapping')
    return True

You would need to do something useful with the exception, but at least this would check each square as you process it, and break out immediately instead of waiting until after the whole rotation to verify that it's good.

Answer 2

I would use the pygame functions to do that.

1. make your surfaces to sprites.
2. rotate them with pygame.transform.rotate.
3. check collision with pygame functions.
4. this function works perfect for me ;).

def collision(sprite, group):
    rectCol = pygame.sprite.spritecollide(sprite, group, False)
    return [s for s in rectCol if pygame.sprite.collide_mask(sprite, s)]

sprite is one of your squares.
group is all the other squares.
the function returns a list with all squares witch collide with your square.

Answer 3

What you have to do is check a collision between the two quarter-circles that two sides of the rotating rect inscribe. To check collisions between a quarter-circle and a rectangle you can try adapting this code.

Answer 4

The 2 squares will overlap in transit if:

• one is stationary, the other is moving
• the center of one starts to the left of the other, and ends up to the right (cross product will be of use here)
• their distances to the pivot square are within a range (determined by the corners furthest and closest to the pivot square).

Above I gave an idea how to quickly check 2 given squares.

If you sort the squares by their distance to the pivot square, you will not have to check all pairs, only the pairs that are within a distance (thus avoiding O(N^2)).

Answer 5

One way you can do it is to model the squares after circles and use the relationship

d=sqrt((x2-x1)^2+(y2-y1)^2) (x1,y1), (x2,y2) being the center of the squares.

where d is the minimum distance between their centres. Then you compare it to r1+r2, where r1 and r2 are the radius of the circles residing in the squares. If d is less than r1+r2, reverse their unit velocity vector, or make them rotate the other way.

You can increase the accuracy of the model by testing the vertices of one square, against the diagonals of another square. For example (please take a graph paper to see this), say we have a square A , vertices being [(2,0),(0,2),(2,4),(4,2)], and another (square B) being [(2,2),(5,2),(5,5),(2,5)], now take any one square (we'll take B) and take any one of it's vertices, say, (2,2). Test if the x-coords (2) lies between the x-coordinate of the diagonally aligned vertices of A, say (2,4) and (2,0). Apparently it does! Then we check it against another diagonal, (0,2) and (4,2). It does too! So, square B has collided with square A and the rotation vector or the velocity vector has to be reversed. You may also check with the y-coords.

You'll have to loop through each square to check if they collide with others. However, you don't have to check all squares as you will only need to concern yourself with squares with min distance of d is less than r1+r2 relative to each other, so you will just need one loop to check if their distances are less than the sum of radius, and another loop to check if their vertices has entered the body of the square. I normally do that in my games which stimulate random motion of particles (e.g. brownian motion)

Answer 6

This problem has been generically solved many, many times. The simplest explanation is that you use an increasing level of detail.

For the shapes themselves you must create either bounding boxes or bounding circles which are large enough to contain the outer-most points in the shape. A bounding circle is nice because it is the smallest shape which will always fully cover the object. It also doesn't need to be regenerated after a rotation because it always describes the maximum space possible for your shape.

For a bounding circle the next operation is to measure the distance between each bounding circle and discard the ones that cannot possibly overlap. This is fairly inexpensive. Note too, that you can discard reflections. I.e. if you tested that shape a cannot overlap shape b, don't now test if shape b overlaps shape a.

Once you have the shapes which "may" overlap, you must use a precise algorithm to see if any point in one shape overlaps any point in the other shape. There are a variety of ways to do this. Some of them are geometric (GJK Algorithm) while others use things like z-buffers or pixel masks. For these latter kind you can draw one shape to a test buffer, then start to draw the second shape. If you check the buffer before you plot a pixel and see there is a pixel already there, you know there is an intersection (collision).