area of intersection between circle and rectangle

Question

i'm looking for a fast way to determine the area of intersection between a rectangle and a circle (I need to do millions of these calculations)

A specific property is that in all cases the circle and rectangle always have 2 points of intersection.

Java lib would be awesome!

Thanks, Britske

Answer 1

Perhaps you can use the answer to this question, where the area of intersection between a circle and a triangle is asked. Split your rectangle into two triangles and use the algorithms described there.

Another way is to draw a line between the two intersection points, this splits your area into a polygon (3 or 4 edges) and a circular segment, for both you should be able to find libraries easier or do the calculations yourself.

Answer 2

Given 2 points of intersection:

0 vertices is inside the circle: The area of a circular segment

    XXXXX              -------------------
   X     X               X            X Circular segment
  X       X               XX        XX 
+-X-------X--+              XXXXXXXX 
|  X     X   |
|   XXXXX    |

1 vertex is inside the circle: The sum of the areas of a circular segment and a triangle.

    XXXXX                   XXXXXXXXX
   X     X       Triangle ->X     _-X
  X       X                 X   _-  X 
  X    +--X--+              X _-   X <- Circular segment 
   X   | X   |              X-  XXX 
    XXXXX    |              XXXX
       |     |

2 vertices are inside the circle: The sum of the area of two triangles and a circular segment

    XXXXX                   +------------X
   X     X                  |      _--'/'X 
  X    +--X---    Triangle->|   _--   / X
  X    |  X                 |_--     /XX <- Circular segment
   X   +-X----              +-------XX
    XXXXX                 Triangle^

3 vertices are inside the circle: The area of the rectangle minus the area of a triangle plus the area of a circular segment

    XXXXX
   X  +--X+             XXX
  X   |   X         -------XXX-----+ <- Triangle outside
 X    |   |X        Rect ''.  XXX  |
 X    +---+X                ''.  XX|  
 X         X                   ''. X <- Circular segment inside 
  X       X                       ^|X 
   X     X                         | X 
    XXXXX

To calculate these areas:

• Most of the points you'll need to use can be found by finding the intersection of a line and a circle

• The areas you need to compute can be found by computing the area of a circular segment and computing the area of a triangle.

• You can determine if a vertex is inside the circle by calculating if its distance from the center is less than the radius.

Answer 3

Thanks for the answers,

I forgot to mention that area estimatations were enough. That; s why in the end, after looking at all the options, I went with monte-carlo estimation where I generate random points in the circle and test if they're in the box.

In my case this is likely more performant. (I have a grid placed over the circle and I have to measure the ratio of the circle belonging to each of the grid-cells. )

Thanks

Answer 4

Here is another solution for the problem:

public static bool IsIntersected(PointF circle, float radius, RectangleF rectangle) {

        var rectangleCenter = new PointF((rectangle.X +  rectangle.Width / 2),
                                         (rectangle.Y + rectangle.Height / 2));

        var w = rectangle.Width  / 2;
        var h = rectangle.Height / 2;

        var dx = Math.Abs(circle.X - rectangleCenter.X);
        var dy = Math.Abs(circle.Y - rectangleCenter.Y);

        if (dx > (radius + w) || dy > (radius + h)) return false;


        var circleDistance = new PointF
                                 {
                                     X = Math.Abs(circle.X - rectangle.X - w),
                                     Y = Math.Abs(circle.Y - rectangle.Y - h)
                                 };


        if (circleDistance.X <= (w))
        {
            return true;
        }

        if (circleDistance.Y <= (h))
        {
            return true;
        }

        var cornerDistanceSq = Math.Pow(circleDistance.X - w, 2) + 
                    Math.Pow(circleDistance.Y - h, 2);

        return (cornerDistanceSq <= (Math.Pow(radius, 2)));
    }

Bassam Alugili