概要

円1: 中心 \((x_1, y_1)\) 半径 \(r_1\) と 円2: 中心 \((x_2, y_2)\) 半径 \(r_2\) の2つの円がなす共通接線の接点を求める。

(円1の方の)共通内接線(最大2本)と共通外接線(最大2本)の接点を計算する。

もしくは、接線上の2点を求める。

具体的計算

2つの円の中心間の距離を \(r_0\) とし、 \(d_x = x_2 - x_1\), \(d_y = y_2 - y_1\) とした時、接点を

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

この時、

  • 共通内接線の場合は \(\displaystyle |\cos \theta| = \frac{|r_1 - r_2|}{r_0}\)

  • 共通外接線の場合は \(\displaystyle |\cos \theta| = \frac{r_1 + r_2}{r_0}\)

を満たす。(実際に図を書いてみると確認できる)

この時 \(|\cos \theta| > 1\) の場合は接線が存在しない。また、 \(|\cos \theta| = 1\) の場合は接線が1本のみ存在する。

実装(円1の接点)

AOJ: "CGL_7_G: Circles - Common Tangent"で提出した実装のPython3版

x1, y1, r1 = map(int, input().split())
x2, y2, r2 = map(int, input().split())
 
from math import sqrt
 
def solve(x1, y1, r1, x2, y2, r2):
    result = []
    xd = x2 - x1; yd = y2 - y1
 
    rr0 = xd**2 + yd**2
    if (r1 - r2)**2 <= rr0:
        # 共通外接線
        cv = r1 - r2
        if rr0 == (r1 - r2)**2:
            # 円が内接する場合 => 共通外接線は1本
            result.append((x1 + r1*cv*xd/rr0, y1 + r1*cv*yd/rr0))
        else:
            sv = sqrt(rr0 - cv**2)
            # (x1, y1) + r1/r0*R(±θ)(x2 - x1, y2 - y1)
            result.append((x1 + r1*(cv*xd - sv*yd)/rr0, y1 + r1*(sv*xd + cv*yd)/rr0))
            result.append((x1 + r1*(cv*xd + sv*yd)/rr0, y1 + r1*(-sv*xd + cv*yd)/rr0))
    if (r1 + r2)**2 <= rr0:
        # 共通内接線
        cv = r1 + r2
        if rr0 == (r1 + r2)**2:
            # 円が外接する場合 => 共通内接線は1本
            result.append((x1 + r1*cv*xd/rr0, y1 + r1*cv*yd/rr0))
        else:
            sv = sqrt(rr0 - cv**2)
            # (x1, y1) + r1/r0*R(±θ)(x2 - x1, y2 - y1)
            result.append((x1 + r1*(cv*xd - sv*yd)/rr0, y1 + r1*(sv*xd + cv*yd)/rr0))
            result.append((x1 + r1*(cv*xd + sv*yd)/rr0, y1 + r1*(-sv*xd + cv*yd)/rr0))
    return result
 
result = sorted(solve(x1, y1, r1, x2, y2, r2))
if result:
    print("\n".join("%.08f %.08f" % p for p in result))

Verified

  • AOJ: "CGL_7_G: Circles - Common Tangent": source (Python2, 0.01sec)

実装(接線上の2点)

def common_tangent_lines(x1, y1, r1, x2, y2, r2):
    result = []
    xd = x2 - x1; yd = y2 - y1

    rr0 = xd**2 + yd**2
    if (r1 - r2)**2 <= rr0:
        cv = r1 - r2
        if rr0 == (r1 - r2)**2:
            bx = r1*cv*xd/rr0
            by = r1*cv*yd/rr0
            result.append([
                (x1 + bx, y1 + by),
                (x1 - yd + bx, y1 + xd + by),
            ])
        else:
            sv = (rr0 - cv**2)**.5
            px = (cv*xd - sv*yd); py = (sv*xd + cv*yd)
            result.append([
                (x1 + r1*px/rr0, y1 + r1*py/rr0),
                (x2 + r2*px/rr0, y2 + r2*py/rr0),
            ])
            qx = (cv*xd + sv*yd); qy = (-sv*xd + cv*yd)
            result.append([
                (x1 + r1*qx/rr0, y1 + r1*qy/rr0),
                (x2 + r2*qx/rr0, y2 + r2*qy/rr0),
            ])
    if (r1 + r2)**2 <= rr0:
        cv = r1 + r2
        if rr0 == (r1 + r2)**2:
            bx = r1*cv*xd/rr0
            by = r1*cv*yd/rr0
            result.append([
                (x1 + bx, y1 + by),
                (x1 - yd + bx, y1 + xd + by),
            ])
        else:
            sv = (rr0 - cv**2)**.5
            px = (cv*xd - sv*yd); py = (sv*xd + cv*yd)
            result.append([
                (x1 + r1*px/rr0, y1 + r1*py/rr0),
                (x2 - r2*px/rr0, y2 - r2*py/rr0),
            ])
            qx = (cv*xd + sv*yd); qy = (-sv*xd + cv*yd)
            result.append([
                (x1 + r1*qx/rr0, y1 + r1*qy/rr0),
                (x2 - r2*qx/rr0, y2 - r2*qy/rr0),
            ])
    return result

Verified

  • AOJ: "2201: Immortal Jewels": source (Python3, 6.64sec)

戻る