地理情報システム特論第 4 回：空間演算の基本 - 大沢研究室

.
.
.
..
.
.
.
地理情報システム特論
第 4 回：空間演算の基本
大沢裕
埼玉大学
.
Ohsawa (Saitama Univ.)
GIS-4
1 / 16
GIS-4
2 / 16
.
. .1 凸包
.
. .2 平面走査
.
. .3 Voronoi Diagram
.
. .4 座標への順序づけ
.
Ohsawa (Saitama Univ.)
.
凸包
凸包
全ての点を内包する，最もタイトな凸多角形
.
Ohsawa (Saitama Univ.)
GIS-4
3 / 16
凸包
素朴な方法
凸包を求める対象となる点の集合を
P = {p1 , p2 , . . . , pn } とする．
.1. 最初の 3 点を取り出し，この 3 点からなる凸
包を H3 と表す．
.. i をインクリメントしつつ，i ≤ n のうち，以
2
.
.
下の処理を繰り返す．
(1) 点 pi が凸包 Hi−1 の内部点の場合
(以下，これを pi ∈ Hi−1 と表す
ことにする)：この時には，凸包
の形は変わらない．従って
Hi = Hi−1 となる．
(2) pi ̸∈ Hi−1 の場合：以下で述べる
[凸包への点の追加] を実行する．
この処理により，Hi は，点 pi を
頂点に持つ形に更新される．
.
Ohsawa (Saitama Univ.)
GIS-4
4 / 16
.
凸包
逐次添加法による凸法の構築
3L
3P
3L
3P
3P
3N
3P
3N
+L +L
3N
3N
D
E
pi が Hi−1 の外部点のとき，
Hi−1 を時計回りに調べ，pi が辺 pm−1 pm の右側であり，かつ
pm pm+1 の右側になる pm を探す．
同様に，辺 pk−1 pk の左側にあり，pk pk+1 の右側になる pk を探す．
pi ,pm ,pk を図のように結び Hi を作る．
.
Ohsawa (Saitama Univ.)
GIS-4
5 / 16
凸包
アルゴリズムの評価
3L
3P
3L
3P
3P
3N
3P
3N
+L +L
3N
3N
D
E
pi が追加されたとき，Hi−1 を構成する全ての頂点に対して，pi の内
外判定を必要とする：O(i)
pi が外部点のとき，pm と pk を求める：O(i)
新しい Hi を構築する：O(i)
以上の処理を i = 4 から i ≤ n のうち繰り返す．従って，全体のコストは
O(n2 ) となる．
.
Ohsawa (Saitama Univ.)
GIS-4
6 / 16
.
凸包
構築コストの削減
&X
3X
3L
3L
3
3O
&O
点列を x 値でソートする：追加される pi は必ず Hi−1 の外部点になる
凸包の頂点を pq , . . . , pi−1 で上下に分割する．上側の単調な点列を
Cu = {p1 , . . . , pi−1 } とし，下側の単調な点列を Cl = {pi−1 , . . . , p1 }
と表す．接線を求める処理の効率が向上する．接線を求める処理で
取り除かれる点は，以降の処理で対象とならないことから，接線を
求める処理は全体で O(n)
点の追加処理は全体で O(n)
支配的な処理は，最初に行われる点列のソート：O(n log n)
全体的な処理量も O(n log n)
.
Ohsawa (Saitama Univ.)
GIS-4
7 / 16
凸包
Graham のアルゴリズム
Step 1. 点集合中の左端の点を求め，この点を v0
とする．もし同じ x 値を持つ点が複数あ
れば，y 値が最小の点を求め v0 とする．
Step 2. v0 以外の点を x 軸から反時計回りの角度
で昇順にソーティングし，そのソートさ
れた順に v1 , v2 , v3 , . . . , vn−1 とする．
\
Step 3. 結果の凸包の頂点を {e1 , e2 , . . .} と表す．
まず，e0 = v0 , e1 = v1 ，k = 1 とおく．
Step 4. vj (2 ≤ j ≤ n − 1) に対して以下の処理を
行う．
Step 4.1 3 点 ek−1 , ek , vj (2 ≤ j ≤ n − 1) が作る
三角形 ek−1 ek vj の符号付面積 S を求め，
それが 0 または負であれば k = k − 1 と
する．逆に S が正であれば k = k + 1 と
し，ek を vj とする．
Y
Y
Y
Y
Y
[
処理量：Step1(O(1)),Step2(O(n log n)),Step3(O(1)),Step4(O(n))
全体で：O(n log n)
.
Ohsawa (Saitama Univ.)
GIS-4
8 / 16
.
平面走査
線分同士の交点を全て求める：問題の単純化
最初に問題を単純化するため，以下の制約を置く
(1) y 軸に平行な (垂直な）線分は存在しない (a)．
(2) 3 本以上の線分が同一点で交わることがない (b)．
(3) 線分の交点を端点とする線分は存在しない (c)．
U
U
U
U
U
U
U
U
U
C
.
Ohsawa (Saitama Univ.)
D
U
U
U
E
GIS-4
9 / 16
平面走査
平面走査
V
直線 ℓ と交わる線分のみを対象
とする
交差するかのチェックは，直線
上で隣り合う線分に対してのみ
行えばよい
V
以下の 3 種類の変化をイベント
と呼ぶ
V
l
...
...
...
.
1
線分の左端点 (新しい線分 sn が ℓ 上に現れる)
2
線分の右端点 (線分 so が ℓ 上から消える)
3
線分間の交点 (線分 s1 と s2 の順序が入れ替わる)
Ohsawa (Saitama Univ.)
GIS-4
10 / 16
.
平面走査
平面走査のアルゴリズム
初期処理線分の左端点及び右端点を x 値で昇順にソートしたイベントリスト E を作成する．
また，L を空集合とする O(n log n)
ループ E が空でないうち以下の処理を繰り返す．
要素の取り出し E の最小要素を取り出し，そのイベントを p とする．O(log n)
p が線分 s の左端点 insert(s,L); s1=above(s,L); s2=below(s,L);O(log n)
もし，s1 が s と交わるなら，E に s1 と s の交点を追加
もし，s2 が s と交わるなら，E に s2 と s の交点を追加
p が線分 s の右端点 s1=above(s,L); s2=below(s,L); delete(s,L);O(log n)
もし，s1 と s2 が p の右側で交わるなら，E に s1 と s2
の交点を追加
p が線分 s1 と s2 との交点 s3=above(s1,L); s4=below(s2,L);O(log n)
もし，s2 と s3 が p の右側で交わるなら，E に s2 と s3
の交点を追加
もし，s1 と s4 が p の右側で交わるなら，E に s1 と s4
の交点を追加
L 中で s2 と s1 を交換
全体のコスト：O(n log n)
.
Ohsawa (Saitama Univ.)
GIS-4
11 / 16
平面走査
多角形の重なり
5N
座標軸に平行な辺を持つ矩形の重なりを持
つペアを列挙する
#
'
BとC
%
CとD
$
&
N
全矩形の集合を R とする．また各矩形の左右の端をその x 座標値で昇順にソートしたリストを E と
する．次に，Rl を空とし，E の要素 e を，x 座標値が小さいものから順に次の様に処理する．
(1) e が矩形 r の左端の場合，r を Rl に追加する．その結果作られる Rl 内部で１次元
データ間の重なりを調べる．
(2) e が矩形 r の右端の場合，r を Rl から削除する．r はこれ以降，どの矩形とも重な
りを持たない．
E の昇順ソート：O(n log n), (1) 重なり:O(log n)，(1) 追加削除：(O(n))
全体の処理量：O(n log n)
.
Ohsawa (Saitama Univ.)
GIS-4
12 / 16
.
Voronoi Diagram
Voronoi Diagram (1)
.
Ohsawa (Saitama Univ.)
GIS-4
13 / 16
Voronoi Diagram
Voronoi Diagram (2)
ある点 q が与えられたとき，点群 P に対して Voronoi 図が作成され
ていれば，P における q の最近点を求める演算は，領域決定問題と
なる．
q がどの Voronoi ポリゴンに含まれるかの決定には，R 木などの空間
索引構造を用いることができる．
.
Ohsawa (Saitama Univ.)
GIS-4
14 / 16
.
座標への順序づけ
スキャン順序
x 座標値による順序づけ
Z-order
Peano-Hilbert スキャン
.
Ohsawa (Saitama Univ.)
GIS-4
15 / 16
座標への順序づけ
まとめ
幾何図形などにおける効率解法を研究する分野に計算幾何学がある．
計算幾何学分野の代表的問題に凸包問題がある．
Graham Scan や逐次添加法により，n 点の集合の凸包を O(n log n)
で求めることができる．
最近接オブジェクトの検索に Voronoi 図を用いることができる．
Peano-Hilbert スキャンや，Z スキャンにより，2 次元点データに 1
次元順序をつけることができる．特に，Peano-Hilbert スキャンでは
空間的な位置が近接している点に対して近い番号を付けることがで
きる（但し，逆は成り立たない）．
.
Ohsawa (Saitama Univ.)
GIS-4
16 / 16

Download Report