How to check if a circle is inside a convex polygon
I would like to check if a circle intersects or lies inside a convex polygon. I found a brilliant method to determine 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 great for one point, but is there a way to change this to check if a circle with a given radius is inside a polygon? I guess this is possible because the circle is actually a point, but larger, but still I have not been successful ...
source to share
I can think of two ways to do this:
Method one:
1) Calculate the distance from the center of the circle to each edge and each vertex and find the minimum and maximum distances, denoted as Dmin and Dmax respectively.
2) Check if the center of the circle is inside the polygon using your inner Polygon () function.
3) if (R> Dmax), then the circle encloses the polygon.
if (Dmin <R <Dmax), then the circle intersects the polygon.
if (R <Dmin && the center of the circle is inside the polygon), then the circle is inside the polygon.
if (R <Dmin && the center of the circle is outside the polygon), then the circle is outside the polygon.
I must admit that this pretty much has nothing to do with the original algorithm used internally by Polygon ().
Method two:
Offset the polygon inward by distance = circle radius. If the resulting polygon is still a valid polygon (i.e., not self-intersecting) and maintains the same vertex intersection orientation, check if the center of the circle is inside the offset polygon. If so, then the circle is inside the original polygon.
The second method is more related to the original algorithm, since it shifts the half-run inward by the amount of the radius of the circle, thereby actually reducing the circle to a point. However, the implementation is wise, the first way is probably easier.
source to share
There are many ways to do it mathematically, but the way I did it was using the class Area
. It might not have been the most efficient way to make this work wise, but the speed was good enough for my needs and since I'm not a math wiz the math part was not 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;
}
source to share