How to check if a circle is "outside" of a polygon?

Question

I'm trying to write a function to check if a circle is contained inside a polygon.

My algorithm is:

if they intersect, return false

if the circle is "outside" of the polygon, return false

return true

by outside, I mean something like this:

I thought about creating a line segment between the center of the circle and the center of the polygon, and if they intersect an edge on the polygon then the circle is outside of the polygon. But is there another way to do it?

Answer 1

You have a polygon defined by a list of points A0, A1, A2, ..., Ak, and a circle defined by a center C and a radius r.

Possible algorithm:

1. Find whether the center C is inside the polygon or not;
2. If C is outside the polygon, return False.
3. Else, find the point P on the polygon which is closest to the circle center C;
4. Compare the distance PC with the radius r.
5. Return the boolean value r < PC.

This leaves us with two sub-problems to solve:

• How to find whether point C is inside the polygon;
• How to find the closest point on the polygon.

Related questions solving these sub-problems:

• Distance from a point to a polygon;
• javascript: How can I find closest point on a polygon from a point?;
• How can I determine whether a 2D Point is within a Polygon?;
• javascript: Check if Point Is Inside A Polygon;
• C: Point in polygon algorithm;
• python matplotlib: What's the fastest way of checking if a point is inside a polygon in python.

Answer 2

1. If the centre of the circle is inside the polygon, the circle is either overlapping or inside it.
2. If any point of the polygon lies on or inside the circle, they are overlapping.
3. If any line-segment of the polygon is intersecting the circle, they are overlapping.
4. Otherwise the circle is outside the polygon.

Something like this should work (C++):

#include <iostream>
#include <vector>
#include <cmath>

namespace math
{

struct Point
{
    int x;
    int y;
};

bool PointInCircle(Point p, Point center, std::size_t radius)
{
    return ((p.x - center.x) * (p.x - center.x) + (p.y - center.y) * (p.y - center.y)) < (radius * radius);
}

bool PointOnCircle(Point p, Point center, std::size_t radius)
{
    return ((p.x - center.x) * (p.x - center.x) + (p.y - center.y) * (p.y - center.y)) == (radius * radius);
}

bool LineIntersectsCircle(int ax, int by, int c, Point center, std::size_t radius)
{
    // radius == distance = touching/tangent
    // radius > distance = not intersecting
    // radius < distance = intersecting
    int distance = (std::abs(ax * center.x + by * center.y + c)) / sqrt(ax * ax + by * by);
    return distance <= radius;
}

bool PointInPolygon(Point p, std::vector<Point> poly)
{
    bool result = false;
    
    std::size_t j = poly.size();
    for (std::size_t i = 0; i < poly.size(); ++i)
    {
        if (((poly[i].y <= p.y && p.y < poly[j].y) || (poly[j].y <= p.y && p.y < poly[i].y))
            &&
            p.x < ((poly[j].x - poly[i].x) * (p.y - poly[i].y) / (poly[j].y - poly[i].y) + poly[i].x))
        {
             result = !result;
        }

        j = i;
    }
    return result;
}

bool CircleInsidePolygon(Point center, std::size_t radius, std::vector<Point> poly)
{
    // Circle with radius 0 isn't a circle
    if (radius == 0)
    {
        return false;
    }
    
    // If the center of the circle is not within the polygon,
    // then the circle may overlap, but it'll never be "contained"
    // so return false
    if (!PointInPolygon(center, poly))
    {
        return false;
    }
    
    for (std::size_t i = 0; i < poly.size(); ++i)
    {
        // If any point of the polygon is within the circle,
        // the circle is not "contained"
        // so return false
        if (PointInCircle(poly[i], center, radius))
        {
            return false;
        }
    }
    
    for (std::size_t i = 0; i < poly.size(); ++i)
    {
        // If any line-segment of the polygon intersects the circle,
        // the circle is not "contained"
        // so return false
        
        Point P1 = i == 0 ? poly[0] : poly[i];
        Point P2 = i == 0 ? poly[poly.size() - 1] : poly[i + 1];
        
        int X1 = P1.x;
        int X2 = P2.x;
        int Y1 = P1.y;
        int Y2 = P2.y;
        
        int A = Y1 - Y2;
        int B = X2 - X1;
        int C = (X1 * Y2) - (X2 * Y1);
        
        if (LineIntersectsCircle(A, B, C, center, radius))
        {
            return false;
        }
    }
    
    return true;
}

bool CircleOutsidePolygon(Point center, std::size_t radius, std::vector<Point> poly)
{
    // Circle with radius 0 isn't a circle
    if (radius == 0)
    {
        return false;
    }
    
    // If the center of the circle is within the polygon,
    // the circle is not outside of the polygon completely.
    // so return false.
    if (PointInPolygon(center, poly))
    {
        return false;
    }
    
    for (std::size_t i = 0; i < poly.size(); ++i)
    {
        // If any point of the polygon is within the circle,
        // or any point of the polygon lies on the circle,
        // the circle is not outside of the polygon
        // so return false.
        if (PointInCircle(poly[i], center, radius) || PointOnCircle(poly[i], center, radius))
        {
            return false;
        }
    }
    
    for (std::size_t i = 0; i < poly.size(); ++i)
    {
        // If any line-segment of the polygon intersects the circle,
        // the circle is not outside the polygon, it is overlapping,
        // so return false
        
        Point P1 = i == 0 ? poly[0] : poly[i];
        Point P2 = i == 0 ? poly[poly.size() - 1] : poly[i + 1];
        
        int X1 = P1.x;
        int X2 = P2.x;
        int Y1 = P1.y;
        int Y2 = P2.y;
        
        int A = Y1 - Y2;
        int B = X2 - X1;
        int C = (X1 * Y2) - (X2 * Y1);
        
        if (LineIntersectsCircle(A, B, C, center, radius))
        {
            return false;
        }
    }
    
    return true;
}

}

int main()
{
    std::size_t radius = 1;
    math::Point p = {-2, -2};
    
    std::vector<math::Point> poly = {
        {0, 0},
        {100, 0},
        {100, 100},
        {0, 100}
    };
    
    bool is_inside = math::CircleInsidePolygon(p, radius, poly);
    bool is_outside = math::CircleOutsidePolygon(p, radius, poly);
    bool is_intersecting = !is_inside && !is_outside;
    
    std::cout<<"Circle In Polygon: "<<std::boolalpha<<is_inside<<"\n";
    std::cout<<"Circle Outside Polygon: "<<std::boolalpha<<is_outside<<"\n";
    std::cout<<"Circle Intersecting Polygon: "<<std::boolalpha<<is_intersecting<<"\n";
    
    return 0;
}