Blogopolisから学ぶ計算幾何

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

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

ベクトルの内積

ベクトルの内積は,以下の式で定義されます。

式1 ベクトルの内積

式1 ベクトルの内積

また,ベクトルaを(x1, y1),ベクトルbを(x2, y2)と成分表示すると,aとbの内積は以下の式で計算できます。

式2 ベクトルの成分による内積の計算式

式2 ベクトルの成分による内積の計算式

ここでまず,前回作成したGeomUtilsクラスに,この内積の計算を行うdot()メソッドを追加しておきましょう。dotという名前は,ベクトルの内積がドット積とも呼ばれることに由来します。

リスト 内積の計算(Java)

public static double dot(double x1, double y1, double x2, double y2) {
    return x1 * x2 + y1 * y2;
}

さて,図4を見てください。点l, m, nに関して,ベクトルnlとnmを考えます。nがlmを内分する場合,nlとnmは互いに逆方向を向くので,nlとnmのなす角度θは180度となり,cosθが-1となるので,その内積は負の値になります。一方,nがlmを外分する場合,nlとnmの向きは一致するのでθは0度となり,cosθが1となるので,内積は正の値になります。また,nがlまたはmに重なる場合は,ベクトルnlまたはnmの大きさがゼロになるので,内積もゼロになります。

図4 内分点・外分点とベクトルの向き

図4 内分点・外分点とベクトルの向き

このように,内積の符号を見ることで,点が線分の内部と外部のどちらに存在するかが分かります。ここから,一直線上に並ぶ2つの線分が共有部分を持つかどうかを判定できるのです。

交差判定の再実装

ここまで見てきた内容をすべてふまえて,LineSegmentクラスのintersects()メソッドを書き直すと,以下のようなコードになります。

書き直したintersects()メソッド(Java)

// 第7回で書き直し
public boolean intersects(LineSegment s) {
    return bothSides(s) && s.bothSides(this);
}

// sが自線分の「両側」にあるかどうかを調べる
private boolean bothSides(LineSegment s) {
    double ccw1 = GeomUtils.ccw(x1, y1, s.x1, s.y1, x2, y2);
    double ccw2 = GeomUtils.ccw(x1, y1, s.x2, s.y2, x2, y2);
    if (ccw1 == 0 && ccw2 == 0) { // sと自線分が一直線上にある場合
        // sのいずれか1つの端点が自線分を内分していれば,sは自線分と共有部分を持つので
        // trueを返す
        return internal(s.x1, s.y1) || internal(s.x2, s.y2);
    } else { // それ以外の場合
        // CCW値の符号が異なる場合にtrueを返す
        return ccw1 * ccw2 <= 0;
    }
}

// (x, y)が自線分を内分しているかどうかを調べる
private boolean internal(double x, double y) {
    // (x, y)から端点に向かうベクトルの内積がゼロ以下であれば内分と見なす
    return GeomUtils.dot(x1 - x, y1 - y, x2 - x, y2 - y) <= 0;
}

動作確認

デモプログラムを作成して,新しいintersects()メソッドの動作を確認してみます。

リスト デモプログラム(Java)

public class RevisedLineSegmentDemo {
    public static void main(String[] args) {
        LineSegment s1 = new LineSegment(0, 0, 100, 0);
        LineSegment s2 = new LineSegment(99, 0, 200, 0);
        LineSegment s3 = new LineSegment(101, 0, 200, 0);
        System.out.println(s1.intersects(s2));
        System.out.println(s1.intersects(s3));
    }
}

このプログラムで,s1, s2, s3は同一の直線上に存在します。s1とs2は一部重なっていますが,s1とs3は離れています。プログラムを実行すると,以下の出力が得られます。

 デモプログラムの実行結果

true
false

intersects()メソッドを書き直したことにより,一直線上に並ぶ線分に対しても,正しく交差を判定できていることがわかります。

まとめと次回予告

今回は,第2回で実装した線分の交差判定に問題があることを説明し,CCW関数とベクトルの内積を使った新しい実装を行いました。図らずも,CCW関数の有用性を示す回になったと言えるかもしれません。

今回作成したプログラムのソースコードがダウンロードできます。

次回は,当初予定していた多角形の話題に戻りたいと思います。お楽しみに!

著者プロフィール

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

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

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