Как определить пересечение трех кругов? - PullRequest
Новая
       1

Как определить пересечение трех кругов?

3 голосов
/ 23 апреля 2011

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

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

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

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

Ответы [ 2 ]

3 голосов
/ 23 апреля 2011

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

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

three circles.

Пусть 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 Саймону за то, что он указал, что я не должен квалифицировать вещи так просто

1 голос
/ 02 мая 2011

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

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

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

...