Search code examples
algorithmgeometrycomputational-geometryintersectionarea

Compute the area of intersection between a circle and a triangle?

How does one compute the area of intersection between a triangle (specified as three (X,Y) pairs) and a circle (X,Y,R)? I've done some searching to no avail. This is for work, not school. :)

It would look something like this in C#:

struct { PointF vert[3]; } Triangle;
struct { PointF center; float radius; } Circle;

// returns the area of intersection, e.g.:
// if the circle contains the triangle, return area of triangle
// if the triangle contains the circle, return area of circle
// if partial intersection, figure that out
// if no intersection, return 0
double AreaOfIntersection(Triangle t, Circle c)
{
 ...
}
Solution

  • If you want an exact solution (or at least as exact as you can get using floating-point arithmetic) then this is going to involve a lot of legwork, because there are so many cases to consider.

    I count nine different cases (categorized in the figure below by the number of vertices of the triangle inside the circle, and the number of edges of the triangle that intersect or are contained in the circle):

    Nine cases for intersection: 1, 2. no vertices, no edges; 3. no vertices, one edge; 4. no vertices, two edges; 5. no vertices, three edges; 6. one vertex, two edges; 7. one vertex, three edges; 8. two vertices, three edges; 9. three vertices, three edges.

    (However, this kind of enumeration of geometric cases is well known to be tricky, and it wouldn't surprise me at all if I missed one or two!)

    So the approach is:

    1. Determine for each vertex of the triangle if it's inside the circle. I'm going to assume you know how to do that.

    2. Determine for each edge of the triangle if it intersects the circle. (I wrote up one method here, or see any computational geometry book.) You'll need to compute the point or points of intersection (if any) for use in step 4.

    3. Determine which of the nine cases you have.

    4. Compute the area of the intersection. Cases 1, 2, and 9 are easy. In the remaining six cases I've drawn dashed lines to show how to partition the area of intersection into triangles and circular segments based on the original vertices of the triangle, and on the points of intersection you computed in step 2.

    This algorithm is going to be rather delicate and prone to errors that affect only one of the cases, so make sure you have test cases that cover all nine cases (and I suggest permuting the vertices of the test triangles too). Pay particular attention to cases in which one of the vertices of the triangle is on the edge of the circle.

    If you don't need an exact solution, then rasterizing the figures and counting the pixels in the intersection (as suggested by a couple of other respondents) seems like a much easier approach to code, and correspondingly less prone to errors.