Blogopolisから学ぶ計算幾何

第7回 (臨時回)線分の交差判定再訪

この記事を読むのに必要な時間:およそ 2 分

はじめに

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

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

何が問題なのか

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

リスト LineSegment#intersects()メソッド(Java)

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

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

図1 一直線上に並ぶ2線分

図1 一直線上に並ぶ2線分

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

図2 一直線上で共有部分を持つ2線分

図2 一直線上で共有部分を持つ2線分

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

CCW関数による交差判定

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

図3 2つの経路

図3 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の内分点になっているときに成立します。

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

著者プロフィール

浜本階生(はまもとかいせい)

1981年生まれ。栃木県出身。東京工業大学情報工学科卒業。技術やアイデアの組み合わせから面白いソフトウェアを生み出したいと日々考えている。現在,ブログの解析および視覚化の試みとして「TopHatenar」「Blogopolis」を開発,運用中。

URLhttp://d.hatena.ne.jp/kaiseh/

コメント

コメントの記入