V. 空間操作.

Slides:



Advertisements
Similar presentations
有限幾何学 第 2 回. 有限幾何学 第 2 回 1. 様々なグラフの例 2. 道と最短経路問題 1. 用語の説明 2. 最短経路問題 3. ダイキストラのアルゴリズム.
Advertisements

地図の重ね合わせに伴う 位相関係の矛盾訂正手法 萬上 裕 † 阿部光敏* 高倉弘喜 † 上林彌彦 ‡ 京都大学工学研究科 † 京都大学工学部 * 京都大学情報学研究科 ‡
地理情報システム論 第11回 GIS による処理技法 アドレスマッチングの利用 空間的分布の特徴の把握.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
区間グラフにおける区間表現からMPQ-treeを効率よく構成するアルゴリズム
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
情報処理演習 (9)グラフィックス システム科学領域 日浦 慎作.
輪読・計算幾何学 第3章 多角形の三角形分割 徳山研究室 M1 鈴木 晶子.
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
画像処理工学 2012年2月2日 担当教員 北川 輝彦.
・力のモーメント ・角運動量 ・力のモーメントと角運動量の関係
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
豊中高校土曜講座「数学セミナー2003」 プラトン多面体の数学 なぜ正多面体は5種類しかないのか 大阪府立豊中高等学校 深川 久.
3DCG技法についての 調査報告 ○○県立○○高等学校 1年は組 グループ0.
曲面上のグラフの彩色 ~種数の増加,面の制限及び局所平面性~
On the Enumeration of Colored Trees
Problem D: Double Sorting 原案: oxy, 解答作成: oxy, nya.
中学数学1年 5章 平面図形 §1 図形の基礎と移動 (7時間).
An Algorithm for Enumerating Maximal Matchings of a Graph
リンク構造を考慮したベクトル空間法によるWebグラフ分割手法に関する研究
前回の内容 結晶工学特論 第4回目 格子欠陥 ミラー指数 3次元成長 積層欠陥 転位(刃状転位、らせん転位、バーガーズベクトル)
宇野 毅明 国立情報学研究所 2002年3月 東北大大学院 情報科学研究科ワークショップ
VI-7 連続分布(面データ)を分析する方法
透視投影(中心射影)とは  ○ 3次元空間上の点を2次元平面へ投影する方法の一つ  ○ 投影方法   1.投影中心を定義する   2.投影平面を定義する
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
階層的境界ボリュームを用いた 陰関数曲面の高速なレイトレーシング法
塩山幾何学を用いた ボロノイ図の解析 立命館高等学校 三村 知洋 宮崎 航輔 村田 航大 塩山幾何学を用いたボロノイ図の解析
s a b f c e d 2016年度 有限幾何学 期末試験 問1:15点
GIS 立地分析への応用 担当 村山祐司 教授 T A  薛 琦.
V. 空間操作.
3次元剛体運動の理論と シミュレーション技法
VI-5 線分布(ネットワークデータ)を分析する方法
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
オーサリングツール&ブラウザの 技術的トピック
顔部品の検出システムの構築 指導教員 廉田浩 教授 1DS04188W  田中 甲太郎.
GISとは・・・ データ処理演習(笹谷担当).
SystemKOMACO Jw_cad 基本操作(6) Ver.1
Data Clustering: A Review
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
第11回   ディジタル画像(2) ディジタル画像処理(2)
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
Hough変換 投票と多数決原理に基づく図形の検出
II. GISデータの種類と構造.
画像処理工学 2013年1月23日 担当教員 北川 輝彦.
第14章 モデルの結合 修士2年 山川佳洋.
G99P043-4 河邊昌彦 G99p094-1 内藤一兵衛 G99P146-1 八幡淳
Computer Graphics 第10回 レンダリング(4) マッピング
VIII. 空間情報表現.
First Course in Combinatorial Optimization
中学数学1年 5章 平面図形 §2 作図 (3時間).
階層的境界ボリュームを用いた 陰関数曲面の高速なレイトレーシング法
貞広幸雄 地理情報システム論 貞広幸雄
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
第2回課題 配布した通り.氏名・学生番号を忘れないこと.
最短ネットワーク問題:シュタイナー問題 3-G 023145 長谷川 和弘.
SystemKOMACO Jw_cad 基本操作(3) Ver.1
第3回 基礎作図 基本的な作図法をしっかりと学ぶ! 本日の課題.
SIFTとGraph Cutsを用いた 物体認識及びセグメンテーション
第16章 動的計画法 アルゴリズムイントロダクション.
アルゴリズムとデータ構造 2011年6月16日
地理情報システム論(総)/ 国民経済計算論(商)
地理情報システム論 第4回 コンピュータシステムおける データ表現(2)
GISとは・・・ デザイン演習A(笹谷担当).
平面走査法を使った 一般線分の 交点列挙アルゴリズム
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
離散数学 11. その他のアルゴリズム 五島.
アルゴリズムとデータ構造 2013年6月20日
第4章 空間解析 2.ネットワーク分析 (2) 最大流問題
市松模様を使用した カメラキャリブレーション
アルゴリズム ~すべてのプログラムの基礎~.
Presentation transcript:

V. 空間操作

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

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

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

3) 点位置決定問題 3 1 2 4 5 7 6 8 9 10

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への入り口となっているノードの番号

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

 そして,始点から近いノードから順に,各ノードへの最短経路を調べていく.

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) 当時間到達圏域の同定