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

Answer 1

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.