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

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

Assuming you're talking integer pixels, not real, the naive implementation would be to loop through every pixel of the triangle and check the distance from the circle's center against its radius.

It's not a cute formula, or particularly fast, but it does get the job done.

Answer 2

try computational geometry

Note: this is not a trivial problem, I hope it's not homework ;-)

Answer 3

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 4

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

Answer 5

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 6

I think you shouldn't approximate circle as some set of triangles, instead of that you can approximate it's shape with a polygon. The naive algorithm can look like:

1. Convert you circle to polygon with some desired number of vertices.
2. Calculate the intersection of two polygons (converted circle and a triangle).
3. Calculate square of that intersection.

You can optimize this algorithm by combining step 2 and step 3 into single function.

Read this links:
Area of convex polygon
Intersection of convex polygons

Answer 7

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.

Answer 8

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 9

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):

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

Answer 10

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.