第3章多角形の三角形分割 - Tokuyama Laboratory

輪読・計算幾何学
第3章多角形の三角形分割
徳山研究室 M1
鈴木晶子
発表の内容
• 美術館問題
• 三角形分割
• 単調な部分多角形への分割
• 単調な多角形の三角形分割
美術館問題
• 美術館に監視カメラを設置
• カメラの台数はできるだけ少なく
• 美術館のどの部分も、少なくとも1台のカメラから
見えるように
• 与えられた美術館を監視するのに必要なカメラの台
数は?
• カメラはどこに配置すべき?
問題のモデル化
• 美術館→平面の多角形領域
• 単純な多角形(single polygon)
• 自己交差しない閉じた多角形チェインで囲まれた
領域
• 多角形領域を三角形（監視が簡単な断片）に分割
→監視に必要なカメラ台数の上界を求める
単純な多角形
単純な多角形ではないもの
三角形分割
三角形分割
• Pをn頂点の単純な多角形とする。
• 多角形Pの三角形分割
• 交差しない対角線の極大集合によって、多角形を
三角形に分割したもの
• 対角線：Pの2頂点をPの内部だけを通って結ぶ開
線分
定理3.1
どんな単純な多角形も三角形分割が可能である。
n頂点の単純多角形の任意の三角形分割は正確に
n-2個の三角形からなる。
[証明]
nに関する帰納法で証明する。
n=3のとき、明らかに成り立つ。
n>3とし、全てのm<nに対して定理が成り立つと仮定
する。
このとき、n頂点の多角形Pに対角線が引けることを
示す。
定理3.1の証明
• Pの最も左の頂点をvとする。
• Pの境界上で、vに隣接する2頂点をu, wとする。
• 開線分 uw がPの内部にあれば、それが対角線。
u
u
v
v
w
v’
w
• uw がPの外部を通る場合は、u,v,wによって定義される三角
形の内部、または対角線 uw上に頂点が1個以上ある。
• これらの頂点のうち、uwから最も遠いものをv’とする。
定理3.1の証明
• vとv’を結ぶ線分はPの辺と交差することはない。
• もし vvがPの辺と交差するとすれば、
vvと交差するPの辺は
u
u,v,wによって定義される三角形の内部に
v
端点をもち、さらにその点は
v’
uwから最も遠いところになければならない。
w
“ uw から最も遠い頂点”というv’の定義に矛盾
• したがって、 vv はPの辺と交差しない、つまり対角線である。
• 対角線は必ず存在する。
P1
P
P2
• Pを2つの単純な多角形P1とP2に分割する。
• P1の頂点数 : m1, P2の頂点数 : m2
• m1とm2はnより小さくなければならない。
したがって帰納法の仮定より、 P1とP2は三角形分割可能。
Pも三角形分割可能
• ここで、 m1 + m2 =n+2
また帰納法の仮定より、Pi の任意の三角形分割はmi-2個の
三角形からなる。
したがって、Pの三角形分割は
(m1 -2)+(m2 -2)=n-2個の三角形からなる。（証明終）
監視に必要なカメラの台数は?
• n頂点の単純多角形Pは、n-2個の三角形に分割可能
• 各三角形の内部に1台ずつカメラを配置
必要なカメラはn-2台
• カメラを多角形の頂点に配置
1台のカメラで複数の
三角形を監視可能
• 定理3.2（美術館定理）
n頂点の単純多角形に対して、多角形内のすべての
点が少なくとも1台のカメラから見えるようにするのに、
n 3台のカメラが必要になることがあり、またその台
数で常に十分である。
カメラ配置のアイデア
• 三角形分割された多角形の3-彩色
• 多角形の各頂点には赤、青、黄色のいずれか1色が割り
当てられている
• 辺や対角線によって結ばれたどの2頂点も異なる色をもつ
• どの三角形も赤、青、黄の頂点を1つずつもつ
• 3色のうち1色を選び、その色が
割り当てられている頂点にカメラ
を設置すると、 n 3台のカメラで
全ての三角形を監視可能
3-彩色は必ず存在する?
三角形分割された多角形の3-彩色
• Tp : Pの三角形分割
• G(Tp) : Tpの双対グラフ
• Tpの全ての三角形に対して1つの節点をもつ
• t(ν)とt(μ)が対角線を共有するとき、対応する2つの
節点νとμの間にグラフの枝を引く
• どの対角線もPを2分する
↓
• G(Tp)は木である
3-彩色の方法
• グラフ探索法（深さ優先探索など）を用いる
• 節点を訪れたときに、対応する三角形の頂点に彩色
する
• 新しく節点νを訪れたとき、三角形の3つの頂点のうち
2つは既に色がつけられている
↓
残る1点に色をつける
• グラフGは木なので、νに隣接
している他の頂点はまだ訪問
されていない
3-彩色は必ず存在する
単調な部分多角形への分割
三角形分割のアイデア
•
•
凸でない多角形Pを三角形分割する方法
1. Pを単調な多角形に分割する
2. 分割された多角形を三角形分割する
y単調な多角形
• y軸に垂直などんな直線lに対しても、lと多角形との交差
部分が連結であるようなもの
• lと多角形との交差部分は線分、1点、空のいずれか
y軸
y軸
l
l
単調な多角形を求めるアイデア
• y単調な多角形の特徴
最も上の頂点から最も下の頂点ま
で、左（あるいは右）の境界をたど
るとき、常に下向きか水平に進ん
でいく
start
y単調な多角形を得るためには...
goal
• 多角形の最も上の頂点から最も下
の頂点へたどっていくとき、下向き
から上向きに変化する頂点（変曲
点）を取り除けばよい
• 変曲点から対角線を引くことにより
取り除く
多角形の頂点の分類
出発点(start vertex)
隣接頂点が両方とも下にあり、
内角がπより小さい
分離点(split vertex)
隣接頂点が両方とも下にあり、
内角がπより大きい
最終点(end vertex)
隣接頂点が両方とも上にあり、
内角がπより小さい
統合点(merge vertex)
普通の頂点(regular vertex)
それ以外
隣接頂点が両方とも上にあり、
内角がπより大きい
y単調な多角形の性質
• 補題3.4
分離点も統合点ももたない多角形はy単調である。
[証明]
「Pがy単調でないとき、Pは分離点か統合点をもつ」ことを示す。
Pはy単調でないので、Pと交差する部分が2つ以上の成分に
分かれるような水平線lが存在する。
P
このとき最も左の成分の左端点をp,
右端点をqとする。
qから出発して、Pの内部を左に見ながら
Pの境界をたどると、ある点rで境界はlと
p
r
l 再び交差するはずである。
q
補題3.4の証明
分離点
P
p
r
q
P
q
r’
p=r
統合点
• p≠rのとき
• qからrまでの道のりで最も高いところ
にある頂点は分離点でなければなら
ない。
l
• p=rのとき
• qから出発して、Pの内部を右に見なが
らPの境界をたどる。このとき境界がl
と交差する点をr’とする。
• もしr’=pなら、Pの境界はlと2回しか交
差しないことになるため、r’≠pである。
l
• このときqからr’までの道のりで最も低
いところにある頂点は、統合点でなけ
ればならない。
アルゴリズムのアイデア
平面走査法を用いて、分離点と統合点を取り除く
helper(ej)
ej
• 仮想的な走査線lを上から下
l
へと動かしていく。
• lが分離点viに到達したとき、
lからの距離が最小でviより
上にある頂点と、viとを結ぶ。
ek
分離点vi
ejのヘルパー
アルゴリズムのアイデア
平面走査法を用いて、分離点と統合点を取り除く
helper(ej) : 移動前
統合点vi
ej
l
ek
• lが統合点viに到達したとき、
lからの距離が最小でviより
下にある頂点と、viとを結ぶ。
viの次に
ejのヘルパーになる点
helper(ej) : 移動後
単調な多角形に分割するアルゴリズム
•
MAKEMONOTONE(P)
• 入力
2重連結辺リストの形で蓄えられた単純多角形P
• 出力
2重連結辺リストDに蓄えられた、Pの単調な部分多角形
への分割
•
用意しておくもの
• y座標値を優先順位として用いた、Pの頂点に関するプラ
イオリティキューQ
• 走査線と交差するPの辺（とそのヘルパー）を蓄えておく、
2分探索木T（空に初期化する）
アルゴリズムの実行例
Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13
l T
v5
v3
e5 e 4 v4 e3
v6
e5
e6
e2
helper v5
v7
v1
v2
v9
e7
e1
e8
• HANDLESTARTVERTEX(v5)
v8
e9
e15
e5をTに挿入し、 e5のヘルパーを
v14 e14
v5とする。
v10
e10
v15
e13
e11 v12
e12
v11
v13
アルゴリズムの実行例
Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13
v5
v3
T
v
e5 e 4 4 e3
l
v6
e5
e3
e6
e2
helper v5
v3
v7
v1
→v4
v2
v9
e7
e1
e8
• HANDLEMERGEVERTEX(v4)
v8
e9
e15
e5のヘルパーもe3のヘルパーも
統合点ではないので、対角線は
v14 e14
v10
引かない。
e10
v15
e13
e11 v12
lはe3と交差しなくなるのでTから
e12
v11
を削除し、 e5のヘルパーをv4に
v13
変更する。
アルゴリズムの実行例
Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13
v5
v3
T
v
e5 e 4 4 e3
l
v6
e5 e6
e6
e2
helper v4
v6
v7
v1
v2
v9
e7
e1
e8
• HANDLEREGULARVERTEX(v6)
v8
e9
e15
e5のヘルパー(v4)が統合点なの
v14 e14
で、v6からv4へ対角線をひく。
v10
e10
v15
lはe5と交差しなくなりe6と交差す
e13
e11 v12
るようになるので、 e5をTから削
e
12
v11
除し、代わりにe6を挿入する。
v13
アルゴリズムの実行例
Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13
v5
v3
T
v
e5 e 4 4 e3
v6
e9
e7
e6
e2
helper v9
v2
v7
v1
→v8
v2
v9
e7
e1
e8
l • HANDLEMERGEVERTEX(v8)
v8
e9
e15
e7のヘルパー(v2)が統合点なの
v14 e14
で、v8からv2へ対角線を引く。
v10
e10
v15
lはe7と交差しなくなるのでTから
e13
e11 v12
を削除し、 e9のヘルパーをv8に
e
12
v11
変更する。
v13
アルゴリズムの実行例
Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13
v5
v3
T
v
e5 e 4 4 e3
v6
e9
e14
e6
e2
helper v8
v14
v7
v1
→v14
v2
v9
e7
e1
e8
• HANDLESPLITVERTEX(v14)
v8
e9
e15
v14とv8 （ e9のヘルパー）を結ぶ
対角線を引く。
v14 e14
l
v10
e10
e9のヘルパーをv14に変更する。
v15
e13
e11 v12
e14をTに挿入し、そのヘルパー
e
12
v11
をv14とする。
v13
アルゴリズムの実行例
Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13
v5
v3
T
v
e5 e 4 4 e3
v6
e10
e14
e6
e2
helper v10
v14
v7
v1
v2
v9
e7
e1
e8
• HANDLEENDVERTEX(v15)
v8
e9
e15
e14のヘルパーは統合点ではな
v14 e14
いので、対角線は引かない。
l
v10
e10
v15
e13
e11 v12
e14をTから削除する。
e
12
v11
v13
アルゴリズムの実行例
Q v5 v3 v4 v6 v7 v1 v9 v2 v8 v14 v10 v15 v12 v11 v13
v5
v3
T
v
e5 e 4 4 e3
v6
e10
e12
e6
e2
helper v10
v12
v7
v1
→v12
v2
v9
e7
e1
e8
• HANDLESPLITVERTEX(v12)
v8
e9
e15
v12とv10 （ e10のヘルパー）を結ぶ
v14 e14
対角線を引く。
v10
e10
e10のヘルパーをv12に変更する。
v15 l
e13
e11 v12
e12をTに挿入し、そのヘルパー
e
12
v11
をv12とする。
v13
• 補題3.5
アルゴリズムMAKEMONOTONEによって加えられる
対角線の集合は、互いに交差することなくPを単調な
多角形に分割する。
[証明]
Pが分割されてできる部分多角形は分離点も統合点
も含まないことは明らか。
したがって、線分が挿入された時にその線分が
• Pの辺と交差しない
• 以前に挿入された線分と交差しない
ことを示す。
vm
ej
Q
ek
vi
• 分離点viに到達した時に、Pに加
えられる線分 vmvi を考える。
• viのすぐ左にある辺をej, すぐ右
にある辺をekとする。
• vi, vmを通る2本の水平線分とej,
ekを境界とする四角形をQとする。
• 四角形Qの中に、Pの頂点は存在しない。
もし存在すれば、その頂点が辺ejのヘルパーとなり、 vmがej
のヘルパーでなくなってしまう。
• 次に、vmvi と交差するPの辺が存在すると仮定する。
• この辺は、Qの中に端点を持つことはできないため、 viとejを
結ぶ水平線分か、 vmとejを結ぶ水平線分と交差するはずで
ある。
• しかしvi, vmのどちらに対しても、それらの頂点のすぐ左にあ
る辺はejなので、vmvi と交差する辺は存在しない。
vm
ej
Q
ek
vi
• 以前に付け加えられた対角線との交差について考える。
• Qの内部にPの頂点は存在しない。
また、以前付け加えられた対角線の両端点は、viよりも上にな
ければならない。
したがって、 vmvi と交差することはない。
• viが統合点、最終点、普通の頂点の場合にも同様の性質が
成り立つ。
アルゴリズムの実行時間
• プライオリティキューQの構成→O(n)時間
• 2分探索木Tの初期化→O(1)時間
• 1つの頂点に到達したときに行われる処理
• Qに関する操作(1回)→O(logn)時間
• Tに関する質問(高々1回)、挿入、削除(1回)
→O(logn)時間
• Dへの対角線の挿入(高々2本)→O(1)時間
1つのイベントに対してO(logn)時間
• n個の頂点に対して処理を行うので、全体での実行
時間はO(nlogn)
定理3.6
記憶領域O(n)のアルゴリズムにより、n頂点の単純
多角形をO(nlogn)の時間でy単調な多角形に分割す
ることができる。
単調な多角形の三角形分割
アルゴリズムの概要
v5
S
v4
v3
v2
v1
v1
v2
v3
v6
v4
v5
• y座標値の降順に頂点を処理す
る。
• 既に出会ったが、まだ対角線が
引かれていない頂点を蓄えて
おくための、スタックSを用意し
ておく。
• 1つの頂点を処理するとき、そ
の頂点からスタック内の頂点に
向けてできるだけ多数の対角
線を引く。
アルゴリズムのポイント
• アルゴリズムの実行中に常に成り立つ性質
• まだ三角形分割しなければな
らないPの部分で、これまでに
調べた最後の頂点より上にあ
る部分
まだ三角形分割
されていない部分
• Pの一つの辺
• 鈍角の頂点からなる多角形
チェイン
が境界となっている
三角形分割アルゴリズム
•
TRIANGULATEMONOTONEPOLYGON(P)
•
•
1.
入力
2重連結辺リストDの形で蓄えられた、厳密にy単調な多
角形P
出力
2重連結辺リストDの形で蓄えられた、Pの三角形分割
y座標値の降順にソートされたPの左側のチェイン上の頂点
列と、右側のチェイン上の頂点列を一つの系列に統合する。
ソート列をu1,…,unとする。
三角形分割アルゴリズム
2.
3.
u1とu2をスタックSにプッシュする。
u3~un-1の頂点ujは、以下のように処理する。
• ujとSの一番上の頂点が異なるチェイン上にある場合
→Sからすべての頂点をポップし、 ujとポップされたそれ
ぞれの頂点とを結ぶ。
uj-1 S
uj-2
uj-1
…
uj-2
S
uj
uj
uj-1
三角形分割アルゴリズム
u3~un-1の頂点ujは、以下のように処理する。
• ujとSの一番上の頂点が同じチェイン上にある場合
→Sから一つずつ頂点をポップし、 ujからの対角線がP
の内部にある限り、対角線を引く。
4. 最初と最後の頂点を除いて、unからすタック上の全ての頂点
への対角線を加える。
3.
uj-1 S
uk
uj-2
…
uj-1
uj
S
uk
uj
uk-1
uk
アルゴリズムの計算時間
• u1とu2をスタックSにプッシュする。→O(1)時間
• u3~un-1の処理(n-3回の繰り返し処理)
• スタックへのプッシュの回数
→1頂点の処理につき高々2回
• スタックからのポップの回数
→プッシュの回数以下
⇒O(n)時間
• 定理3.7
n頂点の厳密にy単調な多角形は、線形時間で三角
形分割できる。
まとめ
• 多角形の監視
• 単純多角形をy単調な多角形に分割
• y単調な多角形を三角形分割
• 3-彩色によりカメラを配置
• 定理3.3
Pをn頂点の単純多角形とする。
P内のどの点も少なくとも1台のカメラから見えるよう
にPの中に n 3台のカメラを配置する方法を
O(nlogn)時間で求めることができる。

Download Report