Blogopolisから学ぶ計算幾何

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

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

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

次に,イベントの具体的な処理を見ていきましょう。イベント点から新しく始まる辺が,left_edge_c1, right_edge_c1, left_edge_c2, right_edge_c2のうちどれにあたるかによって,処理の内容は異なりますが,ここでは,left_edge_c1の場合について考えます(条件が重複して成立することもあるので注意してください⁠⁠。

条件1:left_edge_c1がleft_edge_c2とright_edge_c2の間にあるとき図5

図5 left_edge_c1がleft_edge_c2とright_edge_c2の間にあるとき

図5 left_edge_c1がleft_edge_c2とright_edge_c2の間にあるとき

このとき,left_edge_c1は必ず,交差領域の左側を構成します。したがって,計算結果にleft_edge_c1を追加します。

条件2 left_edge_c1がright_edge_c2より右から始まり,right_edge_c2と交わるとき図6

図6 left_edge_c1がright_edge_c2より右から始まり,right_edge_c2と交わるとき

図6 left_edge_c1がright_edge_c2より右から始まり,right_edge_c2と交わるとき

このとき,left_edge_c1とright_edge_c2の両方が交差領域を構成します。したがって,計算結果にleft_edge_c1とright_edge_c2の両方を追加します。なお,このとき,left_edge_c1とright_edge_c2の交点が,交差領域の最上端になります。

条件3,条件4:left_edge_c1がleft_edge_c2と交わるとき

このときは,2つの可能性があります。

条件3: left_edge_c1がleft_edge_c2と交わり,かつleft_edge_c2より右から始まるとき図7

図7 left_edge_c1がleft_edge_c2と交わり,かつleft_edge_c2より右から始まるとき

図7 left_edge_c1がleft_edge_c2と交わり,かつleft_edge_c2より右から始まるとき

この場合,left_edge_c2は交差領域を構成します。したがって,計算結果にleft_edge_c2を追加します。図7を見ると,left_edge_c1も交差領域の一部では?と思うかもしれませんが,この図のleft_edge_c1は条件1に該当するため,すでに計算結果に追加済みです。

条件4: left_edge_c1がleft_edge_c2と交わり,かつleft_edge_c2より左から始まるとき図8

図8 left_edge_c1がleft_edge_c2と交わり,かつleft_edge_c2より左から始まるとき

図8 left_edge_c1がleft_edge_c2と交わり,かつleft_edge_c2より左から始まるとき

この場合,left_edge_c1は交差領域を構成します。したがって,計算結果にleft_edge_c1を追加します。

以上が,イベント点から始まる辺がleft_edge_c1のケースにおける処理のすべてになります。条件1から4のいずれも,ステータス上の他の辺との位置関係から判定が可能です。

著者プロフィール

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

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

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