Circle and Polygon Collision

Circle and Polygon Collision

Rick

Member #3,572

June 2003

How would one go about checking collision between a circle and a polygon. More specifically a diamond shape? But I imagine there would be a generic algorithm for any polygon and a circle. 2 Rectangles I could do. 2 Circles I could do also, but mixing them I don't know how to start.

========================================================
Actually I think I'm a tad ugly, but some women disagree, mostly Asians for some reason.

FMC

Member #4,431

March 2004

Wouldn't it be easier to turn the circle into a polygon and then check for collision between two polygons?

[FMC Studios] - [Caries Field] - [Ctris] - [Pman] - [Chess for allegroites]
Written laws are like spiders' webs, and will, like them, only entangle and hold the poor and weak, while the rich and powerful will easily break through them. -Anacharsis
Twenty years from now you will be more disappointed by the things that you didn't do than by the ones you did do. So throw off the bowlines. Sail away from the safe harbor. Catch the trade winds in your sails. Explore. Dream. Discover. -Mark Twain

Rick

Member #3,572

June 2003

I'll give it a try. Thanks.

========================================================
Actually I think I'm a tad ugly, but some women disagree, mostly Asians for some reason.

Fladimir da Gorf

Member #1,565

October 2001

Heh, sorry I just had to...

In OpenLayer:

Poly polygon( ... );
Circle circle( pos, radius );

if( polygon.Collides( Poly( circle.ToPolygon() ))) {
  // Collision!
}

OpenLayer has reached a random SVN version number ;) | Online manual | Installation video!| MSVC projects now possible with cmake | Now alvailable as a Dev-C++ Devpack! (Thanks to Kotori)

james_lohr

Member #1,947

February 2002

Quote:

Wouldn't it be easier to turn the circle into a polygon and then check for collision between two polygons

That's not a good idea because firstly it would only be an approximation, and secondly it's a waste of resources.

You can do it properly by breaking the polygon up into line segments, and then calculating the perpendicular distance from the circle's centre to each line. If the perpendicular distance is smaller than the radius of the circle and the perpendicular intersects the line segment, then you have a collision. Of course, you also have a collision if the distance from any of the points describing the polygon is closer to the centre of the circle than its radius. Finally, for the case when the circle is completely inside the polygon, you'll need to check if the cenre of the circle is inside the polygon, which is your standard polygon-point intersection problem.