Blogopolisから学ぶ計算幾何

第10回 凸多角形の交差計算(後編)

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

イベントの処理(開始辺がその他の場合)

イベント点から始まる辺がleft_edge_c1の場合について見てきましたが,right_edge_c1, left_edge_c2, right_edge_c2の場合はどうなるでしょうか。今回のアルゴリズムには対称性がありますので,left_edge_c1の場合の処理と同様に考えることができます。以下,例としてright_edge_c1の場合を示します。

条件1:right_edge_c1がleft_edge_c2とright_edge_c2の間にあるとき

計算結果にright_edge_c1を追加します。

条件2 right_edge_c1がleft_edge_c2より左から始まり,left_edge_c2と交わるとき

計算結果にright_edge_c1とleft_edge_c2の両方を追加します。

条件3:right_edge_c1がright_edge_c2と交わり,かつright_edge_c2より左から始まるとき

計算結果にright_edge_c2を追加します。

条件4:right_edge_c1がright_edge_c2と交わり,かつright_edge_c2より右から始まるとき

計算結果にright_edge_c1を追加します。

走査完了時の処理

ここまでの手順で交差領域を形成する辺がすべて検出され,これ以上走査線を動かせなくなったとき,イベントの処理は完了します。ただしこの時点では,結果は元の多角形における左右の辺リストとして表現されており,まだ凸多角形の形式になっていません図9⁠。

図9 イベント処理完了時点の計算結果

図9 イベント処理完了時点の計算結果

そこで,このリストの中で,隣接する辺同士の交点を求めます図10⁠。これらの交点を結ぶと,交差領域の凸多角形が完成します。

図10 隣接する辺同士の交点

図10 隣接する辺同士の交点

いかがだったでしょうか。平面走査法のアプローチによって,2つの凸多角形の交差領域を高速に計算できることが分かったと思います。デモプログラムをもう一度動かして,ここまで説明した処理内容を1つずつ確認してみてください。

まとめと次回予告

今回は,デモプログラムを使いながら,平面走査法を使った凸多角形の交差計算のアルゴリズムを解説しました。実際のプログラムがどうなっているか興味を持った方は,ぜひ以下からソースコードをダウンロードして,実装に目を通してみてください。

今回作成したプログラムのソースコードは,こちらからダウンロードできます。

次回からは,いよいよ本連載最後のトピックとして,ボロノイ図の作成に挑戦します。お楽しみに!

著者プロフィール

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

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

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