数学orアルゴリズムが得意の方（線分と線分の交点判別）
Ｃ言語のアルゴリズムを勉強中です。
線分Ａ（A(x1,y1),B(x2,y2))と線分Ｂ（C(x3,y3),D(x4,x4))が交差するかどうかを判別し、交差するのであればその交点Ｐ(X,Y)を求める。
また、その交点がどちらか一方の線分上にあるかどうかも判別したいのです。
一番効率よくやるにはどのようにすればよいでしょうか。
例えば
１、三角形の符号付き面積を使って交差するかどうかと各点が線分上にあるかどうかを判別し、その後交点を求める
２、とり合えず交点を求めてその交点が各線分内(上)にあるかどうかを判別
他にもたくさんありそうですがとにかく出来るだけ計算回数を減らしたいのです。（さっき求めた～～を～～するといったかんじで）
出来れば流れ全体を書いていただきたいのですが書き込むのが大変だと思うのでせめて使う判別式だけでも教えてください。
これが出来たら、
多角形と多角形の交点判別のアルゴリズムにも挑戦しようと思っています。
数学の得意な方、アルゴリズムを考えるのが好きな方
よろしくお願いします。
お礼
分かりました！ありがとうございます！