概要

円1: 中心\((x_1, y_1)\) 半径\(r_1\) と 円2: 中心\((x_2, y_2)\) 半径\(r_2\) の2つの円について交点を計算する。

円1と円の交点のうちの1点がなす角\(\theta\)の \(\cos \theta\) と \(\sin \theta\) の値を計算し、交点の座標を求める。

具体的計算

2つの円の中心同士の距離を\(r_0\)とし、なす角\(\theta\)を計算

  • \(\displaystyle \cos \theta = \frac{r_0^2 + r_1^2 - r_2^2}{2 r_0 r_1}\)

  • \(\displaystyle \sin \theta = \sqrt{1 - \cos^2 \theta} = \frac{\sqrt{4 r_0^2 r_1^2 - (r_0^2 + r_1^2 - r_2^2)^2}}{2 r_0 r_1}\)

そして、\(d_x = x_2 - x_1\), \(d_y = y_2 - y_1\) とすると、2つの交点は、

  • \(\displaystyle \left( \begin{array}{c} x_1 \\ y_2 \end{array} \right) + \frac{r_1}{r_0} R(\theta) \left( \begin{array}{c} d_x \\ d_y \end{array} \right)\)

  • \(\displaystyle \left( \begin{array}{c} x_1 \\ y_2 \end{array} \right) + \frac{r_1}{r_0} R(-\theta) \left( \begin{array}{c} d_x \\ d_y \end{array} \right)\)

で計算できる (\(R(\theta)\)は\(2 \times 2\)の回転行列)

頂点から円への接点の計算

応用で 中心 \((x_1, y_1)\) 半径 \(r_1\) に対する、点 \((x_2, y_2)\) から引いた接線がなす接点を計算できる。

2点 \((x_1, y_1)\) と \((x_2, y_2)\) の距離を \(r_0\) とする時、

この接点は 中心 \((x_1, y_1)\) 半径 \(r_1\) と 中心\((x_2, y_2)\) 半径 \(\sqrt{r_0^2 - r_1^2}\) の交点を計算することで求まる。

実装

# the crossing points of two circles
def circles_cross_points(x1, y1, r1, x2, y2, r2):
    rr0 = (x2 - x1)**2 + (y2 - y1)**2
    xd = x2 - x1
    yd = y2 - y1
    rr1 = r1**2; rr2 = r2**2
    cv = (rr0 + rr1 - rr2)
    sv = (4*rr0*rr1 - cv**2)**.5
    return (
        (x1 + (cv*xd - sv*yd)/(2.*rr0), y1 + (cv*yd + sv*xd)/(2.*rr0)),
        (x1 + (cv*xd + sv*yd)/(2.*rr0), y1 + (cv*yd - sv*xd)/(2.*rr0)),
    )

# tangent points on a circle (x1, y1, r1) from a point (x2, y2)
def circle_tangent_points(x1, y1, r1, x2, y2):
    dd = (x1 - x2)**2 + (y1 - y2)**2
    r2 = (dd - r1**2)**.5
    return circles_cross_points(x1, y1, r1, x2, y2, r2)

p0, p1 = circles_cross_points(0, 0, 10, 6, 5, 10)
print("(%.4f, %.4f) (%.4f, %.4f)" % (p0 + p1))
# => "(-2.8935, 9.5722) (8.8935, -4.5722)"

p0, p1 = circle_tangent_points(0, 0, 10, 20, 15)
print("(%.4f, %.4f) (%.4f, %.4f)" % (p0 + p1))
# => "(-2.2991, 9.7321) (8.6991, -4.9321)"

Verified

  • AOJ: "CGL_7_E: Circles - Cross Points of Circles": source (Python2, 0.01sec)

  • AOJ: "2697: Runner and Sniper": source (Python3, 0.03sec)