Document

V. 空間操作
V. 空間操作
空間データの分析手順
1.
視覚による分析（visual analysis）
2.
空間操作（spatial operation）
3.
空間解析（spatial analysis）
4.
空間モデリング（spatial modelling）
V. 空間操作
V-1 空間操作のための基本的アルゴリズム
空間操作は，複数のコンピュータアルゴリズムの
組み合わせによって実現されている
人間の目には簡単な判定でも，コンピュータに
とっては難しいことが少なくない
V. 空間操作
1) 線分の交差判定問題
2) 線分の交差列挙問題
V. 空間操作
3) 点位置決定問題
２
１
４
８
３
５
７
６
９
１０
V. 空間操作
4) 凸包問題
V. 空間操作
5) 全最近点問題
V. 空間操作
6) 可視性問題
V. 空間操作
7) 最短経路問題
いくつものアルゴリズムがあるが，最も良く用いら
れるのはDijkstra法（ラベル確定法）である．
2
3
3
4
4
8
5
4
9
1
6
5
7
3
8
5
V. 空間操作
Dijkstra法の手順
しらみ潰し法
始点を与えると，そこから各ノードへ至る最短経路
を始点の近辺から次々と求めていき，それが終点に
至った段階で探索を終了する．
V. 空間操作
各ノードには，ラベルと呼ばれる符号を付ける
ノードiにつけるラベルを(a, pi)と表す．
pi：始点からノードiへ至る現時点での（探索途中
段階での）最短経路の長さ
a：始点からノードiへ至る最短経路の，ノードiへの
入り口となっているノードの番号
2 (φ, ∞)
3 (φ, ∞)
3
4
5
4
8
4 (φ, ∞)
9
1 (*, 0)
6 (φ, ∞)
5
7 (φ, ∞)
3
8
5 (φ, ∞)
V. 空間操作
そして，始点から近いノードから順に，各ノードへ
の最短経路を調べていく．
2 (1, 4)
3 (φ, ∞)
3
4
5
4
8
4 (φ, ∞)
9
1 [*, 0]
6 (φ, ∞)
5
7 (φ, ∞)
3
8
5 (φ, ∞)
2 [1, 4]
3 (2, 7)
3
4
5
4
8
4 (φ, ∞)
9
1 [*, 0]
6 (2, 9)
5
7 (φ, ∞)
3
8
5 (φ, ∞)
2 [1, 4]
3 [2, 7]
3
4
5
4
8
4 (3, 11)
9
1 [*, 0]
6 (2, 9)
5
7 (φ, ∞)
3
8
5 (φ, ∞)
2 [1, 4]
3 [2, 7]
3
4
5
4
8
4 (3, 11)
9
1 [*, 0]
6 [2, 9]
5
7 (6, 14)
3
8
5 (6, 12)
2 [1, 4]
3 [2, 7]
3
4
5
4
8
4 [3, 11]
9
1 [*, 0]
6 [2, 9]
5
7 (6, 14)
3
8
5 (6, 12)
2 [1, 4]
3 [2, 7]
3
4
5
4
8
4 [3, 11]
9
1 [*, 0]
6 [2, 9]
5
7 (6, 14)
3
8
5 [6, 12]
2 [1, 4]
3 [2, 7]
3
4
5
4
8
4 [3, 11]
9
1 [*, 0]
6 [2, 9]
5
7 [6, 14]
3
8
5 [6, 12]
V. 空間操作
はじめにも述べたとおり，Dijkstra法は基本的に虱
潰し法である．そのため，無駄な経路探索が多く行
われ，効率が悪い．そのため，様々な効率的探索方
法がこれまで提案されてきており，カーナビゲーショ
ンシステムではそのような改良法が一般に用いられ
ている．
V. 空間操作
V-2 重ね合わせ
重ね合わせにもいろいろな方法がある
overlay 1: intersect （ANDの操作）
overlay 2: union （ORの操作）
overlay 3: identity
overlay 4: clip
overlay 5: erase
overlay 6a: update (keepborder)
overlay 6b: update (dropborder)
V. 空間操作
V-3 空間的検索
1) ポイントに基づく検索
距離による検索
○○から□□m以内にある空間オブジェクト
V. 空間操作
2) ラインに基づく検索
距離による検索
○○から□□m以内にある空間オブジェクト
位相による検索
○○と交差する空間オブジェクト
V. 空間操作
3) ポリゴンに基づく検索
距離による検索
○○から□□m以内にある空間オブジェクト
位相による検索
○○と交差する空間オブジェクト
○○が内包する空間オブジェクト
○○を内包する空間オブジェクト
V. 空間操作
V-4 バッファリング
空間オブジェクトから一定距離内にある範囲の同定
オブジェクトごとにバッファ半径を変更することも可能
V. 空間操作
ひったくり・・・
中幅員道路に多い
空き巣ねらい・・・
駐車場から15mの範囲に多い
車上狙い・・・
河川沿い及び商業施設から25mの範囲に多い
V. 空間操作
V-5 ボロノイダイアグラム
空間の各オブジェクトについて，それぞれを最近隣
とする領域分割
ボロノイダイアグラムを作成することで，空間の各
地点における最近隣のオブジェクトが簡単にわかる
Voronoi diagram
V. 空間操作
ボロノイダイアグラムの応用
1) 機能に差異のない都市施設の利用圏同定
例：郵便局，コンビニエンスストア
2) 最不便地点の同定（最大空円問題）
点分布の凸包の内部において，最寄りの点まで
の距離が最も遠い地点
Application of Voronoi diagram
V. 空間操作
ボロノイダイアグラムの作成方法
1) 単純な方法
各点対の垂直二等分線で形成される半平面の
共通部分を求める．
2) 逐次添加法
点が2個の場合から開始し，一つずつ点を追加
しながらボロノイダイアグラムを更新する．
Construction of Voronoi diagram
V. 空間操作
ボロノイダイアグラムは点だけではなく線や面に対
しても構築することができる．
Voronoi diagram for line segments
V. 空間操作
V-6 ドローネ三角網
ボロノイダイアグラムの双対グラフ
Delaunay triangulation
V. 空間操作
全ての点の中から3点を選び，その外接円を描く．
そのとき，円内にその3点以外の点が含まれなけれ
ば，それらを三角形として結ぶ．この作業を全ての3
点の組み合わせについて行ったとき，最終的に得ら
れる三角形分割をドローネ三角網と呼ぶ．
Construction of Delaunay triangulation
V. 空間操作
平面において点分布が与えられたとき，点を頂点
とする三角形分割には様々なものが有り得る．その
中で，最も三角形のゆがみが少ない分割，より正確
に言えば，
各三角形内の最小角を小さい順に並べたとき，角
順位での角度を最大にする
という三角形分割である．
Two triangulations
V. 空間操作
ドローネ三角網の応用
1) 「自然な」隣接点の定義（画像処理，視覚分析）
2) 補間に適した空間分割方法
3) 最小木（minimum spanning tree）の探索
Minimum spanning tree
V. 空間操作
V-7 3次元解析
GISでは，平面上の一点に対して一つの値を定め
るという形で3次元を扱う．この方法は2.5次元などと
呼ばれる．
3次元解析で用いられるデータは，いくつかの標本
点において得られている値を補間して構成される曲
面である．
V. 空間操作
1) 等値線（等高線）の作成
一つ一つの値に対して，一つずつ等値線を描く
a) 全ての線分の両端値を調べ，現在描いている等
値線の値がその中に含まれるかどうかをみる．
b) 現在描いている等値線の値を含む線分を輪郭
の一部とする全ての三角形について，等値線を
描く．
90
90
140
140
80
80
50
50
100
120
120
130
130
100
110
110
70
50
60
20
70
50
60
等値線の作成
20
V. 空間操作
2) 断面図の作成
断面を定める線と各線分の交点を調べ，直線分で
結んでいく．
鉄道や道路の線形計画で用いられる．
90
140
80
50
120
100
130
X
110
Y
70
50
60
20
50
0
X
断面図の作成
Y
V. 空間操作
3) 可視領域の同定
視点から視線を発生し，その直線と周囲の3次元
データとの交点を求める．その作業を，視線を順次
回転させながら行う．
要するに，ほとんとしらみ潰しと考えて良い．
90
90
140
140
80
80
50
120
50
120
130
110
130
110
70
50
60
20
70
50
可視領域の同定
60
20
V. 空間操作
可視領域同定の応用
展望台・遊歩道の設置
「富士山がどこまで見えるか」
アンテナ・反射板・中継局の設置
V. 空間操作
4) 傾斜角度の方向の計算
スキー場の計画
5) 体積計算
土量計算
6) 鳥瞰図の作成
建物の広域配置計画
V. 空間操作
V-8 ネットワーク解析
1) 最短経路探索
2) 当時間到達圏域の同定

Download Report