交差点
線
の交点
a1, b1, c1 - 最初の行の係数、
a2, b2, c2 - 2 行目の係数
x, y - 交点。
\(x = {-(c1 \cdot b2 - c2 \cdot b1) \over (a1 \cdot b2 - a2 \cdot b1)} \\ y = {-(a1 \ cdot c2 - a2 \cdot c1) \over (a1 \cdot b2 - a2 \cdot b1)} \)
線の交点 (平行ではない) をチェックし、交点を見つける方法は既に知っています。
では、セグメントでこれを行う方法を学びましょう.
まず、交差を簡単にチェックする方法を学びましょう。
セグメントが交差する一方の端が他方の反対側にある場合、およびその逆の場合 (これは外積によって簡単に確認できます)。 これが機能しない唯一のケース - セグメントは 1 つの直線上にあります。 そのためには、いわゆる交点をチェックする必要があります。 バウンディング ボックス (セグメントのバウンディング ボックス) - X と Y 上のセグメントの射影の交点を確認します。
軸。
セグメントの交点をチェックする方法がわかったので、交点のポイント (またはセグメント) を見つける方法を学びましょう:
- 交差しない場合、そのような点が存在しないことは明らかです。
- それ以外の場合は、これらのセグメントが存在する直線を作成します。
それらが平行である場合、セグメントは同じ線上にあり、セグメントの左境界線の最大値から右境界線の最小値までの交差セグメントを見つける必要があります (点が他の点よりも小さい場合、左にある場合、等しい場合は X-座標 - 低い場合)。
線が平行でない場合は、交点を見つけて返します。