概要

円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\)の回転行列)

実装

AOJ: "CGL_7_E: Circles - Cross Points of Circles"で提出した実装のPython3版

from math import sqrt
x1, y1, r1 = map(int, input().split())
x2, y2, r2 = map(int, input().split())

def solve(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 = sqrt(4*rr0*rr1 - cv**2)
    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)),
    )

p0, p1 = sorted(solve(x1, y1, r1, x2, y2, r2))
print("%.08f %.08f %.08f %.08f" % (p0 + p1))

Verified

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