はじめに

今回は臨時回として，第2回で取り上げた線分の交差判定について再度考えます。第2回の実装には，ある特別な状況下で正しく動作しないという問題がありました（筆者が執筆時点で問題を見落としていました。申し訳ありません⁠）⁠。

この問題を解決するために，前回学んだばかりのCCW関数を活用し，線分の交差判定を別のアプローチから実装することができます。ちょうど良い機会ですので，今回はその再実装を行ってみたいと思います。

何が問題なのか

第2回では，線分の交差判定を行うLineSegment#intersects()メソッドを以下のように作成しました。

public boolean intersects(LineSegment s) {
    return intersects(s.toLine()) && s.intersects(toLine());
}

これは，線分を延長して直線化し，直線と線分の交差問題に置き換えるという方針に基づく実装です。しかし，図1のように2つの線分が一直線上に並ぶ場合，上のコードは常にtrueを返してしまいます。

本来，一直線上に並ぶ2線分に対しては，図2のように，線分が共有部分を持つときのみ交差としなければなりません。第2回のintersects()メソッドには，こうした問題があったのです。

ところで，前回取り上げたCCW関数のアプローチを使い，上記の問題を回避できる線分の交差判定の方法が存在します。そこで今回は，CCW関数を使ってLineSegment#intersects()メソッドを書き直してみることにします。

CCW関数による交差判定

図3のように，線分abとcdがあるとします。ここで，aからスタートし，cまたはdを経由してbまで進む経路，a→c→bとa→d→bの2つを考えます。

もし，abとcdが交差するのであれば，cとdはabを挟んで互いに向き合うかたちになりますから，a→c→bとa→d→bのCCW値は符号が異なるか，少なくとも一方がゼロになるはずです。CCW値が両方とも正または負になることはあり得ません。

さらに，同じ条件が，cからスタートし，aまたはbを経由してdまで進む経路，c→a→dとc→b→dについてもみたされる必要があります。

したがって，これら4つのCCW値であるccw(a, c, b), ccw(a, d, b), ccw(c, a, d), ccw(c, b, d)の符号を調べれば，線分の交差判定ができることになります。

さて，線分が図1や図2のように一直線上に存在する場合，これらのCCW値はすべてゼロになります。このときに限り，abとcdが図2のように共有部分を持つかどうかを調べる追加処理が必要です。この共有部分を持つ条件は，cまたはdがaとbの内分点になっているか，aまたはbがcとdの内分点になっているときに成立します。

では，点が線分を内分しているかどうかを判定するには，どうすれば良いのでしょうか。それには，ベクトルの内積が利用できます。