第35回日本情報地質学会講演会 講演要旨集 015-016頁 2024年

Z 階数曲線を利用した地図タイルセット作成の高速化
西岡芳晴

Accelerating map tileset creation using Z-rank curve
Yoshiharu NISHIOKA
国立研究開発法人 産業技術総合研究所 地質情報研究部門 Institute of Geology and Geoinformation, AIST,Tsukuba Central 7, 1-1, Higashi 1, Tsukuba Ibaraki, 305-8567, Japan. E-mail: y-nishioka@aist.go.jp

キーワード： キーワード Z 階数曲線，地図タイル，点群 PNG，JavaScript, ウェブ
Key words : Z-rank curve, map tile Point cloud PNG, JavaScript, Web

1．はじめに
近年，大量地図データの公開においてはタイル分割してサーバーに設置する手法が一般的になっている．また，地図データとして単純な画像ファイルではなく標高や点群を提供する方法も紹介されている（西岡，2021）．一方で地図デー
タの水平分解能が向上し，データ量が肥大化するにつれ，その効率的な作成方法の検討が必要になってきている．本論
では，従来の単純な生成方法に代えて，Z 階数曲線や四分木
深度優先帰りがけ探索を応用して高速化する手法を紹介す
る．

2．Z 階数曲線
Z 階数曲線とは，別名モートンオーダーとも呼ばれ，多次元のデータを一次元に写像する手法の一つであり（第 1図），解析学，計算機科学など様々な分野で利用されている．
アルゴリズムの詳細についてはここでは省略するが，深度 2の例（第 2 図）を参考にされたい．Z 階数曲線を使用するメリットの１つに，元の多次元空間における位置を 1 次元配列上から簡単に割り出すことができるという点があり，このことを利用して，二次元や三次元の空間検索に利用されている．地図分野での利用としては，等高線の高速生成に利用された例がある（谷，2015）．

3．ピラミッド化への適用
地図タイルセットの生成では，ベースとなる最大ズームレベル（ズームレベルは数値が大きいほど解像度が高いこ

第１図 Z 階数曲線の例
ウィキペディア「Z 階数曲線」（https://ja.wikipedia.org/wiki/Z 階数曲線）より．とを示す）のタイルセットをまず作成し，それをもとにより低ズームレベルのタイルを作る手法がしばしば用いられる．
これをここではピラミッド化と呼ぶことにする．ピラミッ
ド化ではあるズームレベルの 4 つのタイルから，ズームレベルが 1 小さい 1 つのタイルを作成する作業が基本となる．
ピラミッド化を行うアルゴリズムでもっと単純なものは，最大ズームレベルのタイルセットをすべてメモリー上にロードし，ズームレベルの大きいものから小さいものへ順番に生成するというものである．この方法は最も高速である
が，タイル数に依存した使用メモリー量として入力・出力のすべてのタイル分のメモリーを必要とし，タイル数が多い場合には利用できない．
次に考えられるアルゴリズムは，まずは最大ズームレベ
ルの４つのタイルから 1 つズームレベルの小さいタイルを作業を繰り返し，この作業をズームレベルを 1 減らしながら最後まで繰り返すというものである．この方法はタイル数に依存した使用メモリー量としては 5 タイル相当と最も少ないが，一度生成したタイルを再度ロードする工程が含まれるため処理が遅くなる．
これら 2 つの方法を改善するために，Z 階数曲線を導入する．まず，最大ズームレベルのタイルの処理順序を Z 階数曲線順とし，必要となる４つのタイルがロードされた時点で即座にタイル生成を開始，出力する．より低ズームレベルにもこれを導入し，ズームレベル毎ではなく，生成可能なタイルが発生しだい，即座にタイル生成，出力を行う．この手法により，不要なタイルのロードは行わないためより高速になり，イル数に依存した使用メモリー量としては（ズームレベル数＋4）タイル相当に抑えることができる．このアルゴリズムによるタイルの出力順序は四分木深度優先帰りがけ順探索に相当する．

第２図

深度 2 の Z 階数曲線の例

Haruoka(2024)より

164．実装
Z 階数曲線及び四分木深度優先帰りがけ探索を利用して，複数の LAS 形式ファイルから点群 PNG タイルセットを生
成 す る プ ロ グ ラ ム toPoints.js を 作 成 し た ． toPoints.js はJavaScript で実装され，Node.js 環境で動作させることができる．
主なパラーメータは以下の通り-i {入力ファイルのディレクトリパス}
デフォルトはカレントディレクトリ
指定したディレクトリ及びその子孫ディレクトリ内にある，拡張子が las であるすべてのファイルを対象とします．
-o {点群 PNG 出力ファイルパステンプレート}
デフォルトは 'points/{z}/{x}/{y}.png'-maxz {最大ズームレベル}
デフォルト 20-minz {最小ズームレベル}
デフォルト 0-asyncminz {非同期で生成する最小ズームレベル}
デフォルト maxz-1
指定したズームレベル以上のタイルは非同期的に生成し，それ以外は同期的に生成します．
この値を小さくすると高速化が期待できますが，メモリーエラーになる可能性も大きくなります．
-kei {平面直角座標の系番号}
デフォルト 'auto'
平面直角座標の系番号(1-19)または'auto'(自動判別)を指定します．
'auto'の場合は最初に検出した LAS ファイルのファイル名に含まれる数字から自動判別を試みます．
-mo {最大ズームレベルのウェブメルカトル次数}
デフォルト 32-ms {メッシュサイズ
デフォルト 512
最大ズームレベル以外のタイルの生成時に使用するメッシュサイズを指定します．
例えばデフォルトの 512 の場合，各タイルに含まれるポイント数は 512x512 以下となります．
静岡県(2022)が公開する点群データファイルでテストを行ったところ，LAS ファイル 100 個（15.6GB)を 115 分で変換することができた(Windows 10, メモリー 32GB)．

5．おわりにZ 階数曲線や四分木深度優先帰りがけ探索を応用して地図タイル作成を高速化する手法を示し，LAS 形式のファイルをソースとし点群 PNG タイルを出力するプログラムを紹介した．今後はこのプログラムを公開し，さらに GetTiff,テキスト形式等の入力ファイルや，標高タイルや画像タイルの出力に対応させる予定である．

文献

Haruoka (2024) モートンオーダー（モートンコード）とは？ 決定方法や仕組みを理解する．https://tecsingularity.com/algorithm/morton/(確認:2024/06/07)
西岡芳晴 (2021) ウェブアプリケーションで点群を高速に扱うための仕様“点群 PNG”の考案．情報地質, vol.32. no.2, pp.3942．
静岡県 (2022) VIRTUAL SHIZUOKA 静岡県 富士山および静岡東部
点群データ．https://www.geospatial.jp/ckan/dataset/shizuok
a-2021-pointcloud (確認:2024/06/07)
谷謙二 (2015) 標高タイルを利用した等高線作成 Web サイト「Web等高線メーカー」の開発とそのアルゴリズム．埼玉大学教育学部
地理学研究報告，35 号, pp.20-31.