問題タブ [topographical-lines]

私は、2 次元の連続データの視覚化プロジェクトに取り組んでいます。これは、2D マップで標高データや温度パターンを調べるために使用できるようなものです。本質的には、3 次元を 2 次元と色にフラット化する方法です。私の特定の研究分野では、実際に地理的な標高データを扱っているわけではありませんが、これは良い比喩であるため、この投稿全体を通してこれを使用します。

とにかく、この時点で、私は非常に満足している「連続カラー」レンダラーを持っています。

グラデーションは標準のカラー ホイールであり、赤いピクセルは高い値を持つ座標を示し、紫色のピクセルは低い値を示します。

基礎となるデータ構造は、いくつかの非常に巧妙な (私がそう言うなら) 補間アルゴリズムを使用して、マップの詳細への任意の深いズームを可能にします。

この時点で、(二次ベジエ曲線を使用して) いくつかの地形等高線を描画したいと考えていますが、これらの曲線を見つけるための効率的なアルゴリズムを説明している適切な文献を見つけることができませんでした。

私が考えていることのアイデアを提供するために、これは貧しい人の実装です (レンダラーは、輪郭線と交差するピクセルに遭遇するたびに黒の RGB 値を使用するだけです):

ただし、このアプローチにはいくつかの問題があります。

• 勾配が急なグラフの領域では、トポ ラインが細くなります (しばしば壊れます)。理想的には、すべてのトポ ラインが連続している必要があります。

• 勾配がより平坦なグラフの領域では、トポ ラインが広くなります (特にレンダリング領域の外周では、領域全体が黒くなることがよくあります)。

だから私は、それらの素晴らしい、完璧な 1 ピクセルの太さの曲線を得るためのベクトル描画アプローチを検討しています。アルゴリズムの基本構造には、次の手順を含める必要があります。

1. トポ ラインを描画する個別の標高ごとに、その座標の標高が目的の標高に非常に近い (任意のイプシロン値を指定) 座標のセットを見つけます。

2. 余分なポイントを削除します。たとえば、3 つの点が完全に直線上にある場合、曲線の形状を変更せずに中心点を削除できるため、中心点は冗長です。同様に、ベジェ曲線では、隣接するコントロール ポイントの位置を調整することで、特定のアンカー ポイントを削除できることがよくあります。

3. 2 つのポイント間の各セグメントが高度に中立な軌道に近似し、2 つのライン セグメントがパスを交差しないように、残りのポイントをシーケンスに組み立てます。各ポイント シーケンスは、閉じた多角形を作成するか、レンダリング領域の境界ボックスと交差する必要があります。

4. 各頂点について、ステップ 2 で削除された冗長点に関して、結果の曲線が最小の誤差を示すような制御点のペアを見つけます。

5. 現在のレンダリング スケールで表示される地形のすべてのフィーチャが適切な地形線で表されていることを確認します。たとえば、データに標高の高いスパイクが含まれているが、直径が非常に小さい場合でも、トポ ラインを描画する必要があります。垂直方向の特徴は、それらの特徴の直径が画像の全体的なレンダリングの粒度よりも小さい場合にのみ無視する必要があります。

しかし、これらの制約の下でも、行を見つけるためのいくつかの異なるヒューリスティックを考えることができます。

• レンダリング境界ボックス内の高点を見つけます。その高い地点から、いくつかの異なる軌道に沿って下り坂を進みます。トラバーサル ラインが標高のしきい値を超えるたびに、そのポイントを標高固有のバケットに追加します。トラバーサル パスが極小値に達したら、コースを変更して上り坂に移動します。

• レンダリング領域の長方形のバウンディング ボックスに沿って高解像度のトラバーサルを実行します。各標高のしきい値 (および勾配が方向を反転する変曲点) で、それらのポイントを標高固有のバケットに追加します。境界トラバーサルが終了したら、それらのバケットの境界点から内側にトレースを開始します。

• レンダリング領域全体をスキャンし、一定間隔で標高を測定します。測定ごとに、標高しきい値への近さをメカニズムとして使用して、その近傍の補間測定を行うかどうかを決定します。この手法を使用すると、レンダリング領域全体のカバレッジがより確実に保証されますが、結果のポイントをパスを構築するための適切な順序に組み立てるのは困難です。

だから、それらは私の考えの一部です...

実装を深く掘り下げる前に、StackOverflow の他の誰かがこの種の問題の経験があり、正確で効率的な実装への指針を提供できるかどうかを確認したかった.

編集：

ellisbben による "Gradient" の提案に特に興味があります。そして、私の核となるデータ構造 (最適化補間ショートカットの一部を無視して) は、完全に微分可能な一連の 2D ガウス関数の合計として表すことができます。

3 次元の勾配を表すデータ構造と、任意の点でその勾配ベクトルを計算する関数が必要になると思います。頭のてっぺんから、それを行う方法がわかりません（簡単なように思えますが）が、数学を説明するリンクがあれば、私は大いに感謝します!

アップデート：

ellisbben と Azim による優れた貢献のおかげで、フィールド内の任意の点の等高線角度を計算できるようになりました。実際のトポ ラインの描画はすぐに続きます。

これは、私が使用してきたゲットー ラスター ベースの topo-renderer を使用した場合と使用しない場合の、更新されたレンダリングです。各画像には、赤い点で表される 1000 のランダムなサンプル ポイントが含まれています。その点の等高線は白い線で表されます。場合によっては、（補間の粒度に基づいて）特定のポイントで勾配を測定できなかったため、対応する等高線なしで赤い点が発生します。

楽しみ！

(注: これらのレンダリングでは、以前のレンダリングとは異なる表面トポグラフィを使用しています。これは、プロトタイプを作成している間に、反復ごとにデータ構造をランダムに生成するためです。ただし、コアのレンダリング方法は同じであるため、アイデア。）

ここに興味深い事実があります。これらのレンダリングの右側に、完全な水平および垂直角度で奇妙な等高線がたくさん表示されます。これらは、補間プロセスのアーティファクトです。補間プロセスでは、補間子のグリッドを使用して、コアのレンダリング操作を実行するために必要な計算の数を (約 500%) 削減します。これらの奇妙な等高線はすべて、2 つの補間グリッド セル間の境界に発生します。

幸いなことに、これらのアーティファクトは実際には重要ではありません。アーティファクトは勾配の計算中に検出できますが、異なるビット深度で動作するため、最終的なレンダラーはそれらに気づきません。

再度更新:

そして、寝る前の最後の楽しみとして、もう 1 組のレンダリングを示します。1 つは昔ながらの「連続カラー」スタイルで、もう 1 つは 20,000 のグラデーション サンプルを使用しています。この一連のレンダリングでは、ポイント サンプルの赤い点を削除しました。これは、イメージが不必要に乱雑になるためです。

ここでは、補間コレクションのグリッド構造のおかげで、前に言及した補間アーティファクトを実際に見ることができます。これらのアーティファクトは、最終的なコンター レンダリングでは完全に見えなくなることを強調しておく必要があります (隣接する 2 つのインターポレーター セル間の大きさの差は、レンダリングされたイメージのビット深度よりも小さいため)。

ボナペティ!!

(x, y, 高度)データのかなりまばらなサンプルしかない地形の地形図を作成する必要があります。もちろん、完全に正確なマップを作成することはできませんが、ある意味で「滑らかな」マップが必要です。「滑らかさ」(おそらく表面曲率の二乗の平均の逆数) を定量化する必要があり、2 つの量の合計である目的関数を最小化したい:

• 表面の粗さ
• サンプル地点での表面の高度とその地点で実際に測定された高度との間の平均二乗距離

私が実際に欲しいのは地形図なので、一定の高度の等高線を作成する方法を本当に探しています。表面について話すことなくそれを行うための巧妙な幾何学的方法があるかもしれません。もちろん、輪郭線も滑らかにしたい。

あらゆる提案を歓迎します。これがよく知られた数値問題であることを願っています。私は C に慣れており、FORTRAN の実用的な知識を持っています。Matlab と R については、まったく無知です。

サンプルの配置場所については、ほぼ均等な間隔で計画していますが、地形がより興味深い場所でより多くのサンプルを取得します。たとえば、平野よりも山岳地帯をより密にサンプリングします。しかし、サンプリングに関していくつかの選択肢があることは間違いありません。唯一の問題は

• 探しているフィーチャを見つけるために、どのくらいの地形をマッピングする必要があるかはわかりません。

• サンプルの採取には、10 分程度の適度な費用がかかります。そのため、100x100 グリッドのサンプリングには時間がかかる場合があります。