はじめに
今回は，凸性を持つ多角形について考察していきます。多角形は辺として線分を持ちますので，前回までに学習した線分の知識は，そのまま多角形の幾何にも活かすことができます。
凸多角形とは
図形に凹みが存在しないとき，その図形は凸であるといいます。もっと厳密に述べると，図形の内部のどんな2点をとっても，その2点を結ぶ線分が図形に含まれるとき，図形は凸になります。図1の場合，左の図形は凸ですが，右の図形は凸ではありません。
図1 凸性
さて，凸性のある多角形を凸多角形（convex polygon）と呼びます。
Blogopolisでは，島の外郭が凸多角形になっています（図2）。そして，島の内部のあらゆる土地の区画もまた，例外なく凸多角形になっています（図3）。これは，凸多角形が計算処理上，便利な性質を多く備えているため，凸多角形を意図的に採用しているのです。
図2 Blogopolisの外郭
図3 Blogopolisの内部
今回は，この凸多角形がテーマになります。
凸多角形クラスの作成
まず，凸多角形を表現するクラスを用意しておきましょう。以下のようにConvexPolygonクラスを作成します。このクラスは，コンストラクタで頂点（vertex）の座標リストを与えるものとします。また，頂点の座標リストをもとに凸多角形の辺（edge）を作成し，LineSegmentオブジェクトのリストとして保持するものとします。
LineSegmentオブジェクト（Java）
public class ConvexPolygon {
private List<Point2D> vertices; // 頂点
private List<LineSegment> edges; // 辺
// verticesには凸多角形の頂点座標が順番に格納してあるものとする
public ConvexPolygon(List<Point2D> vertices) {
int size = vertices.size();
if (size < 3) { // 角数が3未満の場合はエラー
throw new IllegalArgumentException();
}
this.vertices = vertices;
edges = new ArrayList<LineSegment>();
for (int i = 0; i < size; i++) {
Point2D v1 = vertices.get(i); // i番目の頂点
Point2D v2 = vertices.get((i + 1) % size); // v1の次の頂点
// 2つの頂点から辺の線分を作成して登録
edges.add(new LineSegment(
v1.getX(), v1.getY(), v2.getX(), v2.getY()));
}
}
// 指定位置の頂点を取得
public Point2D getVertex(int index) {
return vertices.get(index);
}
// 指定位置の辺を取得
public LineSegment getEdge(int index) {
return edges.get(index);
}
// 辺の数（＝角数）を取得
public int getEdgeCount() {
return edges.size();
}
}
凸性の判定
ConvexPolygonクラスを作成したことで，凸多角形のデータ構造は準備できました。しかし，コンストラクタに渡された頂点座標のリストが，凸多角形の条件をみたしているかどうかは分かりません。ここで，ConvexPolygonオブジェクトが凸になることを保証するために，頂点リスト引数の検査を行い，凸でない場合はエラーを発生させたいとします。
多角形の頂点データをもとに，その多角形が凸であるかどうかを判定するには，どうすれば良いのでしょうか。
図4を見てください。多角形の1頂点から出発して，一筆書きのように辺を巡回し，元の頂点に戻ってくる道のりを考えます。新しい頂点に到達したとき，進行方向に回転が加わるわけですが，凸多角形の場合，その回転方向はすべて左向き（反時計回り, counterclockwise）か，右向き（時計回り, clockwise）で統一されています。
図4 多角形と辺の回転の向き
これに対し，凸でない多角形では，凹んでいる頂点のところで回転の向きが逆になります。すなわち，時計回りと反時計回りが混在するのです。このように，多角形の辺の回転方向を調べることで，凸性を判定することができます。
以下，回転方向の計算に求められる知識として，ベクトルの外積と，外積にもとづくCCW関数について見ていくことにします。
ベクトルの外積
高校数学で学んだベクトルの内積を憶えているでしょうか。ベクトルaとbの内積（a・b）はスカラーとなり，aとbのなす角度θを使って以下の式で表されます。
式1 ベクトルの内積
さて，この内積と同じく重要性の高いベクトル演算に，外積というものがあります。3次元ベクトルの世界で，ベクトルaとbの外積（a×b）はベクトルとなり，その大きさは以下の式で表されます。
式2 ベクトルの外積の大きさ
また，その向きはaとbを含む平面に垂直で，aからbへ右ねじが進む方向になります。この様子を図5に示します。
図5 外積の向き
図5を見ると，xy平面上のベクトル同士の外積をとった場合，その結果のベクトルはz軸とちょうど重なり，xとyの成分は常にゼロになることが分かります。したがって，xy平面しか使わない平面幾何の世界では，単に外積の大きさ，つまりz成分のスカラー量だけを指して「外積」ということがあります。本連載でもこの考え方を採用し，外積をスカラーとします。
