はじめに
今回からは，2つの凸多角形を重ね合わせて，その共通部分を切り出す交差計算を見ていきます。以前に学んだ平面走査法をうまく応用することで，高速な交差計算が可能になります。また，この凸多角形の交差計算は，本連載の最後で取り上げるボロノイ図の作成にも深く関係します。
図形のブーリアン演算
Adobe Illustratorなどのドローツールでは，2つの図形を結合して新しい図形を作り出す操作が良く行われます。これはブーリアン演算（boolean operation）と呼ばれ，領域を併合するunion演算，共通部分を切り出すintersection演算，差分を求めるdifference演算といったバリエーションがあります（図1）。
図1 ブーリアン演算
一般に，図形のブーリアン演算は複雑な処理になります。多角形同士の演算を考えてみても，図2に示すように，演算結果が「穴」を含む領域になったり，分離した領域になったりするため，もはや結果を単純な頂点配列などで表現することはできず，二重辺連結リスト（doubly connected edge list）などのデータ構造が必要になります。
図2 一般のブーリアン演算
しかし，凸多角形同士のintersection演算，すなわち交差領域の計算に限れば，処理はいくぶん簡単にです。なぜなら，2つの凸多角形の共通領域の形状は，必ず凸多角形になるというシンプルな性質があるからです（図3）。
図3 凸多角形同士の交差
今回からは，前回までに作成したConvexPolygonクラスをもとに，2つのConvexPolygonオブジェクトから新しいConvexPolygonオブジェクトを作り出す交差計算の方法を解説していきます。
解説の方針
これまでの回では，説明した内容に対応するソースコードを，その都度紙面に掲載するスタイルで記事を構成してきました。しかし，今回はソースコードの規模がやや大きくなるため，ページにプログラムを含めると，解説文が冗長になってしまいます。
そこで，今回以降の連載では，アルゴリズムの大まかな流れを示すにとどめたいと思います。もちろん，最後にはソースコードのアーカイブファイルを公開しますので，興味のある方はぜひダウンロードして，実装の詳細を確認してみてください。
平面走査法の応用
2つの凸多角形の交差から作り出される新しい凸多角形は，どんな頂点から構成されるでしょうか。図4からも容易に分かるように，それは元の2つの凸多角形のいずれかの頂点になるか，あるいは元の辺同士の交点になります。
図4 交差計算結果の頂点
つまり，凸多角形の交差計算の過程には，凸多角形が持つ辺の中から交差を見つけ出す処理が含まれることになります。したがってこれには，第3回から第5回にかけて学習した，平面走査法による線分の交差検出のアプローチを応用できることになります。
簡単に復習しておきましょう。平面走査法では，平面領域上に仮想的な走査線を設定し，イベント点を単位として，走査線が領域を離散的に通過するようになっていました。走査線の移動は，イベントキューから次のイベントを取り出すことによって行われます。また，現在の走査線と交わる線分は，ステータスと呼ばれるデータ構造に格納されます。
以下，凸多角形の交差計算においては，ステータスとイベントキューをどのように表現するのが最も合理的かを考えていきましょう。
