CSIS Discussion Paper Series #32

空間的連続面の構造的特徴を抽出する手法

増山

篤・岡部 篤行

東京大学大学院工学系研究科都市工学専攻〒113‑8656 東京都 文京区 本郷 7‑3‑1

CSIS Discussion Paper Series #32

1. はじめに
空間的連続面（曲面）は，点・線・面と並び，GIS における重要な空間オブジェクトタ
イプの一つである（Goodchild, 1992; Berry, 1999）．例えば，気温分布，大気中におけるNOx の分布，地形などの自然現象の多くは曲面として扱われる現象である．また，都市内
人口分布のように，社会現象の中にも曲面として扱われるものもある．さらには，Kernel 推
定法(Silverman, 1986)のように，元は点データであっても，その分布の密度強度の曲面化という操作が行われることもある．しかしながら，こうした曲面の構造の把握・分析は，
主として視覚的に行われており，その分析結果は，分析者の主観に依存する部分が大きい．
もちろん，これまでも，曲面の構造を何らかの方法で計量的に記述・分析しようという試みは，いくつか行われてきた．計量地理学分野において，その初期の頃から用いられてきた手法としては，傾向面分析がある．傾向面分析とは，曲面を多項式で近似し，その多項式の係数をみることによって曲面の構造を把握するという手法であるが，多項式の次数が高くなると，その係数の解釈が容易ではなくなるという欠点を持っている（Hagett andBassett, 1970）．そこで，曲面の位相的構造をより明示的に取り扱うグラフ理論的手法が提案された（Warntz, 1966; Pfaltz, 1976; Okabe, 1981; Okabe and Masuda, 1984）．具
体的には，曲面上のピーク（頂点），コル（鞍点），ボトム（谷底）を見つけ，それらに関して接続関係を定義したグラフを用いて，曲面構造の記述・分析が行われてきた．しかしながら，後に述べるように，このグラフは，その上に曲面が定義される二次元領域を連続的に変換することによって曲面を変形したときに，必ずしも不変ではなく，曲面構造の記述法として必ずしも好ましくないように思われる．また，その手法の背後にある連続関数としての曲面に関する理論を実際の離散化されたデータに適用する上で問題がある．
これに対し，画像処理分野においては，画像の構造を記述するために提案された領域木（contour tree）と呼ばれる手法がある（van Kreveld et al., 1997; 浅野, 1999）．この論文では，先のグラフが同型ではなくなるような場合であっても，領域木は不変であることを示す．また，連続関数に関する理論を離散化されたデータに適用する上で，問題が生じないことを示し，メッシュデータから領域木を求めるアルゴリズムを詳述する．さらに，
このアルゴリズムにしたがって作成されたプログラムの実行例を示す．最後に，これらを用いて，単一曲面の骨格的な構造のみを把握する手法を提案する．

2. 連続関数として表される曲面に関する理論
ここでは，まず，数学的に連続な関数として表現される曲面について，その特異点，等
高線，および，それらを用いた曲面構造の記述法をみていくことにしよう．

CSIS Discussion Paper Series #32

2‑1

特異点

今，二次元ユークリッド平面上の点を ( x, y ) とし，この平面上の領域を D とする．このとき，曲面 z = f ( x, y ) を， D 上において定義される連続かつ二階微分可能な関数とする．

f ( x, y ) に関し，∂f ( x, y ) = 0
∂x

(1)

∂
f ( x, y ) = 0∂y(2)

を同時に満たす点を，この論文では，特異点と呼ぶことにする．特異点は，さらに 3 種類に分類される．図 1 にあるように，極大値をとる点をピーク，極小値をとる点をボトム，
峠 のようになっている点のことをコルと呼ぶことにする．また，式(1),(2)の少なくとも一方が満たされないときには，スロープと呼ぶことにする．ここでは直観的に説明したが，数学的に厳密に言うと，次のようになる．今，式(3)のように， f を点 ( x, y ) の周りで二次の項までテーラー展開する．

f ( x, y ) = a11 x 2 + a 22 y 2 + 2a12 xy + 2a14 x + 2a 24 y + a 44(3)

この係数を並べた行列

aA =  11
 a12

a12 

a 22 

(4)を考えたとき，特異点の中で， A > 0 , a11 > 0 を満たすものをピーク， A > 0 , a11 < 0を満たすものをボトム， A < 0 を満たすものをコル，と定義する．なお， A = 0 の場合は，その点の性質を判定することはできない．ここで分かるように，行列 A を求めるためには，

f の二階導関数が必要であり，したがって，連続関数として表現される曲面において，特異点は二階微分を用いて定義される．

CSIS Discussion Paper Series #32

2‑2

等高線

まず， D 上において，

 ∂f ∂f V ( x, y ) =  ∂x , ∂y 

(5)で与えられるベクトル場 V を考える．ここで， V ( x, y ) は点 ( x, y ) における最急上昇方向である．次に， V と双対なベクトル場 V * は

 ∂f
∂f 
V * ( x, y ) = 
− 

 ∂y
 , ∂x (6)と定義される．このとき，V * ( x, y ) の積分曲線がいわゆる等高線である．この積分曲線（等高線）に関しては，ピークの十分近くでは，反時計回りに回るという性質がある．逆に，ボトムの十分近くでは，等高線は時計回りに回る．図 2 における矢印は，このような等高線の向きを表している．さらに，等高線に関しては，コルを通らない場合は，閉じた領域
を一つだけ形成するが，コルを通る場合は二つ（以上）の閉じた領域を形成し，そして，
コルを通る等高線によって形成された複数の閉じた領域同士は，そのコルを共有するという性質も持っている．

2‑3 曲面構造の記述法
上のように定義される特異点，等高線を使って曲面の構造を表す手法をみてみると，その一つに，グラフ理論的手法がある．この手法を簡単に説明すると，任意のコルを通るV ( x, y ) の積分曲線によって特異点同士の接続関係を定義し，グラフとして表現するという方法である．図 2 において点線を用いて表されているグラフは，そうしたグラフの例である．実際に，この手法を用いた既存研究としては Okabe (1981), Okabe and Masuda (1984)
における都市内人口分布構造の解析などが挙げられる．
しかしながら，このグラフは，領域 D の連続的な変換に対して必ずしも不変ではなく，曲面構造を把握する手法として，必ずしも適切ではない．例えば，図 3 の二つの曲面を考えてみよう．このとき，図 3(a)では，ピークが直線状に並んでいるのに対し，図 3(b)では，ピークが三角形をなすように並んでおり，ピーク・ボトム・コルを積分曲線によって結んだグラフを求めると，それぞれの図における点線のようになる．一方，これらの曲面は，

CSIS Discussion Paper Series #32

その上に曲面が定義されている領域について適切な連続変換を考えたときに互いに移し替えることができる．したがって，これらは位相的に同一であると捉え，次に，その特異点の配置パターンなどをみることによって，形状の相違を把握するのが，ごく自然な方法だと思われるが，先のグラフを使う限り，そのように捉えることはできない．
では，図 3(a),(b)の二つ曲面を位相的に同一と捉えるような手法とは何かということになるが，これが冒頭で述べた領域木(contour tree)である．領域木とは，コルを通る等高線によって形成される閉じた領域における最も低い値をとる特異点（コルを含む）とコルをノードとし，値の高い方から低い方へ有向枝を引くことによって生成される木（浅野,1999）のことである．例えば，図 4(a)のような曲面が与えられている場合には，その構造を表す領域木は，図 4(b)のようになる．図 4 からも分かるように，領域木においては，端点（次数 1 となるノード）は，ピークもしくはボトムに対応している．一方，次数が 3 以上となっている点はコルに対応している．また，領域木の一本のリンクは，コルを通る等高線によって囲まれる領域に対応している．例えば，図 4(a)においてハッチのかかっている領域と領域木における 2 点 B,C を結ぶリンクは対応している．
さて，次に，この領域木を得る方法について考えてみることにするが，その前に， D 上の任意の点に関する以下の性質を述べておく．今， D 上の点 ( x, y ) をとり，h = f ( x, y ) が成り立っているとする．次に，十分小さな正数 ε をとり， xy 平面に平面に平行な二つの平
面 z = h + ε , z = h − ε で f ( x, y ) を切ったとする．このとき，点 ( x, y ) の性質とその付近の切り口に現れる等高線の形状変化の関係は図 5 のようになる（この図において，ハッチのかかっている領域においては，曲面が上にあるものとする）．この図に示すように，もし，点 ( x, y ) の周りに等高線が現れるならば，等高線内部にピークがあり，逆に点 ( x, y ) を囲
む等高線が消える場合には，等高線内部にボトムがあり，二つの等高線によって囲まれる領域（ハッチのかかった領域）が接する場合には，接点においてコルとなっている．したがって，まず， h の初期値として十分大きな値（ f が D 上においてとる最大値）をとり，連続的に，少しずつ h を小さくしながら，その値で曲面を切り，切り口に現れる等高線の変化パターンをみることで特異点を抽出することができる．そして，この特異点を見つける毎に，領域木の位相構造も変えていけばよい．具体的には，図 5(a)‑(d)にあるにように，
ピークならば，新たに領域木のリンクを付け足し，ボトムならば，そこでリンクの終点とし，コルならば，リンクの合流あるいは分岐を行い，スロープならば，そのままにしておけばよい．そして，十分小さな値（ f が D 上においてとる最小値）まで下りていけばよい．
このようにして領域木を得ることができる．

CSIS Discussion Paper Series #32

3 メッシュデータからの領域木構成手法
3‑1 連続関数に関する理論の離散データへの適用可能性
GIS において，実際に曲面を扱う際には，数学的に連続な関数としてではなく，メッシ
ュデータのように離散化された形で扱う場合がほとんどである．そこで，ここでは，連続な関数に関する理論の離散的なデータへの応用可能性について考えてみよう．
特異点は先に述べたように，数学的には曲面を表す関数 f の二階微分を用いて定義できる．しかしながら，この理論は離散化されたデータには直ちに適用できない．例えば，メッシュデータにおける二階微分（数値微分）は，その計算結果がメッシュにおける座標軸の取り方に依存する（赤松, 1968）．したがって，式(1)‑(4)に基づいて特異点を決定することはできない．特異点同士を結ぶグラフによって曲面構造を把握する手法においては，まず，特異点を見つけることが重要であるにも関わらず，ここで連続関数としての曲面に関する理論を実際のデータに適用する上で問題があることが分かる．
一方，領域木では，切り口に現れる等高線の形状変化が問題となるが，これは連続から離散に移る上で，特に問題が生じることはない．例えば，メッシュデータを考えてみよう．
今，隣接する二つのメッシュがあり，それぞれ z1 , z 2 という値を持っているとする．このとき，この二つのメッシュが共有する辺を z1 と z 2 の間の値を持つ等高線としてごく自然に定義でき，したがって，等高線の形状変化もごく自然に定義できる．

3‑2 領域木構成アルゴリズム
先にで述べたように，領域木を構成するためには，その曲面の最も値の高いところから少しずつ値を低くしながら，その切り口に現れる等高線の形状変化を調べ，それに応じて
領域木のリンクを付け足したり，リンクを枝分かれさせたりしていけばよい．したがって，
これをメッシュデータに応用するには，まず，メッシュをそれが持つ値が大きい順にソーティングし，次に，その順番に各メッシュが領域木のどのリンクに属するかラベルを付け，等高線を変化させながら，値が最小のメッシュまで繰り返してやればよい．この大まかな考え方自体は，van Kreveld et al. (1997) において紹介されているものだが，そこではアルゴリズムが明示されている訳ではない．そこで，この論文では，長方形メッシュデー
タの場合において，領域木構成のアルゴリズムを明示的にする．
さて，ある一つのメッシュの局所的性質の判定は，図 6 のように行われる．大まかに言うと，メッシュをを囲む 4 辺につけられているラベルの種類数，隣接メッシュとの関係によって判定するのだが，詳しくは，記号を用いて以下のように記述される．
今，分析対象としているメッシュデータのサイズは m × n とし，左から数えて i 番目，上

CSIS Discussion Paper Series #32

から数えて j 番目のメッシュを (i, j ) とする．このメッシュ (i, j ) が持つ値は z (i, j ) とする．
また，あるメッシュ (i, j ) に x というラベルが与えられているとき， l (i, j ) = x と書くことにする．ここで， x は自然数としても，一般性を失わない．なお，メッシュにラベルがまだ与えられていない場合には， l (i, j ) = 0 と書くことにする．さらに，このメッシュを囲
む辺については，図 6 にあるように，左から順番に1, 2,... と番号を付けていくこととすると，この番号の最大値は m( 2n + 1) + n であり， (i, j ) を囲む 4 辺に付けられる番号は，上から反時計回りに， (i − 1)( 2n + 1) + n + j , (i − 1)( 2n + 1) + j , (i − 1)( 2n + 1) + n + j + 1 ,i (2n + 1) + j となる．番号 i の辺に x というラベルが付けられているときには，C (i ) = x と書くことにする．ここで，ある命題 P があるものとし，以下のような関数 T (P) を定義する．

1 ( Pが真)T ( P) = 
0 ( Pが偽)(7)

さらに， s (i, j ) , t (i, j ) , u (i, j ) をそれぞれ

s (i , j ) =T (C ((i − 1)(2n + 1) + n + j ) ≠ 0) + T (C ((i − 1)(2n + 1) + j ) ≠ 0)
+ T (C ((i − 1)(2n + 1) + n + j ) ≠ 0) + T (C (i (2n + 1) + j ) ≠ 0)

(8)

t ( i, j ) =C ((i − 1)(2n + 1) + n + j ) + C ((i − 1)(2n + 1) + j ) + C ((i − 1)(2n + 1) + n + j ) + C (i (2n + 1) + j )(9)u ( i, j ) =T (C ((i − 1)(2n + 1) + n + j ) = t (i, j ) / s (i, j ) or C ((i − 1)(2n + 1) + n + j ) = 0)
+ T (C ((i − 1)(2n + 1) + j ) = t (i, j ) / s (i, j ) or C ((i − 1)(2n + 1) + j ) = 0)
+ T (C ((i − 1)(2n + 1) + n + j ) = t (i, j ) / s (i, j ) or C ((i − 1)(2n + 1) + n + j ) = 0)
+ T ((C (i(2n + 1) + j ) = t (i, j ) / s (i, j ) or (C (i (2n + 1) + j ) = 0)(10)

とおく（ただし， s (i, j ) = 0 のときは u (i, j ) を定義しない）．
さて，以上の準備を終えると任意のメッシュの局所的性質の判定法は次のようになる．
もし， s (i, j ) = 0 であれば， (i, j ) はピークである． s (i, j ) > 0 かつ u (i, j ) = 0 の場合，スCSIS Discussion Paper Series #32

ロープかコルである．もし， l (i, j ) = t (i, j ) / s (i, j ) とすることによっても，図 7(b)のように「穴」が生じないのであれば，スロープであり，逆に，図 7(c)のように「穴」が生じる
場合はコルである． s (i, j ) > 0 かつ u (i, j ) > 0 の場合はコルである．
さて，ソーティングと前述のメッシュの局所的性質判定法を組み合わせると，領域木を構成するアルゴリズムは以下のようになる．

Step 0. 1 ≤ i ≤ m を満たす i と 1 ≤ j ≤ n を満たす j の組み合わせに対して， l (i, j ) = 0 とし，1 ≤ i ≤ m(2n + 1) + n を満たす i に対して C (i ) = 0 とする．また，ラベル用の
変数 label （ label の初期値は 1 とする）を用意する．
Step 1.

z (i, j ) を降順にソートし，一番大きな値をとる (i, j ) を初期値にする．

Step 2. メッシュ (i, j ) に関して， s (i, j ) , t (i, j ) を求める．
Step 3.

もし， s (i, j ) = 0 であれば， l (i, j ) = label とし， (i, j ) を囲む 4 つの辺に label
を 与 え る （ C ((i − 1)(2n + 1) + n + j ) = label , C ((i − 1)(2n + 1) + j ) = label ,C ((i − 1)(2n + 1) + n + j + 1) = label , C (i (2n + 1) + j ) = label とする）．領域木
については，上端の性質がピークで， label というラベルを持ったリンクを一本追加する（なおリンクの下端の性質は，差し当たってボトムとしておく）．labelを一つ大きくして Step 7 へ．
Step 4.

u (i, j ) を求め， u (i, j ) > 0 ならば， (i, j ) を囲む 4 辺の中でラベルのついているものをすべて探し出す．このラベルの集合を l1 , l 2 ,... とする（要素数は最大で 4）．

l ( x, y ) = l k （ k = 1,2,... ）を満たす全てのメッシュに対し， l ( x, y ) = label とする．また， C (i ) = l k （ k = 1,2,... ）を満たす全ての辺に対し， C (i ) = label とする．また， l (i, j ) = label とし， (i, j ) を囲む 4 つの辺も label を与える．領域木
については， l1 , l 2 ,... というラベルを持つすべてのリンクの下端の性質をコルとし，また，これら下端は共通のノードであるとする．さらに，上端がコルであり，label というラベルを持ったリンク（ここでも，下端の性質はボトムとしておく）
を一本追加する． label を一つ大きくして Step 7 へ．
Step 5. とりあえず l (i, j ) = t (i, j ) / s (i, j ) とする． l ( x, y ) = t (i, j ) / s (i, j ) を満たすメッシ
ュ群からなる領域が「穴」を持っているかどうかを調べる．
「穴」がある場合には，Step 6 へ．もし，「穴」がなければ， (i, j ) を囲む 4 辺にも t (i, j ) / s (i, j ) というラベルを与える．なお，領域木に関しては，t (i, j ) / s (i, j ) というラベルのリ
ンクの上端，下端の性質に，特に，変更を加える必要はない．Step 7 へ．
Step 6.

図 8 にあるように， l ( x, y ) = t (i, j ) / s (i, j ) を満たすメッシュ群からなる領域の

CSIS Discussion Paper Series #32

内側の境界と外側に異なる二つのラベルをつける．このとき用いるラベルは，

label と label + 1 とすればよい．また，領域木においては，label , label + 1 という二本のリンクを追加し，この上端の性質をコルとする．label を二つ大きくし，Step 7 へ．
Step 7.

z (i, j ) の次に値の低いメッシュを探す．これが存在する場合には，このメッシ
ュを新たに (i, j ) として Step 2 へ．もし，存在しない場合には終了．

3‑3 アルゴリズム適用例
このアルゴリズムの適用例を見てみよう．今，図 9(a)にあるように，4×4 のメッシュがあり，各メッシュには，その中に書かれている数字が値として与えられているものとする．
このとき，先のアルゴリズムにしたがって，値が大きい順に領域木を構成していくプロセ
スは図 9(b)のようになり，その結果として，図 9(c)のような特異点と図 9(d)のような領域木が得られる．
なお，ここで述べたアルゴリズムは長方形メッシュデータに対するものであるが，上の記述からも分かるように，一つのメッシュが 4 つの辺で囲まれるものからなるとし，あたかも，ベクトルデータのように扱っている．したがって，これを部分的に変更することで，TIN データを始めとするあらゆる形式のデータに適用可能である．
また，このアルゴリズムを実行させた結果からは，領域木におけるリンクとリンクの接続関係，リンクの上端，下端の性質が与えられるに過ぎない．しかし，Step 3 ‑ Step 6
において，領域木に変更を加える際に， z (i, j ) も領域木のノードに蓄えるようにすることで，後でみるように，ピーク，ボトムの顕著さを測ることも可能となり，さらに，それにより，曲面の骨格的構造のみを抽出できる．

4 領域木における骨格的構造の抽出
上のアルゴリズムにしたがって，作成される領域木においては，どのような微少なピー
ク，ボトムも残される．しかしながら，曲面の骨格的な構造を考える際に重要なのは，顕著なピークやボトムであり，微少なものは削除した方がよい．例えば，図 10 にあるような曲面が与えられているとしよう．この曲面において，ピーク A やピーク C は顕著なピークであるが，ピーク B は微少である．そして，ピーク B を削除してやることで，ピーク A と
ピーク C からなる曲面の主要な構造が抽出されるだろう．そこで，ここでは，ピーク（ボトム）の顕著さというものを定義し，次に，顕著なピーク（ボトム）だけを残すような微少なピーク（ボトム）の削除法（スムージング）を示す．

CSIS Discussion Paper Series #32

今，ある曲面に関し，ピークの集合を P1 , P2 ,.... ，コルの集合を C1 , C 2 ,.... ，ボトムの集合を B1 , B2 ,... とする．あるピーク Pi に関し，それが領域木において接続しているコルを

C j とするとき，ピーク Pi の高さ h( Pi ) をh( Pi ) = f ( Pi ) − f (C j )(11)

なる式で定義することはごく自然なことだろう．この定義より，ピークの相対的高さは，領域木においてピークを表すノードからすぐ下のノードに降りることによって容易に求められる．また，ピーク高さは上の式で定義されたが，同様にして，ボトムの相対的深さも定義され，これも，領域木から容易に求められる．
このようにして，ピークの相対的高さ，ボトムの相対的深さが定義できたので，ある閾
値 h * を導入することで，ピーク（ボトム）が顕著か微少かを判定することができる．つまり， h( Pi ) ≥ h * ならば，顕著なピークとみなし，逆に h( Pi ) < h * ならば，微少なピークとみなすのである．
次に，先の図 10 におけるピーク B を例にとって微少ピークの削除法を示そう．この場合，
まず，2 点 B,D を結ぶリンクを削除する．次に，ピーク C を上端に持つリンクの下端のコ
ルを E に変更する．
一般には，以下のようになる．ピーク Pi が領域木において接続しているコルを C j とする．コル C j が上端となるリンクの下端（コルかボトムである）を X とする．このとき，
まず上端に Pi ,下端に C j を持つリンクを削除し，下端が C j であるすべてのリンクに関し，その下端を X に変更する．
さて，このピーク削除法によって，顕著なピークのみが残されることを示そう．このス
ムージングによって，下端が書き換えられたリンクの上端（ピークかコルである）を

W1 ,W2 ,... とする．このとき， f ( X ) < f (C j ) より，すべての k に対して，
f (Wk ) − f ( X ) > f (Wk ) − f (C j )(12)が成り立つ．これより，ピーク Pi を削除することで， Pi 以外のピークの相対的高さは変化
しないか，あるいは，大きくなるかどちらかである．したがって，微少なピークの削除を繰り返していくことで顕著なピークのみが残されることになる．
以上がピークの削除であったが，ボトムの削除も同様にして行われ，また，微少なボト

CSIS Discussion Paper Series #32

ムのみを削除することで，顕著なボトムのみが残されることも同様である．

5 おわりにこの論文では，まず，曲面をある領域上に定義される連続的な関数と考え，この領域のあらゆる連続的な変換に対して不変な曲面の構造的な特徴を記述する手法として領域木と呼ばれる手法を導入した．次に，離散的なデータから，その領域木を構築するにはどのようにすればよいか考え，その一連の手続きをアルゴリズム化し，仮想的なデータに適用した．最後に，こうして求められる領域木を用いて曲面の微少な特徴は捨象し，骨格的な構造だけを抽出する方法を示した．
今後の課題としては，ここで単一曲面に関する構造分析だけでなく，複数曲面の構造比較を行う手法を提案すること，および，そうした手法を実際の空間データに適用して，その有効性を検証することが挙げられるが，それについては，稿を改めて述べることにしたい．

[参考文献]
赤松 隆 (1968) 数値計算, コロナ社
浅野

哲夫 (1999) 画像処理と計算幾何学−Visual Computing 計算幾何学は画像処理に如何に貢献できるか, 数理科学, 433, 34‑40
Berry, J.K. (1999) GIS Represents Spatial Patterns and Relationships, Geo World,
Apr‑99, 24‑25
Etzelmuller, B. (2000) On the Quantification of Surface Changes using Grid‑based
Dgital Elevation Models (DEMs), Transactions in GIS, 4(2), 129‑143
Goodchild, M.F. (1992) Geographical information science, International Journal of
Geographical Information Systems, 6(1), 31‑45
Hagett, P. and Bassett, K.A. (1970) The use of trend‑surface parameters in inter‑urban
comparisons, Environment and Planning, 2(2), 225‑237,
Jacquez, G.M. (1995) The map comparison problem: tests for the overlap of geographic
boundaries, Statistics in Medicine, 14, 2343‑2361
Okabe, A. (1981) A Qualitative Method of Trend Surface Analysis, Discussion Paper
No. 3. Department of Urban Engineering, University of Tokyo
Okabe, A. and Masuda, S. (1984) Qualitative Analysis of Two‑dimensional Urban

CSIS Discussion Paper Series #32

Population Distributions in Japan, Geographical Analysis, 16(4), 301‑312
Pfaltz, J.L. (1976) Surface Networks, Geographical Analysis, 8(1), 77‑93
Silverman, B.W. (1986) Density Estimation, Chapman and Hall, London
van Kreveld, M., van Oostrum Rene, Bajaj, C., Pascucci, V. and Schikore, D. (1997)
Contour Trees and Small Seed Sets for Isosurface Traversal, Computational Geometry
97 Nice France, 212‑219
Warntz, W. (1966) The Topology of a Socio‑Economic Terrain and Spatial Flows, Papers,
Regional Science Association, 17, 47‑61

peakbottom

col

図1

slope

D

peak
bottom
col

図2

(a)

(b)

図3

A
D

E

C
B

(a)

A
B

C

D

E
F
(b)

図4

F
(外周．一種のボトムとみなす）

h+ε

(x,y)

(x,y)

(x,y)
(x,y)

h‑ε

(x,y)

(x,y)

(x,y)
(x,y)

h+ε
or
h‑ε

peak

bottom

(a)

(b)

col
(c)

図5

slope

(d)

n+1
1 n+2
2 n+3
3 n+4
4

n+5
5 ・
・
・ ・
・
・

図6

4辺のうち，1種類のラベルが存在する．これと同じラベルを付けても，「穴」は生じない

4辺ともまだラベルが付けられていない

peak
slope
(a)

(b)

穴

4辺のうち，1種類のラベルが存在する．また，これと同じラベルを付けると，「穴」が生じる．

col

4辺のうちに2種類（以上）のラベルが存在する．

col
(c)

(d)
図7

内側の境界（label）

外側の境界（label+1）

図8

15

14

5

4

16

7

8

3

13

12

9

2

6

10 11 1(a) データ

peak

15

14

5

4

15

14

5

4

15

14

5

4

16

7

8

3

16

7

8

3

16

7

8

3

13

12

9

2

13

12

9

2

13

12

9

2

6

10 11 16

10 11 16

10 11 1

t=1

t=4

t=7

col

15

14

5

4

15

14

5

4

15

14

5

4

16

7

8

3

16

7

8

3

16

7

8

3

13

12

9

2

13

12

9

2

13

12

9

2

6

10 11 16

10 11 16

10 11 1

t=2

t=5

t=8
col

15

14

5

4

15

14

5

4

15

14

5

4

16

7

8

3

16

7

8

3

16

7

8

3

13

12

9

2

13

12

9

2

13

12

9

2

6

10 11 16

10 11 16

10 11 1t=3

t=6

t=10からは省略

t=9

peak

(b) 領域木の構成プロセス

16.000bottom

2
A

3

12

A

col

B

13

D

1

10

4

5

11

7

peak

E

C

col

9

14

8

15

6

B

11.00016
peak

C 10.000

D 8.000

FbottomE
1.000(c) 特異点
図9

F

7.000
(d) 領域木

切断方向(a)等高線

ピークC

ピークA
ピークB
コルD
コルE

(b) 切断方向で曲面を垂直に切ったときに見える断面

C

C
A

A
B

D

E

E

スムージング前の領域木

スムージング後の領域木(c) 領域木とそのスムージング

図10