Compute the area of intersection between a circle

Question

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)
{
 ...
}

Answer 1

Since your shapes are convex, you can use Monte Carlo area estimation.

Draw a box around the circle and triangle.

Choose random points in the box and keep a count of how many fall in the circle, and how many fall in both the circle and triangle.

Area of Intersection ≅ Area of circle * # points in circle and triangle / # points in circle

Stop choosing points when the estimated area doesn't change by more than a certain amount over a certain number of rounds, or just choose a fixed number of points based on the area of the box. The area estimate should converge pretty fast unless one of your shapes has very little area.

Note: Here's how you determine if a point is in a triangle: Barycentric coordinates

Answer 2

How exact do you need to be? If you can approximate the circle with simpler shapes, you can simplify the problem. It wouldn't be hard to model a circle as a set of very narrow triangles meeting at the center, for example.

Answer 3

If just one of the triangle's line segments intersects the circle, the pure math solution isn't too hard. Once you know when the two points of intersection are, you can use the distance formula to find the chord length.

According to these equations:

ϑ = 2 sin⁻¹(0.5 c / r)
A = 0.5 r² (ϑ - sin(ϑ))

where c is the chord length, r is the radius, ϑ becomes the angle through the center, and A is the area. Note that this solution breaks if more than half the circle is cut off.

It's probably not worth the effort if you just need an approximation, since it makes several assumptions about what the actual intersection looks like.

Answer 4

I'm almost a year and a half late, but I thought maybe people will be interested in code here that I wrote which I think does this correctly. Look in function IntersectionArea near the bottom. The general approach is to pick off the convex polygon circumscribed by the circle, and then deal with the little circular caps.

Answer 5

If you have a GPU at your disposal, you could use this technique for obtaining a pixel count of the intersection..

Answer 6

My first instinct would be to transform everything so that the circle is centered on origin, trans the triangle to polar coordinates, and solve for the intersection (or encompassment) of the triangle with the circle. I haven't actually worked it through on paper yet though so that's only a hunch.