はじめに

前回に引き続き，平面走査法のアプローチを用いて，2つの凸多角形の交差部分を求める方法を解説します。今回は，まずWeb上で実行可能なデモプログラムを示した上で，プログラムを実際に操作しながら，その動きを追うかたちで説明を行います。

前回の復習

最初に，前回のポイントを押さえておきましょう。

• 2つの凸多角形の交差部分は，同じく凸多角形になる
• 2つの凸多角形の交差計算には，第3回～第5回で解説した平面走査法を応用できる
• 走査線と交わる線分は，left_edge_c1, right_edge_c1, left_edge_c2, right_edge_c2のたかだか4個である（図1）
• イベント点となるのは，入力の凸多角形の頂点のみである
• left_edge_c1, right_edge_c1, left_edge_c2, right_edge_c2の4辺の各終点のうち，もっとも上にある点が次のイベント点になる

交差計算のデモプログラム

それでは早速，デモプログラムを示します。

このリンクをクリックしてください。Java Web Start形式のプログラムが起動します。これは，平面走査法による凸多角形の交差計算過程を，グラフィックで段階的に表示するデモになっています。

ウィンドウの中には，2つの凸多角形が置かれています（図2⁠）⁠。辺や頂点をドラッグすると，図形を移動したり，変形したりすることができます。ただし，凸でない多角形にすることはできません。

画面上部の「次のイベント」ボタンをクリックすると，特定の頂点位置に走査線が現れます。さらに続けて「次のイベント」ボタンをクリックすると，走査線が少しずつ下に移動していきます。走査線が移動する過程で，2つの多角形の交差部分となる辺が，順に赤色と青色で塗られていきます（図3⁠）⁠。赤色は，交差計算結果となる凸多角形の「左側」の辺を示し，青色は「右側」の辺を示しています。計算がすべて終わり，交差部分の凸多角形が確定すると，走査線は消滅します。

2つの凸多角形をいろいろな配置に変えて，走査線がどのような動きをするか，そして交差部分の辺がどのように決まっていくかを確認してみてください。

走査線の開始位置

では最初の問題として，走査線がどの頂点位置からスタートしているかを観察してください。いろいろと条件を変えて試すと分かりますが，これは入力となる2つの凸多角形のうち，より下にある方の最上端の頂点になっています（図4⁠）⁠。

この位置は，2つの凸多角形が同時に存在し得るy座標の上限です。ここより上には片方の多角形しかないので，交差領域は絶対に存在しないことになります。