V. 空間操作

空間データの分析手順 視覚による分析（visual analysis） 空間操作（spatial operation） 空間解析（spatial analysis） 空間モデリング（spatial modelling）

V-1　空間操作のための基本的アルゴリズム 　空間操作は，複数のコンピュータアルゴリズムの組み合わせによって実現されている 　人間の目には簡単な判定でも，コンピュータにとっては難しいことが少なくない

1) 線分の交差判定問題 2) 線分の交差列挙問題

3) 点位置決定問題 ３ １ ２ ４ ５ ７ ６ ８ ９ １０

4) 凸包問題

5) 全最近点問題

6) 可視性問題

7) 最短経路問題 　いくつものアルゴリズムがあるが，最も良く用いられるのはDijkstra法（ラベル確定法）である．

3 2 3 4 4 8 5 4 9 1 6 8 5 3 7 5

Dijkstra法の手順 　しらみ潰し法 　始点を与えると，そこから各ノードへ至る最短経路を始点の近辺から次々と求めていき，それが終点に至った段階で探索を終了する．

各ノードには，ラベルと呼ばれる符号を付ける ノードiにつけるラベルを(a, pi)と表す． 　pi：始点からノードiへ至る現時点での（探索途中段階での）最短経路の長さ 　a：始点からノードiへ至る最短経路の，ノードiへの入り口となっているノードの番号

ラベルには二種類ある． 　永久ラベル：始点からの経路探索が終了し，最短経路が確定したノードにつけられるラベル ( , ) 　仮ラベル：始点からの最短経路が確定していないノードにつけられるラベル [ , ] 終点に永久ラベルが付けられた時点で探索終了

1. 各ノードに初期ラベルを付ける 探索開始前なので， 　始点ノードには仮ラベル(*, 0)， 　その他のノードには仮ラベル(φ, ∞) と書き込む．

2 (φ, ∞) 3 (φ, ∞) 3 4 4 8 5 4 (φ, ∞) 9 1 (*, 0) 6 (φ, ∞) 8 5 3 7 (φ, ∞) 5 (φ, ∞)

2. 終点に永久ラベルが付いていれば探索を終了． 　そうでなければ，仮ラベルの付いているノードのうち，pi：（始点からノードiへ至る現時点での最短経路の長さ）の最小なノードを探し，ステップ3へ． 　ここで，見つかったノードへの最短経路はこの時点で確定することに注意

2 (φ, ∞) 3 (φ, ∞) 3 4 4 8 5 4 (φ, ∞) 9 1 (*, 0) 6 (φ, ∞) 8 5 3 7 (φ, ∞) 5 (φ, ∞)

3. 見つかったノード（番号をsとする）に直接リンクしている全ての仮ラベル付きノードを調べる 　sに直接リンクしているノードjについて，pi　と　ps+d(s, j)を比較する．これは，sに直接リンクしているノードへの最短経路として，ノードsを経由するルートがその候補となるかどうかを調べる作業である． s

piとps+d(s, j)のうち， 　piが小さければそのまま 　ps+d(s, j) が小さければ，ノードjに仮ラベル (s, ps+d(s, j)) を付ける． 　sに直接リンクしている全てのノードを調べ終えたら，ノードsのラベルを永久ラベルとし，ステップ2へ

　ステップ2と3を繰り返す間に，終点ノードに永久ラベルが付けられるので，それによって探索を終了する．

2 (1, 4) 3 (φ, ∞) 3 4 4 8 5 4 (φ, ∞) 9 1 [*, 0] 6 (φ, ∞) 8 5 3 7 (φ, ∞) 5 (φ, ∞)

2 [1, 4] 3 (2, 7) 3 4 4 8 5 4 (φ, ∞) 9 1 [*, 0] 6 (2, 9) 8 5 3 7 (φ, ∞) 5 (φ, ∞)

2 [1, 4] 3 [2, 7] 3 4 4 8 5 4 (3, 11) 9 1 [*, 0] 6 (2, 9) 8 5 3 7 (φ, ∞) 5 (φ, ∞)

2 [1, 4] 3 [2, 7] 3 4 4 8 5 4 (3, 11) 9 1 [*, 0] 6 [2, 9] 8 5 3 7 (6, 14) 5 (6, 12)

2 [1, 4] 3 [2, 7] 3 4 4 8 5 4 [3, 11] 9 1 [*, 0] 6 [2, 9] 8 5 3 7 (6, 14) 5 (6, 12)

2 [1, 4] 3 [2, 7] 3 4 4 8 5 4 [3, 11] 9 1 [*, 0] 6 [2, 9] 8 5 3 7 (6, 14) 5 [6, 12]

2 [1, 4] 3 [2, 7] 3 4 4 8 5 4 [3, 11] 9 1 [*, 0] 6 [2, 9] 8 5 3 7 [6, 14] 5 [6, 12]

　はじめにも述べたとおり，Dijkstra法は基本的に虱潰し法である．そのため，無駄な経路探索が多く行われ，効率が悪い．そのため，様々な効率的探索方法がこれまで提案されてきており，カーナビゲーションシステムではそのような改良法が一般に用いられている．

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-3　空間的検索 1) ポイントに基づく検索 　　距離による検索 　　　○○から□□m以内にある空間オブジェクト

2) ラインに基づく検索 　　距離による検索 　　　○○から□□m以内にある空間オブジェクト 　　位相による検索 　　　○○と交差する空間オブジェクト

3) ポリゴンに基づく検索 　　距離による検索 　　　○○から□□m以内にある空間オブジェクト 　　位相による検索 　　　○○と交差する空間オブジェクト 　　　○○が内包する空間オブジェクト 　　　○○を内包する空間オブジェクト

V-4　バッファリング 空間オブジェクトから一定距離内にある範囲の同定 オブジェクトごとにバッファ半径を変更することも可能

ひったくり・・・ 　中幅員道路に多い 空き巣ねらい・・・ 　駐車場から15mの範囲に多い 車上狙い・・・ 　河川沿い及び商業施設から25mの範囲に多い

V-5　ボロノイダイアグラム 　空間の各オブジェクトについて，それぞれを最近隣とする領域分割 　ボロノイダイアグラムを作成することで，空間の各地点における最近隣のオブジェクトが簡単にわかる

Voronoi diagram

ボロノイダイアグラムの応用 1) 機能に差異のない都市施設の利用圏同定 　　　例：郵便局，コンビニエンスストア 2) 最不便地点の同定（最大空円問題） 　　　点分布の凸包の内部において，最寄りの点までの距離が最も遠い地点

Application of Voronoi diagram

ボロノイダイアグラムの作成方法 1) 単純な方法 　　　各点対の垂直二等分線で形成される半平面の共通部分を求める． 2) 逐次添加法 　　　点が2個の場合から開始し，一つずつ点を追加しながらボロノイダイアグラムを更新する．

Construction of Voronoi diagram

　ボロノイダイアグラムは点だけではなく線や面に対しても構築することができる．

Voronoi diagram for line segments

V-6　ドローネ三角網 　ボロノイダイアグラムの双対グラフ

Delaunay triangulation

　全ての点の中から3点を選び，その外接円を描く．そのとき，円内にその3点以外の点が含まれなければ，それらを三角形として結ぶ．この作業を全ての3点の組み合わせについて行ったとき，最終的に得られる三角形分割をドローネ三角網と呼ぶ．

Construction of Delaunay triangulation

　平面において点分布が与えられたとき，点を頂点とする三角形分割には様々なものが有り得る．その中で，最も三角形のゆがみが少ない分割，より正確に言えば， 　各三角形内の最小角を小さい順に並べたとき，角順位での角度を最大にする という三角形分割である．

Two triangulations

ドローネ三角網の応用 1) 「自然な」隣接点の定義（画像処理，視覚分析） 2) 補間に適した空間分割方法 3) 最小木（minimum spanning tree）の探索

Minimum spanning tree

V-7　3次元解析 　GISでは，平面上の一点に対して一つの値を定めるという形で3次元を扱う．この方法は2.5次元などと呼ばれる． 　3次元解析で用いられるデータは，いくつかの標本点において得られている値を補間して構成される曲面である．

1) 等値線（等高線）の作成 　一つ一つの値に対して，一つずつ等値線を描く 　a) 全ての線分の両端値を調べ，現在描いている等値線の値がその中に含まれるかどうかをみる． 　b) 現在描いている等値線の値を含む線分を輪郭の一部とする全ての三角形について，等値線を描く．

90 90 140 140 80 50 80 50 100 120 120 130 130 100 110 110 70 70 50 50 20 20 60 60 等値線の作成

2) 断面図の作成 　断面を定める線と各線分の交点を調べ，直線分で結んでいく． 　鉄道や道路の線形計画で用いられる．

90 140 80 50 120 130 100 X 50 110 Y 70 50 X Y 20 60 断面図の作成

3) 可視領域の同定 　視点から視線を発生し，その直線と周囲の3次元データとの交点を求める．その作業を，視線を順次回転させながら行う． 　要するに，ほとんとしらみ潰しと考えて良い．

90 90 140 140 80 50 80 50 120 120 130 130 110 110 70 70 50 50 20 20 60 60 可視領域の同定

可視領域同定の応用 　展望台・遊歩道の設置 　「富士山がどこまで見えるか」 　アンテナ・反射板・中継局の設置

4) 傾斜角度の方向の計算 　　スキー場の計画 5) 体積計算 　　土量計算 6) 鳥瞰図の作成 　　建物の広域配置計画

V-8　ネットワーク解析 1) 最短経路探索 2) 当時間到達圏域の同定