最短軌道を見つけるアルゴリズム

次に、参照点と局所領域内の各点との最短軌道長と平均法線変化を用いて、重み付き 最小２乗法に使う重みを決定するが、そのためには局所領域内で参照点から各点まで の全ての軌道の中から最短軌道を求める必要がある。このためには、重み付きグラフ のための最短パスの探索アルゴリズム（例えば、[108]）を利用することが できる。以下、そのアルゴリズムの詳細について述べる。

局所領域内の各点をグラフのノードとし、点の隣接関係をアークとし、点 $(x(t_i),y(t_i))$ と点 $(x(t_{i+1}),y(t_{i+1}))$ のアークの重みを

$$\sqrt{a_i^2 + b_i^2 + c_i^2}$$ (386)

とすると、参照点から領域内の全ての点までの最短軌道を求めるアルゴリズムは、 図8.12のようになる。

図 8.12: 最短軌道を求めるアルゴリズム

このアルゴリズムでは、まだ調べていないノードの集合のパス長に関する情報を更新 しながらから最小のパス長を持つノードを見つけ出すことを繰り返して最短パスを見 つける。そのためには、ノードの集合のパス長に関する情報を更新と最小のパス長を 持つノードの探索を頻繁に行う必要がある。ここでは、ヒープを用いてこれを効率よ く実現している。参照点からまだ調べていないノードまでの現時点での最小パス長を ヒープに蓄えると、参照点から最小パス長のノードを見つけるためには、単に、ヒー プの根の要素を取れば良い。その最小パス長を持つノードに継ったノードの最小パス 長に関する情報の更新には、階層的クラスタリングの高速化にヒープを用いたのと同 様の方法を用いれば良い。ヒープに蓄えられる要素数は、最大でグラフのノード数で あるから、必要な記憶容量は $O(\vert V\vert)$ である。ここで、 $\vert V\vert$ はグラフのノード 数である。一方、計算時間は $O((\vert E\vert+\vert V\vert)\mbox{log}\vert V\vert)$ となる。ここで、 $\vert E\vert$ はグラフのアーク数である。

以上のようなアルゴリズムを用いて最短軌道長が計算できるが、平均法線変化を計算 するためには各点での法線ベクトルを知る必要がある。各点での法線ベクトルの計算 は、例えば、$3 \times 3$ の局所領域内でレンジデータに平面を当てはめて推定す ることができる（例えば、[19]）。各点での法線ベクトルがわかれば、 平均法線変化を求めるためには、得られた最短軌道にそって法線ベクトルがどのよう に変化するかを調べればよい。