20
\$\begingroup\$

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?

Improve this question
\$\endgroup\$

3 Answers 3

Reset to default
26
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 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 \$\endgroup\$
    – bummzack
    Jan 26, 2011 at 12:59
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Notabene
    Jan 26, 2011 at 13:02
  • 1
    \$\begingroup\$ I'm sorry I confused "edge" with "vertex" and therefore misinterpreted your first check. When reading it correctly, it works :) \$\endgroup\$
    – bummzack
    Jan 26, 2011 at 14:04
7
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$
    – ehsanul
    Jan 26, 2011 at 20:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – SplinterReality
    Jan 27, 2011 at 5:21
  • 1
    \$\begingroup\$ @ehsanul: en.wikipedia.org/wiki/Polygon_triangulation describes a couple popular approaches. \$\endgroup\$
    – user744
    Jan 27, 2011 at 9:10
0
\$\begingroup\$

Here's what I do.

  1. Use the horizintal line test to detect if the center of the circle is inside the polygon. If it is, then they intersect.
  2. If not, check for the following case. For each side of the polygon
    1. Find the slope of the polygon side
    2. Calculate the Perpendicular Slope
    3. (READ THIS CAREFULLY) Find the intersect between a line with the slope of the polygon side intersecting with either vertex which makes the side, and the line of the slope perpendicular to that of the side which intersects the circle's center.
    4. If the established point of intersection lies inside the circle, this means thee circle at some point crosses over the side in question, and is hence intersecting the polygon
  3. Lastly, if nothing else is conclusive, check if any vertices of the polygon lie inside of the circle (because of previous tests, you only need to check once) If so, they intersect. If not, you can conclusively say that they don't.
Improve this answer
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .