How to check if a circle lies inside of convex polygon

Question

I would like to check if a circle intersects or lies inside a convex polygon. I found a brilliant method to detect if a point is inside a polygon (from here):

        public boolean insidePolygon(Vector2 [] vertices, Vector2 p)
        {
            int i, j;
            boolean c = false;
            int nvert = vertices.length;
            for (i = 0, j = nvert - 1; i < nvert; j = i++)
            {
                if (((vertices[i].Y > p.Y) != (vertices[j].Y > p.Y)) &&
                 (p.X < (vertices[j].X - vertices[i].X) * (p.Y - vertices[i].Y) / (vertices[j].Y - vertices[i].Y) + vertices[i].X))
                    c = !c;
            }
            return c;
        }

And this works perfectly for a single point, but is there any way we could modify this to check if a circle with a given radius is inside a polygon? I suppose it's possible because a circle is actually a point but bigger, but still I haven't managed to succeed...

Answer 1

I can think of two ways to do this:

First way:
1) Compute distance from circle's center to each edge and each vertex and find the minimum and maximum distance, denoted as Dmin and Dmax respectively.
2) Check if the circle's center lies inside the polygon using your insidePolygon() function.
3) if ( R > Dmax ) then the circle encloses the polygon.
if ( Dmin < R < Dmax) then the circle intersects the polygon.
if ( R < Dmin && circle center is inside polygon), then circle is inside polygon.
if ( R < Dmin && circle center is outside polygon), then circle is outside polygon.

I have to admit that this pretty much has nothing to do with the original algorithm used by the insidePolygon().

Second way:
Offset the polygon inwards by distance = circle's radius. If the resulting polygon is still a valid polygon (i.e., is not self-intersecting) and maintain the same vertices traversing orientation, check if the circle's center is inside the offset polygon. If yes, the circle is inside the original polygon.

The second way is more algined with the original algorithm as it offsets the polgon inwards by the amount of the circle's radius, thus virtually reducing the circle back to a point. However, implementation wise, the first way is probably easier.