Точки пересечения окружности

Ответ 1

Пересечение двух кругов

Автор Paul Bourke

В следующем примечании описывается, как найти точку (точки) пересечения между двумя кругами на плоскости используются следующие обозначения. Цель состоит в том, чтобы найти две точки P ₃= (x ₃, y ₃), если они существуют.

Сначала вычислите расстояние d между центром кругов. d = || P ₁ - P ₀ ||.

• Если d > r ₀ + r ₁, то нет решений, круги являются отдельными.

• Если d < | r ₀ - г <к югу > 1суб > | то решений нет, потому что один круг содержащихся внутри другого.

• Если d = 0 и r ₀ = r ₁, то круги совпадают и существуют бесконечное число решений.

Учитывая два треугольника P ₀ P ₂ P ₃и P ₁ P ₂ P ₃ мы можем написать

a ² + h ²= r ₀ ² и b ² + h ²= r ₁ ²

Используя d = a + b, мы можем решить для a,

a = (r ₀ ² - r ₁ ² + d ²)/(2 d)

 Нетрудно показать, что это сводится к r ₀, когда два круга касаются одной точки, т.е. d = r ₀ + r ₁  Решите для h, подставив a в первый уравнение, h ²= r ₀ ² - a ²

So

P ₂= P ₀ + a (P ₁ - P ₀)/d

И, наконец, P ₃ = (x ₃, y ₃) в терминах P ₀ = (x ₀, y ₀), P ₁ = (x ₁, y ₁) и P ₂ = (x ₂, y ₂),

x ₃ = x ₂ + - h (y ₁ - y ₀)/d

y ₃= y ₂ - + h (x ₁ - x ₀)/ д

Источник: http://paulbourke.net/geometry/circlesphere/

Ответ 2

Вот моя реализация на С++, основанная на статье Paul Bourke. Он работает только в том случае, если есть два пересечения, иначе он, вероятно, вернет NaN NAN NAN NAN.

class Point{
    public:
        float x, y;
        Point(float px, float py) {
            x = px;
            y = py;
        }
        Point sub(Point p2) {
            return Point(x - p2.x, y - p2.y);
        }
        Point add(Point p2) {
            return Point(x + p2.x, y + p2.y);
        }
        float distance(Point p2) {
            return sqrt((x - p2.x)*(x - p2.x) + (y - p2.y)*(y - p2.y));
        }
        Point normal() {
            float length = sqrt(x*x + y*y);
            return Point(x/length, y/length);
        }
        Point scale(float s) {
            return Point(x*s, y*s);
        }
};

class Circle {
    public:
        float x, y, r, left;
        Circle(float cx, float cy, float cr) {
            x = cx;
            y = cy;
            r = cr;
            left = x - r;
        }
        pair<Point, Point> intersections(Circle c) {
            Point P0(x, y);
            Point P1(c.x, c.y);
            float d, a, h;
            d = P0.distance(P1);
            a = (r*r - c.r*c.r + d*d)/(2*d);
            h = sqrt(r*r - a*a);
            Point P2 = P1.sub(P0).scale(a/d).add(P0);
            float x3, y3, x4, y4;
            x3 = P2.x + h*(P1.y - P0.y)/d;
            y3 = P2.y - h*(P1.x - P0.x)/d;
            x4 = P2.x - h*(P1.y - P0.y)/d;
            y4 = P2.y + h*(P1.x - P0.x)/d;

            return pair<Point, Point>(Point(x3, y3), Point(x4, y4));
        }

};

Ответ 3

Почему бы просто не использовать 7 строк вашего любимого процедурного языка (или программируемого калькулятора!), как показано ниже.

Предполагая, что вам даны P0-коорды (x0, y0), P1-коорды (x1, y1), r0 и r1, и вы хотите найти P3-коорды (x3, y3):

d=sqr((x1-x0)^2 + (y1-y0)^2)
a=(r0^2-r1^2+d^2)/(2*d)
h=sqr(r0^2-a^2)
x2=x0+a*(x1-x0)/d   
y2=y0+a*(y1-y0)/d   
x3=x2+h*(y1-y0)/d       // also x3=x2-h*(y1-y0)/d
y3=y2-h*(x1-x0)/d       // also y3=y2+h*(x1-x0)/d

Ответ 4

Вот реализация в Javascript с использованием векторов. Код хорошо документирован, вы сможете следить за ним. Здесь исходный источник

Смотрите живое демо здесь:

// Let EPS (epsilon) be a small value
var EPS = 0.0000001;

// Let a point be a pair: (x, y)
function Point(x, y) {
  this.x = x;
  this.y = y;
}

// Define a circle centered at (x,y) with radius r
function Circle(x,y,r) {
  this.x = x;
  this.y = y;
  this.r = r;
}

// Due to double rounding precision the value passed into the Math.acos
// function may be outside its domain of [-1, +1] which would return
// the value NaN which we do not want.
function acossafe(x) {
  if (x >= +1.0) return 0;
  if (x <= -1.0) return Math.PI;
  return Math.acos(x);
}

// Rotates a point about a fixed point at some angle 'a'
function rotatePoint(fp, pt, a) {
  var x = pt.x - fp.x;
  var y = pt.y - fp.y;
  var xRot = x * Math.cos(a) + y * Math.sin(a);
  var yRot = y * Math.cos(a) - x * Math.sin(a);
  return new Point(fp.x+xRot,fp.y+yRot);
}

// Given two circles this method finds the intersection
// point(s) of the two circles (if any exists)
function circleCircleIntersectionPoints(c1, c2) {

  var r, R, d, dx, dy, cx, cy, Cx, Cy;

  if (c1.r < c2.r) {
    r  = c1.r;  R = c2.r;
    cx = c1.x; cy = c1.y;
    Cx = c2.x; Cy = c2.y;
  } else {
    r  = c2.r; R  = c1.r;
    Cx = c1.x; Cy = c1.y;
    cx = c2.x; cy = c2.y;
  }

  // Compute the vector <dx, dy>
  dx = cx - Cx;
  dy = cy - Cy;

  // Find the distance between two points.
  d = Math.sqrt( dx*dx + dy*dy );

  // There are an infinite number of solutions
  // Seems appropriate to also return null
  if (d < EPS && Math.abs(R-r) < EPS) return [];

  // No intersection (circles centered at the 
  // same place with different size)
  else if (d < EPS) return [];

  var x = (dx / d) * R + Cx;
  var y = (dy / d) * R + Cy;
  var P = new Point(x, y);

  // Single intersection (kissing circles)
  if (Math.abs((R+r)-d) < EPS || Math.abs(R-(r+d)) < EPS) return [P];

  // No intersection. Either the small circle contained within 
  // big circle or circles are simply disjoint.
  if ( (d+r) < R || (R+r < d) ) return [];

  var C = new Point(Cx, Cy);
  var angle = acossafe((r*r-d*d-R*R)/(-2.0*d*R));
  var pt1 = rotatePoint(C, P, +angle);
  var pt2 = rotatePoint(C, P, -angle);
  return [pt1, pt2];

}