Blogopolisから学ぶ計算幾何

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

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

はじめに

前回に引き続き,平面走査法のアプローチを用いて,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辺の各終点のうち,もっとも上にある点が次のイベント点になる

図1 走査線と交わる4辺

図1 走査線と交わる4辺

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

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

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

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

図2 デモプログラムを起動したところ

図2 デモプログラムを起動したところ

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

図3 交差部分の辺検出過程

図3 交差部分の辺検出過程

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

走査線の開始位置

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

図4 走査線の開始位置

図4 走査線の開始位置

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

著者プロフィール

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

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

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

コメント

コメントの記入