CODEWITHSUNDEEP
javageometrycollision-detection
Savail
Savail

Reputation: 867

How to check if a circle lies inside of convex polygon

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...

Upvotes: 5

Views: 3716

Answers (2)

fang
fang

Reputation: 3633

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.

Upvotes: 3

JTMon
JTMon

Reputation: 3199

There are many ways to do it mathematically, however the way I did it was using the Area class. It might not be the most efficient way of doing it performance wise, but the speed was good enough for my needs and since I am not a math wiz, the no math part was a plus :) 

public bool polygonContains circle (Shape poly, Shape circle){
    Area p = new Area(poly);
    if (!p.contains(circle.center)) return false;
    Area a = new Area(poly);        
    Area c = new Area(circle);
    a.add(c);
    //get the pathiterator of a and one for area p and compare the points they return
    // if there is a point in a not in p, it means circle jets out of polygon so return false.
    //if you care about the circle touching the inside of the polygon then 
    Area m = new Area(poly);
    Area s = m.substract(c);
    //repeat the pathiterator comparison for p and s , if there is a point in s not found in a
    //it means the circle touched the edge of the polygon return the value you see fit.
    return true;
}

Upvotes: 0

Related Questions