# Circle - Polygon intersection test

This topic is 3314 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've been looking around a bit for methods to determine if a circle intersects with a general polygon (i.e. concave or convex). And it's beginning to look like that is generally something difficult (as with most collision algorithms, concave leading to many of the problems). So I guess I'm asking two things: 1) Does anyone know of a good algorithm that DOES do circle -> polygon intersection testing? 2) If i am right and that's generally a more complex topic, my next feeling is to tessellate the polygon into a triangle strip, and then do the much simpler, circle -> triangle intersection test. Does this sound reasonable? The performance isn't much of a concern, it is only going to be run on a few triangles (n < ~10) every minute or so.

##### Share on other sites
There isn't a direct easy method for concave polygons that I know of.

here's two that you mentioned.

1)
. split concave polygon into convex pieces (gluTesselate(), or some simple algo if your concave polygons are sensible).
. for each convex piece, find point on perimeter the closest to the sphere centre.
. check if closest point is inside circle.
. also check if sphere centre inside each convex perimeter (usually given when you do the closest point calculation).

2)
. for each edge, find closest point on edge to sphere centre.
. check if closest point inside the circle.
. do a point-in-concave-polygon test for the circle centre.

##### Share on other sites
One method rather similar to described above is to first break up the concave polygon into convex parts and then perform a Separating Axis Test against each of them. Both the circle and convex polygon are convex, so SAT applies. Since the separating axis must be parallel to one of the edges of the convex polygon, there's only a small number of axes to test.

##### Share on other sites
I'm looking into all of this, thanks for the responses, i'll post back once I get it all worked out :)

##### Share on other sites
Seems pretty simple, actually, even without a decomposition. Just do a segment-circle test with each edge of the polygon, and a point-in-polygon test with the center of the circle. That should catch both fully-enclosed cases as well as the general case.

EDIT: nevermind, olii already mentioned it. Do it that way, tho. :-)

##### Share on other sites
Ah yes, the 2 step process worked perfectly, and was quite simple, thanks a million guys!

1. 1
Rutin
25
2. 2
JoeJ
20
3. 3
4. 4
5. 5

• 9
• 9
• 46
• 41
• 23
• ### Forum Statistics

• Total Topics
631749
• Total Posts
3002053
×