Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have a polygon (sometimes convex, but often concave), and a bunch of circles with different radius. How can I find out if a circle is intersecting/overlapping with the polygon?

If it makes it easier, then I can split my concave polygon into convex pieces no problem. Would this help to solve the problem? Or just an unnecessary step?

share|improve this question

2 Answers 2

up vote 22 down vote accepted

there 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:

enter image description here

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

share|improve this answer
    
I don't think this will work by just "shooting" a ray to the right. Maybe I misread your approach, but from what I understood it would fail with a setup as depicted here: imgur.com/Whg2u –  bummzack Jan 26 '11 at 12:59
2  
Yes but this is described in the first case. Shooting ray will solve only the Polygon containing circle (second case in my description). You have to test both cases. It is fast, easy to implement and do not need any memory. –  Notabene Jan 26 '11 at 13:02
1  
I'm sorry I confused "edge" with "vertex" and therefore misinterpreted your first check. When reading it correctly, it works :) –  bummzack Jan 26 '11 at 14:04

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.

share|improve this answer
    
Do you have a reference for splitting a concave polygon into convex polygons? The SAT link you provided doesn't mention anything of the sort. –  ehsanul Jan 26 '11 at 20:50
    
This is actually a very complex problem depending on the geometry of the polygon, but all 3D engines do this, as the hardware can generally only render coplanar quads and triangles, not polygons. –  SplinterReality Jan 27 '11 at 5:21
1  
@ehsanul: en.wikipedia.org/wiki/Polygon_triangulation describes a couple popular approaches. –  user744 Jan 27 '11 at 9:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.