Блог

Учитывая три окружности с их центральной точкой и радиусом, как вы можете определить область пересечения?

Пока что у меня есть:

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

Кроме того, если две окружности сталкиваются, но не третья, функция должна возвращать значение null.
Если ни один из них не сталкивается, должен быть возвращен null.

В этой статье описывается, как найти площадь пересечения между двумя окружностями. В результате он легко расширился до трех окружностей.

————-РЕДАКТИРОВАТЬ————- Хорошо, проблему нелегко распространить на три круга, я нашел кандидатские диссертации на эту тему. Предполагая, что три окружности пересекаются, как показано ниже, приблизительное решение может быть найдено (я думаю). Прежде чем мы попытаемся это сделать, мы должны проверить, действительно ли три круга пересекаются, как показано ниже. Проблема немного меняется, если, скажем, один круг находится внутри другого, а третий пересекает их оба.

.

Пусть S1, S2 и S3 обозначают площади трех окружностей, а X1, X2 и X3 обозначают площадь пересечений между каждой парой окружностей (индекс увеличивается по часовой стрелке). Как мы уже установили, для них существуют точные формулы. Рассмотрим следующую систему линейных уравнений:

A D F G = A D X1 = S1

B D E G = B D X3 = S2

B E D G = B E X2 = S3

Это недоопределено, но приблизительное решение может быть найдено с использованием метода наименьших квадратов. Я не пробовал это численно, но вернусь к вам, как только сделаю: D Если решение методом наименьших квадратов кажется неправильным, мы также должны наложить несколько ограничений, например, площадь, если пересечение между любой парой окружностей меньше площади окружностей. Комментарии приветствуются.

PS 1 Саймону за указание на то, что я не должен квалифицировать вещи как простые

Одним из способов решения этой проблемы является моделирование с помощью метода Монте-Карло:

 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 amp;amp;
        Math.sqrt(Math.pow(x - point2.x, 2)   Math.pow(y - point2.y, 2)) <= r2 amp;amp;
        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;
}
  

Решение может быть улучшено до произвольной точности (в пределах значений с плавающей запятой) путем увеличения числа итераций, хотя скорость, с которой приближается решение, может стать медленной. Очевидно, что выбор жесткой ограничивающей рамки важен для достижения хорошей сходимости.