計算幾何学とは

小学生や中学生の頃，算数や数学の授業で，台形の面積を求めたり，直線の方程式を解いたりした記憶が誰にでもあることでしょう。計算幾何学とは，コンピュータサイエンスの立場から，こうした「図形」に関するアルゴリズムを研究する学問です。計算幾何学は，今日のコンピュータグラフィックスやCADの発展においてきわめて重要な役割を担っているほか，地理情報システム（GIS）やロボット工学といった数多くの分野に応用されています。

本連載では，ブログ可視化サイトの「Blogopolis」で採用されている計算幾何的アプローチを引き合いに出しつつ，Javaプログラムでアルゴリズムを実装しながら，計算幾何学の初歩を学びます。

Blogopolisとボロノイ図

Blogopolisは筆者の開発したWebサイトで，主に日本国内で開設された25万件以上のブログを解析し，「仮想都市景観」として視覚化したサービスです。Blogopolisでは，1人1人のブロガーが人気度に応じた広さの「土地」を持っています。土地の中では，ブログの個別記事を示す「ビル」が立ち並び，オフィス街のような見た目を形成しています。

Blogopolisの外観は3Dですが，その3D表現の基盤になっているのは，2次元平面上の区画分けアルゴリズムです。この区画分けには，ボロノイ図（voronoi diagram）をアレンジした手法が使われています。

ボロノイ図は，複数個の母点との距離にもとづいて領域を分割した図で，計算幾何学の重要なテーマの1つです。もっとも単純なボロノイ図では，「どの母点との距離が最短になるか」によって分割が決定されて境界線が引かれるため，境界線は2つの母点の垂直二等分線になっています。

ボロノイ図はさまざまな応用ができますが，その1つに商圏分析があります。例えば図2で，各母点の位置にコンビニエンスストアが建っているとしましょう。客は自宅から最も近いコンビニエンスストアに行くと仮定した場合，各店舗が集客を見込めるエリアは，ボロノイ図で分割された領域で推定することができます。

幾何ライブラリ

多くのプログラミング言語では，幾何が標準ライブラリでサポートされていたり，外部ライブラリとして提供されています。例えばJavaでは，java.awt.geomパッケージ以下のクラスを使って，基本図形の定義や交差判定，パスの結合といった操作を行うことができます。

こうしたライブラリは高度に抽象化されており，内部実装を知らなくても簡単に利用できます。図形を扱う大半の用途では，標準のライブラリを呼び出すだけで事足りるはずです。しかし，より複雑な問題を解く場合には，それぞれの問題に適したデータ構造やアルゴリズムを独自に実装する必要も出てきます。いずれにせよ，計算幾何の基本的な考え方を知り，動作原理に触れておくことは有益でしょう。

本連載のロードマップ

本連載では，計算幾何学の中でも特に基本的な内容として，直線，線分，そして多角形を取り上げます。初めに，2次元平面上で直線と線分を表現するクラスを作成し，それらが交差する条件を調べます。次に，平面走査法（plane sweep algorithm）と呼ばれるアルゴリズムを使って，多数の線分の中から交差点を高速に検出する方法を学びます。さらに，線分を組み合わせて多角形を表現し，多角形を使った演算について見ていきます。最後に，これまで学んだ手法を組み合わせ，ボロノイ図の作成に挑戦します。

Javaの開発環境について

本連載では，プログラミング言語としてJavaを使用します。手元にJavaの開発環境がなく，本連載のプログラムを試したい場合には， NetBeansの導入をおすすめします。NetBeansはオールインワン型のIDEですので，インストールするだけで特別な設定の必要もなく，一通りの開発環境を整えることができます。

直線クラスの作成

まず，中学数学の復習から始めましょう。2次元平面上の直線は，どのような式で表すことができるでしょうか。

上の式を思い浮かべた人が多いかもしれません。aは直線の傾き，bはy軸の切片です。しかし，この式ではy軸に平行な直線を表現できないため，以下の一般形を使うのが正解になります。

a，b，cの3つのパラメータがあれば，2次元平面上の任意の直線を示せるのです。ではこれを，Lineクラスとして作成してみましょう。

public class Line {
    public double a;
    public double b;
    public double c;

    public Line(double a, double b, double c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }

    @Override
    public String toString() {
        return "a = " + a + ", b = " + b + ", c = " + c;
    }
}

簡略化のため，a，b，cはpublicフィールドとして宣言し，getterやsetterのメソッドは設けていません。また，デバッグを容易にするため，toString()メソッドをオーバーライドしています。