Computational Geometry
Algorithms and Applications
Chapter.15 Visibility Graph
発表者：西川 徹
・１３章では、与えられた出発点から与えられた目標点に至るロボットの経路を求める方法
→そこで与えたアルゴリズムは、経路が存在すれば必ず求めることができるが、経路の質に
ついては考慮していない。
→遠回りや、ぐるぐると不必要な回転を繰り返すといったこともある
↓
単に経路を求めるだけでなく、良い経路を見つけたい！！
しかし・・・
・どんな経路がよいかはロボットによって異なる
一般に、経路が長ければ長いほど時間がかかる
直線上しか移動できないようなロボットもいる
→その場合は、方向転換のたびに速度を落として、停止した後で回転
→経路の長さだけでなく、経路における折れ曲がり点の個数も重要
↓
今回は、並進可能な平面ロボットに対するユークリッド最短路を求める方法
15.1 点ロボットに対する最短経路
・平面上の互いに共通部分を持たない単純多角形の集合Sの間を移
動する点ロボットの場合をまず考える
・Sの多角形は障害物（Obstacle）と呼ばれ、その辺の総数をnであらわす
・障害物は開いた集合
→ロボットが障害物に接触してもよい
・出発点pstartと目標点pgoalが与えられる（自由空間にある）
↓
目標は、 pstartからpgoalまでの無衝突の最短経路を求めること
ここで、
・最短経路は唯一であるとは限らない
・最短経路が存在するためには、障害物が開いた集合であることが必要
＜コンフィグレーション空間＞
・ロボットの配置はロボットの自由度に等しい個数のパラメータによって指定される。
・並進移動だけの平面的ロボットの場合は２
・回転もできる平面的ロボットの場合は３
→ロボットのパラメータ空間は一般的にコンフィグレーション空間と呼ばれる。
点ロボットの場合は、作業空間とかわらない。
・ロボットが障害物の一つと交差する配置に対応する点は禁止されている。
→禁止コンフィグレーション空間
・ロボットがどの障害物とも交差しない配置
→自由コンフィグレーション空間
・１３章では、自由コンフィグレーション空間Cfreeの台形地図T(Cfree)
を求めることによって、経路を見つける。
・点ロボットの場合、Cfreeは単に障害物の間の空の空間
基本的なアイデアは、
無限通りの経路が存在する連続作業空間
↓
有限通りの経路しか含まない離散的な道路地図Groadで置き換える
←ここでの道路地図は、節点を台形の中心と隣接台形を分離する垂直延長線の中間に
置いた平面グラフ。各台形の中心においた節点は境界上の節点と連結。
・ロボットの出発点と目標点を含む台形を見つける
↓
・台形の中心にある節点を結ぶ経路を幅優先探索
・幅優先探索を用いた
→求まった経路はGroadの辺を最小個数しかつかわない
↓
必ずしも短い経路ではない！
そこで、、、
・各枝に、対応する節点間の線分のユークリッド距離に等しい値を重みとして与え
・Dijkstraのアルゴリズム
↓
経路長は改善できるが、最短経路が得られるわけではない
・道路地図における最短経路は三角形の下を通る
→実際の最短経路は三角形の上を通る
↓
今回ほしいのは、その道路地図に従って最短経路を求めると、それ
が実際の最短経路になっていることを保証するような道路地図！！
・最短経路の形状？？
pstartからpgoalまでの経路について考える
・経路をゴムバンドだと考えると、
ゴムバンドはちぢんでできる限り短くなろうとするが、障害物に止められる。
→この新たな経路は障害物の境界の部分と開いた空間に含まれる直線を通る
→このことを定式化すると・・・
補題15.1
互いに共通部分を持たない多角形障害物の集合Sの間を通るpstartとpgoalの間のどの最短
経路も、内側頂点がSの頂点であるような多角形経路である。
Proof)
多角形的であることについて
矛盾を導くために、最短経路τは多角形的でないとする。障害物は多角形的であるから、
自由空間の内部に、ｐを含む線分がτに含まれないような点ｐが存在する。すると、ｐは自由
空間の内部にあるから、ｐを中心とした、自由空間に完全に含まれる円（正の半径）が存在
する。しかし、円の中のτのまっすぐでない一部分は、それを円とまじわる点同士でショート
カットすることができる。任意の最短経路は、局所的にも最短（すべての部分経路はその部
分で最短でなければならない）から、τが最短経路であるという仮定に反する。
頂点について
τの頂点vについて考える。vは自由空間の内部にはない。もし自由空間の内部にあるとす
ると、vを中心とした円は完全に自由空間に含まれ、その経路はvでターンしているので、まっ
すぐな線で置き換えることにより、経路を短くすることができる。また、vは障害物の辺の内部
にはない。もし辺の内部にあるとすると、それを中心とした円が存在し、その半分は、自由空
間に含まれる。そして、再び、まっすぐな線分で置き換えることにより、経路を短くするこがで
きる。よって、τの頂点は、障害物の頂点である。
・これで、最短経路の性質はわかった。
→では、どういう道路地図を用いれば、最短経路を見つけることができるだろうか？？？
↓
Visibility Graph（可視グラフ）
・Sのvisibility graphをGvis(S)と表記する。
・節点は、Sの頂点
・頂点v,wがお互いに見えれば、v,wの間に枝が存在する。
・・つまり、辺vwはSの障害物の内部と交差しない。
→お互いに見える２つの頂点は“Mutually Visible”
→それらを結ぶ線分は、“Visibility Edge”
☆同じ障害物辺の２つの短点は、常にVisible
・・障害物の辺はGvis(S)の枝の部分集合を形成
・補題15.1より、最短経路の線分はvisibility edges（最初と最後の線分を除く）
→Sにスタートとゴールの位置を点として追加すればよい
S* := S∪{pstart,pgoal}
Corollary 15.2
disjointな多角形の障害物の集合Sにおいて、pstartとpgoalとの間の最短経路は、visibility
graph Gvis(S*)の辺から構成される。
これで、最短経路を見つける準備はできた！！！
Algorithm ShortestPath(S,pstart,pgoal)
入力：
disjointな多角形の障害物の集合S
自由空間内の２点pstart,pgoal
出力：
pstartとpgoalを衝突なく結ぶ自由空間内の最短経路
1.
Gvis ← VisibilityGraph(S∪{pstart,pgoal})
2.
Gvisの各枝(v,w)に辺vwの距離を重みとしてアサインする
3.
ダイクストラのアルゴリズムを用い、pstartとpgoal間のGvisにおける最短経路を求める。
時間計算量
Visiblity Graph : O(n2 log n) (n:障害物の辺の総数）
２行目：O(n2) (Gvisの枝の上限はn+2C2)
Dijkstra’s algorithm：O(n log n + k) (k:枝の数）
k=O(n2)であるから、このアルゴリズムの計算量は
O(n2 log n)
15.2 Visibility Graphを求める
Visibility Graphを求める
Sをdisjointな多角形的障害物。辺数はn。
Sのvisibility graphを求めるためには、互いに見える点のペアを見つける必要がある。
↓
すべてのペアに対し、障害物とぶつかるかどうか判定する必要がある。
ナイーブに実装すれば、障害物とぶつかるかどうかの判定はO(n)時間かかる。
・・・全体としてO(n3)時間かかりそう。
このテストをもっと効率よく実行できる方法がある！！！
・・・その前に、まず、アルゴリズムの外枠を考えてみる
Algorithm VisibilityGraph(S)
入力：
disjointな多角形の障害物の集合S
出力：
visibility graph Gvis(S)
1.
Graph G=(V,E)をVを多角形のすべての頂点の集合とし、E=φとして初期化。
2.
For all vertices v∈V
3.
4.
5.
do W ← VisibleVertices(v,S)
Wのすべての頂点wに対し、(v,w)をEに追加
Return G
手続きVisibleVerticesは、多角形の障害物の集合Sと平面内の点pを受け取って、pから
みえる多角形の頂点すべてを返す。
Visible Vertices
頂点wがpからみえるか判定したい
・すべての障害物の辺に関してテスト？
・それまでのテストで得た情報
を使えないだろうか？？？
・・・pからでているすべての線分を、どういう順番で扱えばよいか？
→pの周りのcyclic orderで調べればよい！！
ρ
・辺pwがどの障害物ともぶつからないときに、頂点wはpからみえる。
w
もうちょっと細かくみていくと・・・
p
pを始点として、wを通過する半直線ρを考える。
もし、wが見えないなら、ρはwにたどり着くまえに、障害物の辺にぶつからなければならな
い。
・・・これを確かめるためには、ρによってまじわる障害物の辺に関して頂点wを２分探索
すればよい。→これにより、wがどの辺よりか後ろにあるかどうか確かめることができ
る。
☆pが障害物の頂点だと、wが見えなくなるもう一つのケースがある。
・・・pとwが同じ障害物の頂点で、辺pwがその障害物の内部に含まれる時。このケース
は、ρがwにたどり着く前に障害物の内部に入るかどうか見るために、wに付随する
辺を見ればチェックできる。（wに付随する辺の一つが辺pwに含まれるという縮退の
場合は当分無視）
・pの周りのcyclic orderで頂点を扱っている間、ρによって交わる障害物の辺を平衡探索木T
で扱う。（後でみるように、ρに含まれる辺はTに蓄える必要はない）
・Tの葉は、交差する辺を、左端の葉が最初にρと交わる線分を蓄えるような順番で保持する。
・Tの節点も、辺を蓄える。正確には、内部節点vは左部分木のうちもっとも左にある辺を蓄
える。 → Tの探索をしやすいようにする
e4
e4
e5
e2
e6
e1
e3
e5
e3
e2
e1
e1
e2
e3
e4
e5
e6
・頂点をcyclic orderで扱うということ：半直線ρをpのまわりで回転
→これは、まさに平面走査パラダイムの回転版。
・この回転平面走査の状態は、ρによって交差されている障害物辺のordered sequence。
・走査におけるイベントは、Sの頂点。
・頂点wの処理
・wがpから見えるかどうかをTを探索して調べる
・Tを、wに付随する辺を削除・追加することによって更新
・走査は、正のx軸方向を向いた半直線で始まり、時計周りでまわる。
・・・最初に、各頂点を時計周りにソート。
（pから頂点に伸ばした線分と正方向のx軸のなす角度でソート）
・同じ角度に２点以上の頂点があったら、pから近い順に処理すればよい。
・・・頂点wを処理する前に、辺pwに含まれる頂点を先にしらべればよいのは明白
これで、Visible Verticesを求める準備ができた！！！
Algorithm VisibleVertices(p,S)
入力：
多角形の障害物の集合S、どの障害物の内部にもない点p
出力：
pからみえるすべての障害物辺
1.
2.
3.
4.
5.
6.
7.
8.
障害物の頂点を、pからその点を通る半直線と正方向のx軸が成す時計回りの角度で
ソート。
同じ角度の場合は、pに近い方から先に並ぶようにする。
w1,…,wnをソートされたリストとする。
Ρをpを始点とする、正方向のx軸と平行な半直線とする。
ρと交差している障害物辺を見つけ、それらをρに交差する順番でTに蓄える。
W←φ
for i ← 1 to n
do if Visible(wi) then Add wi to W.
wiに付随する辺のうち、pからwiへの半直線の時計側にあるものをTに挿入
wiに付随する辺のうち、pからwiへの半直線の半時計側にあるものをTから削除
Return W
最後の問題は、Visible手続き。つまり、頂点wiが見えるかどうかを決定する部分。
Subroutine Visible : Consideration
・通常は、pwiと交わるpに一番近い（左端の葉）をTの中から探索すればよい
→問題となるのは、辺pwiの中に点が含まれているとき
＜pwiの中に点が含まれているとき＞
・wi-1が見えない
→wiも見えない
・wi-1は見える
→wiが見えないのは、
・辺wi-1wiがTの中の辺と交差する
・wi-1とwiが同じ障害物の頂点の時に、辺wi-1wiが障害物にある。
時である。
Subroutine Visible(wi)
1. if 辺pwiがwiの近くでwiを頂点とする障害物の内部と交差する
2.
then return false
3.
else if i = 0 or wi-1 は辺pwi上にない
4.
then Tの中から、左端の葉に蓄えられている辺eを探す
5.
if e が存在し、辺pwiがeと交差する
6.
then return false
7.
else return true
8.
else if wi-1 はnot visible
9.
then return false
10.
else Tの中から、辺wi-1wiと交差する辺eを見つける
11.
if eが存在
12.
then return false
13.
else return true
Visible Vertices の完成
VisibleVerticesの時間計算量
pのまわりのcyclic orderでのソート：O(n log n);
・ループの実行
定数回の平衡探索木の走査：O(log n)
定数回の幾何的判定：Constant Time
よって、overall running time は、
O(n log n)
Sの各点(n個)に関してVisibleVewrticesを実行すればVisibility Graphができあがるから、
Theorem 15.4
n辺からなるのdisjointな多角形的障害物の集合Sのvisibility graphは、O(n2logn)時間で求
めることができる。
© Copyright 2024 ExpyDoc
