Blogopolisから学ぶ計算幾何

第2回 線分の幾何

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

はじめに

今回からは, 前回作成した直線クラスをもとに,2次元平面上の2点を結ぶ線分について考えていきます。線分は直線の一部ですが,現実のアプリケーションでは,直線よりも線分を扱うケースの方が多くなります。なぜなら,線分の集合を使って,さまざまな図形を表現できるからです。Blogopolisでは,図1に示すように土地の各区画が多角形で構成されていますが,これらの多角形も,内部的には線分の組み合わせになっています。

図1 Blogopolisと多角形

図1 Blogopolisと多角形

今回は線分を表すクラスを作成し,直線や他の線分との交差判定を実装することにします。

線分クラス

では早速,2次元平面上の線分を示すLineSegmentクラスを作ってみましょう。LineSegmentクラスは,端点の座標(x1, y1)と(x2, y2)をフィールドとして保持します。

線分クラス(Java)

public class LineSegment {
    public double x1;
    public double y1;
    public double x2;
    public double y2;

    public LineSegment(double x1, double y1, double x2, double y2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }

    @Override
    public String toString() {
        return "(" + x1 + ", " + y1 + ") - (" + x2 + ", " + y2 + ")";
    }
}

さて,線分を永遠に延長すると直線になります図2)⁠この直線への変換を行うtoLine()メソッドを,LineSegmentクラス内に用意しておくことにします。直線の表現には,前回作成したLineクラスをそのまま使用します。

図2 線分の延長

図2 線分の延長

線分を延長して直線化するメソッド

public Line toLine() {
    return Line.fromPoints(x1, y1, x2, y2);
}

線分と直線の交差判定

2つの直線は,平行でない限り必ず交わります。これに対して,線分と直線は図3のように,交差する場合もあれば交差しない場合もあります。どのような条件がみたされたとき,線分と直線が交差するのかを調べてみましょう。

なお,今回の連載では,線分の端点がちょうど直線上に重なる場合も「交差」するものとします。

図3 線分と直線の交差

図3 線分と直線の交差

以下の直線の方程式を考えます。

サンプル方程式(1)

サンプル方程式(1)

この式の等号を不等号に変えることで,2次元平面を式(1)の直線で2つに区切ったときの一方となる半平面(half plane)を示す式(2)が得られます。また,不等号の向きを逆にすると,式(2)のもう一方となる反対側の半平面を示す式(3)が得られます。この様子を図4に示します。

サンプル方程式(2)⁠3)

サンプル方程式(2)(3)

図4 不等式と半平面

図4 不等式と半平面

図4を見ると,線分と直線が交差する,つまり線分が直線を「またぐ」のは,線分の2つの端点が互いに異なる半平面の上にあるときであることが分かります。これは,線分の端点の一方が式(2)をみたし,もう一方が式(3)をみたす場合にあたります。

これを実装してみましょう。LineSegmentクラスに,引数で与えられた直線と交差するかどうかを判定するintersects()メソッドを追加します。

線分と直線の交差判定

public boolean intersects(Line l) {
    double t1 = l.a * x1 + l.b * y1 + l.c; // 端点1の座標を直線の式に代入
    double t2 = l.a * x2 + l.b * y2 + l.c; // 端点2の座標を直線の式に代入
    return (t1 <= 0 && t2 >= 0) || (t1 >= 0 && t2 <= 0); // 不等式の判定
}

上のコードの不等式判定は,もっと簡略化できます。t1とt2の積をとって,その正負を調べれば良いのです。この改良を加えたコードを以下に示します。

線分と直線の交差判定(改良版)

public boolean intersects(Line l) {
    double t1 = l.a * x1 + l.b * y1 + l.c;
    double t2 = l.a * x2 + l.b * y2 + l.c;
    return t1 * t2 <= 0; // 上の判定と等価
}

著者プロフィール

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

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

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

コメント

  • 「Blogopolisから学ぶ計算幾何」の図について

    貴Webサイトの連載「Blogopolisから学ぶ計算幾何」の「第2回 線分の幾何」内の図が「※指定画像がありません※」と表示されてしまい、見えないようです:

    http://gihyo.jp/dev/serial/01/geometry/0002

    ご確認くださいますでしょうか。

    よろしくお願い申し上げます。

    Commented : #1  関口宏司 (2013/09/26, 17:33)

コメントの記入