概要

2点\((x_1, y_1), (x_2, y_2)\)を通る直線と円: 中心\((c_x, c_y)\) 半径\(r\)との交点を計算する。

\(d_x = x_2 - x_1\), \(d_y = y_2 - y_1\)とする。

直線を通る点を \((x, y) = (x_1, y_1) + s(d_x, d_y)\) とした時、\((x - c_x)^2 + (y - c_y)^2 = r^2\) となる \(s\) を求める。

具体的計算

\((x - c_x)^2 + (y - c_y)^2 = r^2\)を変形すると、 \(X = x_1 - c_x\), \(Y = y_1 - c_y\) とした時に、

\((d_x^2 + d_y^2) s^2 -2 (d_x X + d_y Y) s + (X^2 + Y^2 - r^2) = 0\)

が得られるため、この\(s\)の解を計算する。

そして、この\(s\)から交点\((x, y)\)を求める。

実装

AOJ: "CGL_7_D: Circles - Cross Points of a Circle and a Line"で提出した実装のPython3版

from math import sqrt
def solve(cx, cy, r, x1, y1, x2, y2):
    xd = x2 - x1; yd = y2 - y1
    X = x1 - cx; Y = y1 - cy
    a = xd**2 + yd**2
    b = xd * X + yd * Y
    c = X**2 + Y**2 - r**2
    # D = 0の時は1本で、D < 0の時は存在しない
    D = b**2 - a*c
    s1 = (-b + sqrt(D)) / a
    s2 = (-b - sqrt(D)) / a
    return (x1 + xd*s1, y1 + yd*s1), (x1 + xd*s2, y1 + yd*s2)
cx, cy, r = map(int, input().split())
q = int(input())
for i in range(q):
    x1, y1, x2, y2 = map(int, input().split())

    p0, p1 = sorted(solve(cx, cy, r, x1, y1, x2, y2))
    print("%.08f %.08f %.08f %.08f" % (p0 + p1))

Verified

  • AOJ: "CGL_7_D: Circles - Cross Points of a Circle and a Line": source (Python2, 0.01sec)