collision between a rect and a circle?

CyanPrime · May 14, 2010, 12:14pm

Okay, I’m trying to create a method to handle collisions between a rect and a circle. this is how far I’ve gotten, but now I’m stumped. It only works properly if px and py < the circles center.

Here’s the method


    public boolean col(){
    	float planeAngle = (float) Math.toDegrees(Math.atan2(px - (px + pwidth), -(py - py)));
    	float planeWidth = rotate(px + pwidth,py + pheight, px,py,planeAngle,true);
    	float planeHeight = rotate(px + pwidth,py + pheight, px,py,planeAngle,false);
    	float planeCentX = (planeWidth/2);
    	float planeCentY = (planeHeight/2);
    	
    	float dist = (float) Math.sqrt(Math.pow((bx + (bsize/2)) - planeCentX, 2) + Math.pow(-((by + (bsize/2)) - planeCentY), 2));

    	if(dist <= (bx + (bsize/2)))
    		return true;
    		
    	else
    		return false;
    }

and here is the full source: (requires slick)


import org.newdawn.slick.AppGameContainer;
import org.newdawn.slick.BasicGame;
import org.newdawn.slick.GameContainer;
import org.newdawn.slick.Graphics;
import org.newdawn.slick.Input;
import org.newdawn.slick.SlickException;

public class ColTest extends BasicGame{

    
	float px = 50;
	float py = 50;
	float pheight = 50;
	float pwidth = 50;
	
	float bx = 200;
	float by = 200;
	float bsize = 200;
	
	float pspeed = 3;
    Input input;
    
    public ColTest()
    {
        super("ColTest");
    }
 
    @Override
    public void init(GameContainer gc)
			throws SlickException {
         
    }

    @Override
    public void update(GameContainer gc, int delta)
			throws SlickException
	{
    	input = gc.getInput();
    	
    	try{	
    		if(input.isKeyDown(Input.KEY_UP))	
        		py-=pspeed;
    		
    		if(input.isKeyDown(Input.KEY_DOWN))	
        		py+=pspeed;
    		
    		if(input.isKeyDown(Input.KEY_LEFT))	
        		px-=pspeed;
    		
    		if(input.isKeyDown(Input.KEY_RIGHT))	
        		px+=pspeed;
    	}
    	
    	catch(Exception e){}
	}
 
    public void render(GameContainer gc, Graphics g)
			throws SlickException
    {	
    		g.drawString("col: " + col(), 10, 10);
    		g.fillRect(px, py, 50, 50);
    		g.fillOval(200, 200, 200, 200);
    }
    
    public boolean col(){
    	float planeAngle = (float) Math.toDegrees(Math.atan2(px - (px + pwidth), -(py - py)));
    	float planeWidth = rotate(px + pwidth,py + pheight, px,py,planeAngle,true);
    	float planeHeight = rotate(px + pwidth,py + pheight, px,py,planeAngle,false);
    	float planeCentX = (planeWidth/2);
    	float planeCentY = (planeHeight/2);
    	
    	float dist = (float) Math.sqrt(Math.pow((bx + (bsize/2)) - planeCentX, 2) + Math.pow(-((by + (bsize/2)) - planeCentY), 2));

    	if(dist <= (bx + (bsize/2)))
    		return true;
    		
    	else
    		return false;
    }
    
    public float rotate(float x, float y, float ox, float oy, float a, boolean b)
    {
         float dst = (float) Math.sqrt(Math.pow(x-ox,2.0)+ Math.pow(y-oy,2.0));

         float oa = (float) Math.atan2(y-oy,x-ox);

         if(b)
         	return (float) Math.cos(oa + Math.toRadians(a))*dst+ox;

         else
         	return (float) Math.sin(oa + Math.toRadians(a))*dst+oy;

    }
    
    public static void main(String[] args)
			throws SlickException
    {
         AppGameContainer app =
			new AppGameContainer( new ColTest() );
 
         app.setShowFPS(false);
         app.setAlwaysRender(true);
         app.setTargetFrameRate(60);
         app.setDisplayMode(800, 600, false);
         app.start();
    }
}

Roquen · May 14, 2010, 12:17pm

You’ll probably get a faster response if you ask a question that doesn’t require the reader to figure out your code to understand what is being asked.

Circle to Rect: Can the rectangle be rotated?

CyanPrime · May 14, 2010, 12:28pm

Yeah, it can.

Demonpants · May 14, 2010, 6:49pm

The key thing to remember here is that you just need to distill this down into the possible cases. What are the different things that can happen?

The circle can be outside the rectangle (no collision).
The circle can touching one of the vertices of the rectangle only.
The circle can be touching one of the sides of the rectangle.
The circle can be touching any number of sides as well as any number of vertices.
The rectangle can lie inside the circle.
The circle can lie inside the rectangle.

Calculating every single one of those would take a lot of time, thinking, and waste a lot of cycles, but you would probably be able to figure out a way to do each step if your geometry is pretty good. But after doing them all you’d probably realize that there are a lot of redundant cases there.

If the circle is touching just one vertex, that means that it’s also touching two different line segments.
if the circle is touching multiple sides or vertices, then you should only need to check the first side it’s touching and then know there is collision.
If the rectangle lies inside the circle, then that’s equivalent to all 4 sides touching the circle.

So that simplifies us to:

The circle can be outside the rectangle (no collision).
The circle can be touching one of the sides of the rectangle.
The circle can lie inside the rectangle.

We don’t need to worry about checking for the first case, because we know if either of the last two cases are true then the first case can’t be true. So that leaves just two.

The circle can be touching one of the sides of the rectangle.
The circle can lie inside the rectangle.

And to simplify even more, you know that the circle lies inside the rectangle, if it gets too close to a side then that means that it will intersect that side, so all you really need to do is see if the center of the circle lies inside the rectangle - its radius doesn’t even matter.

Google should be able to tell you how to do circle/segment collision (essentially you see if the radius segment that is perpendicular to the line segment intersects the line segment), and also how to find whether or not a point lies inside a rectangle (compare 4 dot products for the perpendiculars of each line, basically).

Or, have a look here:

http://local.wasp.uwa.edu.au/~pbourke/geometry/sphereline/

Gudradain · May 15, 2010, 3:53am

Rotate the axis.

Abuse · May 15, 2010, 1:30pm

Are either the circle or rectangle in motion?

If so, you need to intersect the swept volumes, not just the static shapes.
To not do so will lead to pass-through, (to a lesser or greater extent, depending on your time step & object velocities)

Demonpants · May 15, 2010, 5:16pm

Yes, this is true.

By swept volume he means if you were to draw a circle at previousPos, then another one at destinationPos, then draw two lines to connect the circles (to end up with a sort of cylinder), and calculate collision that way.

Riven · May 15, 2010, 8:16pm

Oh man, there is this not-so-fine line between correctness and helpfulness.

Nate · May 16, 2010, 12:20am

Is the circle in a bad mood? How does the rectangle feel about the circle’s possible intersection?

Is Riven’s circle of vagueness intersecting the not-so-fine line of helpfulness? Signs say yes.

Riven · May 16, 2010, 12:25am

What I tried to say discretely, was that if this poor boy is struggling with circle/rect intersections, it’s absolutely no help to him to even mention swept circle/rect intersections.

SimonH · May 16, 2010, 2:08am

So, there’s a circle and a rectangle… how about this;

Get the distance and angle from the centre of the rectangle to the centre of the circle (using sqrt() and atan2()).
Clip this line to the rectangle (you can use tan(angle) on the relevant side/sides to do this) & get the length of the clipped line (if no clipping is required then a collision is certain - the centre of the circle must lie inside the rectangle).
Now if clipped_length+circle_radius<distance_between_centres then there is no collision.

Not very efficient and could indeed get iffy if either shape is moving fast, but it should generally work…

Demonpants · May 16, 2010, 7:10am

Here’s an easy (and totally inefficient) way to do this:

Implement normal circle / rectangle collision, as we talked about above.
As an object moves, instead of moving it its full distance, move it one pixel at a time, checking for collision after each movement. If it would collide with something as part of its movement, then you will be able to stop it within the precision of one pixel, which is obviously all the granularity you need for it to look fine to the player.

As I said, it’s easy to implement but very very wasteful. But it works. If you don’t have too many entities and your circle / rectangle collision algorithm is fast enough, this should suit you just fine.

bleb · May 16, 2010, 8:44am

Demonpants has posted the answer: Check for the circle center lying inside the rectangle (4 dot products), check for the rectangle edges intersecting the circle (4 closest-point-on a line-segment and distance checks).
Don’t worry about motion until you know it’s a problem.

SimonH · May 17, 2010, 1:33am

[quote=“bleb,post:13,topic:35294”]
Sure! I posted the kludge - sometimes the perfect is the enemy of the good…