How to define the intersection of three circles?

Given three circles with their center point and 开发者_开发知识库radius, how can you define the area of intersection?

So far what I have is:

var point1 = {x: -3, y: 0};
var point2 = {x: 3, y: 0};
var point3 = {x: 0, y: -3};

var r1 = 5;
var r2 = 5;
var r3 = 5;

var area = returnIntersectionArea(point1, point2, point3, r1, r2, r3);

Also, if two collide but not the third, the function should return null. If none collide, null should be returned.

---

This article describes how to find the area of the intersection between two circles. The result it easily extended to three circles.

-------------EDIT------------- OK, the problem is not easily extended to three circles, I found PhD theses on the subject. Assuming the three circles intersect as shown below, an approximate solution can be found (I think). Before we attempt it, we must check if the three circles indeed intersect as shown below. The problem changes quite a bit if say one circle is inside the other and the third intersects them both.

.

Let S1,S2 and S3 denote the areas of the three circles, and X1,X2 and X3 denote the area of the intersections between each pair of circles (index increases in clockwise direction). As we already established, there are exact formulae for these. Consider the following system of linear equations:

A+D+F+G = A+D+X1 = S1

B+D+E+G = B+D+ X3 = S2

B+E+D+G = B+E+X2 = S3

It is underdetermined, but an approximate solution can be found using least squares. I haven't tried it numerically but will get back to you as soon as I do :D If the least-squares solution seems wrong, we should also impose several constraints, e.g. the area if the intersection between any pair of circles is smaller than the area of the circles. Comments are appreciated.

PS +1 to Simon for pointing out I shouldn't qualify things as easy

---

One way of approaching this problem is via a Monte Carlo simulation:

function returnIntersectionArea(point1, point2, point3, r1, r2, r3) {

  // determine bounding rectangle
  var left   = Math.min(point1.x - r1, point2.x - r2, point3.x - r3);
  var right  = Math.max(point1.x + r1, point2.x + r2, point3.x + r3);
  var top    = Math.min(point1.y - r1, point2.y - r2, point3.y - r3);
  var bottom = Math.max(point1.y + r1, point2.y + r2, point3.y + r3);

  // area of bounding rectangle
  var rectArea = (right - left) * (bottom - top);

  var iterations = 10000;
  var pts = 0;
  for (int i=0; i<iterations; i++) {

    // random point coordinates
    var x = left + Math.rand() * (right - left);
    var y = top  + Math.rand() * (bottom - top);

        // check if it is inside all the three circles (the intersecting area)
    if (Math.sqrt(Math.pow(x - point1.x, 2) + Math.pow(y - point1.y, 2)) <= r1 &&
        Math.sqrt(Math.pow(x - point2.x, 2) + Math.pow(y - point2.y, 2)) <= r2 &&
        Math.sqrt(Math.pow(x - point3.x, 2) + Math.pow(y - point3.y, 2)) <= r3)
      pts++;
  }

  // the ratio of points inside the intersecting area will converge to the ratio
  // of the area of the bounding rectangle and the intersection
  return pts / iterations * rectArea;
}

The solution can be improved to arbitrary precision (within floating-point limits) by increasing the number of iterations, although the rate at which the solution is approached may become slow. Obviously, choosing a tight bounding box is important for achieving good convergence.