javascript - How to define the intersection of three circles? - Stack Overflow

admin管理员组

文章数量:1429064

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.

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.

• javascript
• formula

Share Improve this question Follow asked Apr 22, 2011 at 22:13 nagymaflanagymafla 26755 silver badges1111 bronze badges 4

• 3 This is less a programming question and more of a geometry/trig question so I suggest you try math.stackexchange. – Chris Cherry Commented Apr 22, 2011 at 22:19
• Thank you! I wanted to know what are the different javascript specific solutions as this script is a part of a javascript project. – nagymafla Commented Apr 22, 2011 at 22:24
• What if each circle overlaps with one other, but there is no point inside all three circles? Does that count as three colliding or not? – Simon G. Commented Apr 22, 2011 at 22:33
• Yes it does. If the three circles are not the same sized in pairs, then the intersection is the smallest circle in the middle. Otherwise, as always, it's the "mon part" of the three circles. – nagymafla Commented Apr 22, 2011 at 22:42

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 3

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 bee slow. Obviously, choosing a tight bounding box is important for achieving good convergence.

本文标签： javascriptHow to define the intersection of three circlesStack Overflow