Line
(Geometric/Line.py)

• View this file on GitHub
• Last update: 2025-03-01 16:16:33+09:00

Theory

線分, 半直線, 直線の定義

$\mathrm{A}, \mathrm{B}$ を相異なる2点とする.

• $\mathrm{A}, \mathrm{B}$ を端点とする線分 (Segment) $s$ は以下のようにして定義される.

\[s:=\{t \mathrm{A}+(1-t) \mathrm{B} \mid 0 \leq t \leq 1\}\]

• $\mathrm{A}$ を端点とし, $\mathrm{B}$ を通る半直線 (Ray) $r$ は以下のようにして定義される.

\[r:=\{t \mathrm{A}+(1-t) \mathrm{B} \mid 0 \leq t\}\]

• $\mathrm{A}, \mathrm{B}$ を通る直線 (Line) $\ell$ は以下のようにして定義される.

\[\ell:=\{t \mathrm{A}+(1-t) \mathrm{B} \mid t \in \mathbb{R} \}\]

どの場合でも $\overrightarrow{\mathrm{AB}}$ が方向ベクトルになる.

線分, 半直線, 直線上の点かの判定

$\mathrm{A}, \mathrm{B}$ を相異なる2点とする. $\mathrm{P}$ が線分, 半直線, 直線上の点であるかの判定をする. これは3点の位置関係を利用することが出来る.

• $s$ を $\mathrm{A}, \mathrm{B}$ を端点とする線分とする. $\mathrm{P}$ が $s$ 上の点であることの判定は3点の位置関係でそのまま判定できる.
• $r$ を $\mathrm{A}$ を端点とし, $\mathrm{B}$ を通る半直線とする. $\mathrm{P}$ が $r$ 上の点であることの必要十分条件は以下のうちのどちらか一方が成り立つことである.
  • $\mathrm{P}$ が線分 $\mathrm{AB}$ 上の点である.
  • $\mathrm{B}$ が線分 $\mathrm{AP}$ 上の点である.
• $\ell$ を $\mathrm{A}, \mathrm{B}$ を通る直線とする. $\mathrm{P}$ が $\ell$ 上の点であることの必要十分条件は以下である.
  • $\mathrm{P}$ が線分 $\mathrm{AB}$ 上の点である.
  • $\mathrm{B}$ が線分 $\mathrm{AP}$ 上の点である.
  • $\mathrm{A}$ が線分 $\mathrm{BP}$ 上の点である.

なお, $\mathrm{P}$ が $\ell$ 上の点の判定についてはよくみると $\mathrm{iSP}$ が $\pm 1$ でないことと同値であるから, これは以下のように帰着である.

\[\mathrm{P} \in \ell \iff \overrightarrow{\mathrm{PA}} \times \overrightarrow{\mathrm{PB}}=0\]

2直線 (線分) の関係性

直線 (線分) $\ell ,m$ をそれぞれ以下のようにする.

• $\ell$ : 点 $\mathrm{A}, \mathrm{B}$ を通る直線 (を端点とする線分).
• $m$ : 点 $\mathrm{C}, \mathrm{D}$ を通る直線 (を端点とする線分).

このとき, 以下が成り立つ.

• $l,m$ が平行 (または一致) $\iff \overrightarrow{\mathrm{AB}} \times \overrightarrow{\mathrm{CD}}=0$
• $l,m$ が (共有点を持つならば) 直交 $\iff \overrightarrow{\mathrm{AB}} \cdot \overrightarrow{\mathrm{CD}}=0$

線分と線分の交差判定

直線と直線の交差判定

2つの直線 $\ell, m$ はそれぞれ次のようになっているとする.

• $\ell$ : 点 $\mathrm{A}$ を通り, 方向ベクトルが $\boldsymbol{u}$ である.
• $m$ : 点 $\mathrm{B}$ を通り, 方向ベクトルが $\boldsymbol{v}$ であるとする.

このとき, $\ell, m$ の関係は交差, 平行 (かつ 非一致), 一致のどれかである.

• 一致 $\iff \boldsymbol{u} \times \boldsymbol{v}=0$ かつ $\mathrm{B} \in \ell$
• 平行かつ不一致 $\iff \boldsymbol{u} \times \boldsymbol{v}=0$ かつ $\mathrm{B} \not \in \ell$
• 交差 $\iff \boldsymbol{u} \times \boldsymbol{v} \neq 0$

直線と直線の交点

以下, 2つの直線 $\ell, m$ 交差するとする. このとき, 交点は唯一存在する.

このことから, 線分と半直線の交点のような場合でも交点が存在する場合, 両者を直線に拡張して直線同士の交点を求めれば, その点がそのまま元問題の交点にもなる.

直線 $\mathrm{H}$ は次のようにして求められる.

$\ell,m$ をそれぞれ次のようにする.

• $\ell$ : 2点 $\mathrm{A}, \mathrm{B}$ を通る直線.
• $m$ : 2点 $\mathrm{C}, \mathrm{D}$ を通る直線.

このとき, 次のようにして点 $\mathrm{E}, \mathrm{F}$ を定める.

• $\mathrm{E}$ : 次の2つの直線の交点
  • $\mathrm{A}$ を通り, $m$ と平行な直線
  • $\mathrm{C}$ を通り, $\overrightarrow{\mathrm{AD}}$ と平行な直線
• $\mathrm{F}$ : 次の2つの直線の交点
  • $\mathrm{B}$ を通り, $m$ と平行な直線
  • $\mathrm{E}$ を通り, $l$ と平行な直線

このとき, $\mathrm{CE} \parallel \mathrm{AD}, \mathrm{AE} \parallel \mathrm{CD}$ であるから, 四角形 $\mathrm{AECD}$ は平行四辺形である. 同様にして, $\mathrm{AE} \parallel \mathrm{BF}, \mathrm{EF} \parallel \mathrm{AB}$ であるから, 四角形 $\mathrm{AEFB}$ も平行四辺形である.

よって, $\overrightarrow{\mathrm{AE}}=\overrightarrow{\mathrm{DC}}, \overrightarrow{\mathrm{AE}}=\overrightarrow{\mathrm{BF}}$ が導ける.

また, 平行四辺形 $\mathrm{AECD}, \mathrm{AEFB}$ は辺 $\mathrm{AE}$ を共有しているので, この2つの平行四辺形の面積を $S,T$ とすると, ある線分 $\mathrm{AB}$ 上の点 $\mathrm{G}$ が存在して,

\[S:T=\mathrm{AG} : \mathrm{GB} \cdots (\spadesuit)\]

が成り立つ. そして, 3つの直線 $\mathrm{AE}, \mathrm{CD} (=m), \mathrm{BF}$ は互いに平行であるから, この $\mathrm{G}$ は直線 $\mathrm{CD} (=m)$ 上の点でもある.

よって, この点 $\mathrm{G}$ が直線 $l,m$ の交点であり,$(\spadesuit)$ および, $S,T$ が平行四辺形の面積であることから, $k$ を

\[k:=\dfrac{S}{T}=\dfrac{\overrightarrow{\mathrm{AE}} \times \overrightarrow{\mathrm{AD}}}{\overrightarrow{\mathrm{AE}} \times \overrightarrow{\mathrm{AB}}}=\dfrac{\overrightarrow{\mathrm{DC}} \times \overrightarrow{\mathrm{AD}}}{\overrightarrow{\mathrm{DC}} \times \overrightarrow{\mathrm{AB}}}=\dfrac{\overrightarrow{\mathrm{AD}} \times \overrightarrow{\mathrm{CD}}}{\overrightarrow{\mathrm{AB}} \times \overrightarrow{\mathrm{CD}}}\]

とすると, 点 $\mathrm{G}$ は線分 $\mathrm{AB}$ を $k:(1-k)$ に内分する点である.

射影

点 $\mathrm{P}$ の直線 $\ell$ への射影 $\mathrm{H}$ を求める. $\ell$ は2点 $\mathrm{A}, \mathrm{B}$ を通る直線とする. $\theta:=\angle \mathrm{PAB}$ とする. このとき,

\[\overrightarrow{\mathrm{AP}} \cdot \overrightarrow{\mathrm{AB}}=\left \lvert \overrightarrow{\mathrm{AP}} \right \rvert \left \lvert \overrightarrow{\mathrm{AB}} \right \rvert \cos \theta\]

である.

ここで, $\mathrm{H}$ は $\mathrm{P}$ の $\ell$ への射影であるから, $\mathrm{PH}$ と $\ell$ は直交する. そして, $\mathrm{H}$ は $\ell$ 上の点であるから, 直角三角形 $\mathrm{AHP}$ を考えることにより,

\[\left \lvert \overrightarrow{\mathrm{AH}} \right \rvert=\left \lvert \overrightarrow{\mathrm{AP}} \right \rvert \cos \theta\]

となる.

以上から,

\[\left \lvert \overrightarrow{\mathrm{AH}} \right \rvert=\dfrac{\overrightarrow{\mathrm{AP}} \cdot \overrightarrow{\mathrm{AB}}}{\left \lvert \overrightarrow{\mathrm{AB}} \right \rvert}\]

となり,

\[\overrightarrow{\mathrm{OH}}=\overrightarrow{\mathrm{OA}}+\dfrac{\left \lvert \overrightarrow{\mathrm{AH}}\right \rvert}{\left \lvert \overrightarrow{\mathrm{AB}}\right \rvert} \overrightarrow{\mathrm{AB}}=\overrightarrow{\mathrm{OA}}+\dfrac{\overrightarrow{\mathrm{AP}} \cdot \overrightarrow{\mathrm{AB}}}{\left \lvert \overrightarrow{\mathrm{AB}} \right \rvert^2}\overrightarrow{\mathrm{AB}}\]

が得られる.

反射

点 $\mathrm{P}$ を直線 $\ell$ に関して対称移動させた点を $\mathrm{P}’$ とする. このとき, $\mathrm{P}’$ は $\mathrm{P}$ の $\ell$ への射影を $\mathrm{H}$ とすると,

\[\overrightarrow{\mathrm{OP}'}=\overrightarrow{\mathrm{OP}}+2\overrightarrow{\mathrm{PH}}\]

を満たす.

Code

from Point import *

class Segment():
    __slots__=["begin","end","id"]

    def __init__(self,P,Q):
        """2点 P, Q (P!=Q) を端点とする線分を生成する.

        P,Q: Point
        """
        assert P!=Q
        self.begin=P
        self.end=Q
        self.id=2

    def __str__(self):
        return "[Segment] {}, {}".format(self.begin,self.end)

    __repr__=__str__

    def __eq__(self,other):
        return (
            (self.begin==other.begin) and (self.end==other.end) or
            (self.begin==other.end) and (self.end==other.begin)
            )

    def __contains__(self,point):
        return (self.begin==point) or (self.end==point) or (iSP(self.begin,self.end,point)==0)

    def vectorize(self):
        return self.end-self.begin

    def counter_vectorize(self):
        return self.begin-self.end

class Ray():
    __slots__=["begin","end","id"]

    def __init__(self,P,Q):
        """ P を端点とし, Q を通る半直線を通る.

        P,Q: Point
        """
        assert P!=Q
        self.begin=P
        self.end=Q
        self.id=3

    def __str__(self):
        return "[Ray] {} -> {}".format(self.begin,self.end)

    __repr__=__str__

    def __eq__(self,other):
        if self.begin!=other.begin:
            return False

        m=iSP(self.begin,self.end,other.end)
        return m==0 or m==2

    def __contains__(self,point):
        m=iSP(self.begin,self.end,point)
        return m==0 or m==2

    def vectorize(self):
        return self.end-self.begin

    def counter_vectorize(self):
        return self.begin-self.end

class Line:
    __slots__ = ("begin", "end")

    def __init__(self, P: Point, Q: Point):
        """ 2 点 P, Q を通る直線を生成する.

        Args:
            P (Point): 始点
            Q (Point): 終点
        """
        assert P != Q
        self.begin = P
        self.end = Q

    def __str__(self) -> str:
        return f"[Line] {self.begin}, {self.end}"

    def __repr__(self) -> str:
        return f"{self.__class__.__name__}({repr(self.begin)}, {repr(self.end)})"

    def __iter__(self):
        yield self.begin
        yield self.end

    def __eq__(self, other: "Line") -> bool:
        return (other.bein in self) and (other.end in self)

    def __contains__(self, point: Point) -> bool:
        return abs(iSP(self.begin, point, self.end)) != 1

    def vectorize(self) -> Point:
        """ この直線の方向ベクトルを求める.

        Returns:
            Point: 方向ベクトル
        """

        return self.end - self.begin

    def counter_vectorize(self) -> Point:
        return self.begin - self.end

#=== 生成
def Line_from_General_Form(a,b,c):
    """ ax+by+c=0 という形の直線を生成する.

    a,b,c: int or float ((a,b) neq (0,0))
    """

    assert (a!=0) or (b!=0)

    k=sqrt(a*a+b*b)

    if b==0:
        x=-c/a; y=0
    else:
        x=0; y=-c/b

    return Line(Point(x,y),Point(x-b/k, y+a/k))

#=== 一般形
def General_Form_from_Line(L, lattice=False):
    """ 直線 L が満たす式 ax+by+c=0 の a,b,c を求める.
    """

    s=L.begin.x; t=L.begin.y
    v=L.vectorize(); alpha=v.x; beta=v.y

    sgn=compare(beta,0)
    if sgn==0:
        sgn=compare(-alpha,0)

    k=alpha*t-beta*s
    if lattice:
        g=gcd(gcd(alpha,beta),k)
        alpha//=g; beta//=g; k//=g

    return (sgn*beta,sgn*(-alpha),sgn*k)

#=== 交差判定
def has_Intersection_between_Segment_and_Segment(L,M,endpoint=True):
    """ 線分 L,M が交わるかどうかを判定する.

    L,M: 直線
    """

    a=L.begin; b=L.end; c=M.begin; d=M.end
    if not(iSP(a,b,c)*iSP(a,b,d)<=0 and iSP(c,d,a)*iSP(c,d,b)<=0):
        return False

    if endpoint:
        return True

def has_Intersection_between_Line_and_Segment(L,M,endpoint=True):
    """ 直線 L と線分 M が交わるかどうかを判定する.

    L: 直線
    M: 線分
    """

    a=L.begin; b=L.end; c=M.begin; d=M.end
    return iSP(a,b,c)*iSP(a,b,d)<=0

def has_Intersection_between_Line_and_Line(L,M):
    """ 直線 L,M が交わるかどうかを判定する.

    L,M: 直線
    """

    return not equal(L.vectorize().det(M.vectorize()), 0)

#=== 交点を求める
def Intersection_between_Line_and_Line(L,M,Mode=False):
    """ 直線 L,M の交点を求める.

    L,M: 直線
    Mode=False: 交点が一意に定まらない場合エラーを吐く.
    Mode=True: 一致する場合, True, 交点が存在しない場合 False を返す.
    """

    if L==M:
        if Mode:
            return True
        else:
            assert 0,"直線が一致します"
    if is_Parallel(L,M):
        if Mode:
            return False
        else:
            assert 0,"交点が存在ません"

    a=L.begin; b=L.end; c=M.begin; d=M.end
    k=(d-a).det(d-c)/(b-a).det(d-c)
    return a+k*(b-a)

#=== 垂直二等分線
def Perpendicular_Bisector(S, lattice=False):
    """ 線分 S の垂直二等分線を求める."""

    u=S.vectorize()

    M=S.begin+S.end
    if lattice:
        M.x//=2; M.y//=2
    else:
        M.x/=2; M.y/=2
    return Line(M,M+u*Point(0,1))

#=== 2直線の関係
def is_Parallel(L,M):
    """2つの直線 (線分) L,M が平行かどうかを判定する.

    L,M: 直線 or 線分
    """

    u=L.vectorize(); v=M.vectorize()
    return equal(u.det(v), 0)

def is_Orthogonal(L,M):
    """2つの直線 (線分) L,M が直行するかどうかを判定する.

    L,M: 直線 or 線分
    """

    u=L.vectorize(); v=M.vectorize()
    return equal(u.dot(v), 0)

#=== 点との距離
def Distance_between_Point_and_Segment(P,L):
    """ 点 P と線分 L の距離を求める.

    """

    A=L.begin; B=L.end
    if Angle_Type(P,A,B)==-1:
        return abs(P-A)
    elif Angle_Type(P,B,A)==-1:
        return abs(P-B)
    else:
        v=L.vectorize()
        return abs((P-L.begin).det(v)/abs(v))

def Distance_between_Point_and_Line(P,L):
    """ 点 P と直線 L の距離を求める.

    """

    v=L.vectorize()
    return abs((P-L.begin).det(v)/abs(v))

#=== 線同士の距離
def Distance_between_Line_and_Line(L,M):
    """ 2直線 L,M の距離を求める.

    L,M: 直線
    """

    if is_Parallel(L,M):
        return Distance_between_Point_and_Line(L.begin,M)
    else:
        return 0

def Distance_between_Line_and_Segment(L,M):
    """ 直線 L と線分 M の距離を求める.

    L: 直線, M: 線分
    """

    if has_Intersection_between_Line_and_Segment(L,M):
        return 0
    else:
        return min(
            Distance_between_Point_and_Line(M.begin, L),
            Distance_between_Point_and_Line(M.end, L)
            )

def Distance_between_Segment_and_Segment(L,M):
    """ 2線分 L,M の距離を求める.

    L,M: 線分
    """

    if has_Intersection_between_Segment_and_Segment(L,M):
        return 0

    return min(
        Distance_between_Point_and_Segment(L.begin,M),
        Distance_between_Point_and_Segment(L.end  ,M),
        Distance_between_Point_and_Segment(M.begin,L),
        Distance_between_Point_and_Segment(M.end  ,L)
        )

#=== 点と直線の幾何
def Projection(P,L):
    """ 点 P の直線 L 上の射影を求める.

    """

    v=L.vectorize()
    return L.begin-((L.begin-P).dot(v)/v.norm_2())*v

def Reflection(P,L):
    """ 点 P の直線 L による反射を求める.

    """

    return P+2*(Projection(P,L)-P)

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.3/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page