概要

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)\) を求める。

この時、 \(0 \le s \le 1\) に制限することで、線分と円の交点を求めることができる。

実装: 直線と円の交点計算

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)

実装: 線分と円の交差判定

\(st\) -平面において \(f(s) = (d_x^2 + d_y^2) s^2 + 2 (d_x X + d_y Y) s + (X^2 + Y^2 - r^2)\) が \(t = 0 (0 \le s \le 1)\) との交差条件(以下のいずれか)を満たすかを判定している。

  1. \(f(0) \ge 0\) かつ \(f(1) \le 0\)

  2. \(f(0) \le 0\) かつ \(f(1) \ge 0\)

  3. \(f(0) > 0\) かつ \(f(1) > 0\) かつ \(f(s)\) が最小値を \(0 \le s \le 1\) で取り、その最小値が 0 以下

def intersection(cx, cy, r, P1, P2):
    x1, y1 = P1; x2, y2 = P2

    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

    f0 = c; f1 = a+2*b+c
    if (f0 >= 0 and f1 <= 0) or (f0 <= 0 and f1 >= 0):
        return True
    return -a <= b <= 0 and b**2 - a*c >= 0 and (f0 >= 0 or f1 >= 0)

print(intersection(2, 0, 1, (-2, 0), (0, 0)))
# => "False"
print(intersection(0, 0, 1, (-2, 0), (0, 0)))
# => "True"
print(intersection(0, 0, 2, (-2, 0), (0, 0)))
# => "True"
print(intersection(0, 0, 3, (-2, 0), (0, 0)))
# => "False"

Verified

  • AOJ: "0129: Hide-and-Seek Supporting System": source (Python3, 0.06sec)

戻る