I have a polygon (sometimes convex, but often concave), and a bunch of circles with different radii. How can I find out if a circle is intersecting/overlapping with the polygon?
I could split my concave polygon into convex pieces. Would that help?
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It only takes a minute to sign up.
Sign up to join this communitythere are two cases of this problem. First is the intersection and second that is overlaping (containing).
First (intersection / polygon inside circle):
Find closest point on every edge of the polygon to the circle's center. If any distance between closest point to the center is less than radius, you got intersection or overlap.
Second (circle is whole in polygon): Shoot ray from circle center to the right (or left/up/down) and count ray/segment (polygon edges) intersections. If intersection count is even circle is outside of polygon. If it's odd circle is inside.
I'll share picter from lectue for this case:
And take care of the singular cases.
Hope this will help.
edit: I think that it is just fair to add credits to the picture. Author is Petr Felkel, Assistant Professor at Czech Technical University in Prague
The first step, as you guess, is to split the concave polygon into multiple convex ones. The reason for this is that you'll use the separating axis theorem, which only works on convex polygons.
SAT per se only works on two convex polygons. The "separating axis" in the name refers to the axes perpendicular to the edges of the polygon. Circles, unfortunately, have an infinite number of these. However, it turns out there's a pretty easy way to find out which of those axes are relevant, by looking at this which project outwards to intersect the vertices of the polygon.
Rather than go over the entire algorithm here, Metanet Software (makers of N/N+) have a good tutorial on collision detection using SAT, the third section of which covers SAT when one of the objects is a circle.
Here's what I do.