概要

点\((x_0, y_0)\)と点\((x_1, y_1)\)を通る直線1と点\((x_2, y_2)\)と点\((x_3, y_3)\)を通る直線2の交点を求める。

直線1上の点\((x, y) = (x_0, y_0) + s(x_1 - x_0, y_1 - y_0)\)の中で、直線2と交わる時の\(s\)を計算して交点を求める。

線分同士の交点を計算する場合、線分の交差判定を行った上で直線とみなして交点を計算すればよい。

具体的計算

\(d_{x0} = x_1 - x_0\), \(d_{y0} = y_1 - y_0\), \(d_{x1} = x_3 - x_2\), \(d_{y1} = y_3 - y_2\) とした時、

\(\displaystyle s = \frac{(y_0 - y_2) d_{x1} - (x_0 - x_2) d_{x1}}{d_{x0} d_{y1} - d_{y0} d_{x1}}\)

を満たす。

実装

AOJ: "CGL_2_C: Segments/Lines - Cross Point"の実装

def solve(x0, y0, x1, y1, x2, y2, x3, y3):
    dx0 = x1 - x0
    dy0 = y1 - y0
    dx1 = x3 - x2
    dy1 = y3 - y2

    s = (y0-y2)*dx1 - (x0-x2)*dy1
    sm = dx0*dy1 - dy0*dx1
    if s < 0:
        s = -s
        sm = -sm
    if s == 0:
        x = x0
        y = y0
    else:
        x = x0 + s*dx0/sm
        y = y0 + s*dy0/sm
    return x, y

for t in range(int(input())):
    print("%.09f %.09f" % solve(*map(int, input().split())))

Verified

  • AOJ: "CGL_2_C: Segments/Lines - Cross Point": source (Python3, 0.04sec)