質問

2次元の連続データの視覚化プロジェクトに取り組んでいます。これは、2Dマップで標高データまたは温度パターンを調査するために使用できる種類のものです。本質的には、3次元を2次元プラスカラーに平坦化する方法です。私の特定の研究分野では、実際に地理的標高データを扱っているわけではありませんが、それは良いメタファーですので、この投稿を通してそれを守ります。

とにかく、この時点で、「連続色」があります。私が非常に満足しているレンダラー：

連続カラーレンダラー

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

基礎となるデータ構造は、非常に巧妙な（私がそう言うなら）補間アルゴリズムを使用して、マップの詳細を任意に深くズームできるようにします。

この時点で、（二次ベジェ曲線を使用して）いくつかの地形等高線を描きたいが、それらの曲線を見つけるための効率的なアルゴリズムを説明する優れた文献を見つけることができなかった。

私が考えていることのアイデアを提供するために、貧しい人の実装があります（等高線と交差するピクセルに遭遇するたびにレンダラーは単に黒いRGB値を使用します）：

Ghetto Topoラインの連続色

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

  • 勾配が急なグラフの領域では、トポラインが細くなります（そしてしばしば破損します）。理想的には、すべての地形線が連続している必要があります。

  • より平坦な勾配のグラフの領域は、より広いトポライン（および多くの場合、特にレンダリング領域の外周で黒さの領域全体）になります。

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

  1. トポラインを描画する個々の標高で、その座標の標高が目的の標高に非常に近い（任意のイプシロン値が与えられている）座標セットを見つけます。

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

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

  4. 各頂点について、手順2で削除された冗長ポイントに関して、結果の曲線が最小のエラーを示すように、一対の制御ポイントを見つけます。

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

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

  • レンダリング境界ボックス内のハイポイントを見つけます。その高い地点から、いくつかの異なる軌道に沿って下り坂を進みます。トラバースラインが標高しきい値を超えるたびに、そのポイントを標高に追加します。特定のバケット。横断経路がローカルミニマムに達したら、コースを変更して上り坂を走行します。

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

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

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

実装を深く掘り下げる前に、StackOverflowの他の誰かがこの種の問題を経験し、正確かつ効率的な実装へのポインタを提供できるかどうかを確認したかったのです。

編集：

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

3次元の勾配を表すデータ構造と、任意の点での勾配ベクトルを計算する関数が必要だと思います。私の頭上では、それを行う方法がわかりません（簡単なはずですが）数学を説明するリンクがあれば、私は大いに義務づけられます！

更新：

ellisbbenとAzimの優れた貢献のおかげで、フィールド内の任意のポイントの輪郭角を計算できるようになりました。本物の地形線を描くことはまもなく続きます！

これは、私が使用しているゲットーラスターベースのトポレンダラーの有無にかかわらず、更新されたレンダリングです。各画像には、赤い点で表される千のランダムなサンプルポイントが含まれています。そのポイントでの輪郭角は白い線で表されます。特定のケースでは、（補間の粒度に基づいて）所定のポイントで勾配を測定できないため、対応する輪郭角線なしで赤い点が発生します。

お楽しみください

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

alt text

alt text

おもしろい事実があります。これらのレンダリングの右側に、完璧な水平および垂直角度で奇妙な輪郭線がたくさん見えます。これらは補間プロセスのアーティファクトであり、補間プロセスのグリッドを使用して、コアレンダリング操作の実行に必要な計算数を（約500％）削減します。これらの奇妙な等高線はすべて、2つの補間グリッドセルの境界にあります。

幸いなことに、これらのアーティファクトは実際には問題ではありません。アーティファクトはスロープ計算中に検出可能ですが、最終レンダラーは異なるビット深度で動作するため、それらに気付きません。

再度更新：

Aaaaaaa、そして私が寝る前の最後のasとして、もう1組のレンダリングがあります。1つは旧式の「連続色」です。スタイル、および20,000の勾配サンプルを含むスタイル。この一連のレンダリングでは、不必要にポイントサンプルの赤い点を削除しました。

役に立ちましたか？

解決

勾配は、あなたを助ける数学演算子です。

補間を微分可能な関数に変えることができる場合、高さの勾配は常に最も急な上昇の方向を指します。高さが等しい曲線はすべて、そのポイントで評価された高さの勾配に垂直です。

最高点から開始するという考えは賢明ですが、複数のローカル最大値がある場合は機能が失われる可能性があります。

提案します

  1. 線を引く高さの値を選択
  2. 規則正しく配置された細かいグリッド上に一連のポイントを作成し、線を描画する最も近い高さに向かって勾配方向に各ステップを少しずつ歩きます
  3. 勾配に垂直な各ポイントをステップすることにより曲線を作成します。別の曲線が近すぎるときにポイントを殺すことで余分なポイントを排除します。しかし、砂時計のような数字の中心が破壊されないようにするには、両方のポイントの勾配に垂直な方向ベクトル間の角度を確認する必要があります。 （指向と言うとき、勾配と計算する垂直値との間の角度が常に同じ方向で90度になるようにします。）

他のヒント

代わりに、マーチングスクエアアルゴリズムがあります。粗いグリッドを使用する場合、結果を滑らかにすることができます。

描画する地形曲線は、2次元のスカラーフィールドの isosurfaces です。 3次元の等値面には、マーチングキューブアルゴリズムがあります。

@ericksonへのコメントに応えて、関数の勾配の計算に関するポイントに答えます。 300項関数の導関数を計算する代わりに、次のように数値微分を行うことができます。

画像内の点[x、y]を指定すると、勾配（最も急な方向）を計算できます

g={  ( f(x+dx,y)-f(x-dx,y) )/(2*dx), 
  {  ( f(x,y+dy)-f(x,y-dy) )/(2*dy)

dxとdyは、グリッド内の間隔です。等高線はグラデーションに垂直になります。したがって、等高線の方向cを取得するには、g = [v、w]と行列A = [0 -1、1 0]を乗算して

を与えることができます。 
c = [-w,v]

自分でこのようなものが欲しかったのですが、ベクターベースのソリューションが見つかりませんでした。

ただし、特にデータがラスターベースの場合、ラスターベースのソリューションはそれほど悪くはありません。データもベクトルベースの場合（つまり、サーフェスの3Dモデルがある場合）、実際の数学を実行して、さまざまな標高で水平面との交差曲線を見つけることができるはずです。

ラスターベースのアプローチでは、隣接するピクセルの各ペアを調べます。 1つが等高線レベルより上で、1つが下にある場合、明らかに等高線がそれらの間にあります。輪郭線のアンチエイリアスに使用したコツは、理想的な輪郭線に近いことに比例して、輪郭線の色を both ピクセルに混ぜることです。

おそらくいくつかの例が役立つでしょう。現在のピクセルが「高度」にあると仮定します。 12フィートの場合、隣人は8フィートの高度にあり、等高線は10フィートごとです。次に、中間に等高線があります。 50％の不透明度で等高線の色で現在のピクセルをペイントします。別のピクセルは11フィートにあり、6フィートに隣接しています。 80％の不透明度で現在のピクセルに色を付けます。 

alpha = (contour - neighbor) / (current - neighbor)

残念なことに、私はコードを手元に持っていないので、もう少しあったかもしれません（対角線上の隣人を見て、 sqrt（2）/ 2 で調整したことを漠然と思い出します）。これで要点を説明できればと思います。

contour関数を使用すると、MATLABでやろうとしていることが非常に簡単になることがわかりました。輪郭の低密度近似を行うなどのことは、おそらく輪郭のかなり簡単な後処理で行うことができます。

幸いなことに、MATLABクローンであるGNU Octaveには、さまざまな等高線プロット関数が実装されています。数学的にはほぼ確実なアルゴリズムと実装のコードを見ることができます。または、処理をOctaveにオフロードできる場合があります。 他の言語とのインターフェースのページをチェックして、それが簡単かどうかを確認してください。

開示：Octaveをあまり使用しておらず、実際に等高線プロットをテストしていません。ただし、MATLABでの私の経験から、データをMATLABに取得すれば、ほんの数行のコードで、求めているほぼすべてのものが得られると言えます。

また、非常にVanGough風の傾斜場プロットを作成できたことをお祝いします。

私は自分で深く行く前に、常に http://mathworld.wolfram.com のような場所をチェックします：）

曲線セクションが役立つでしょうか？または、マップのエントリかもしれません。

実際の地形図でレンダリングしたものと比較してください-それらは私と同じように見えます！私は何かを変えないだろう...

データを HGTファイル（非常に簡単なUSGSで使用されるデジタル標高データ形式）および無料のオープンソース gdal_contour ツールを使用して作成します輪郭。これは、地上のマップでは非常にうまく機能します。制約は、データポイントが16ビットの数字に署名されていることです。これはメートル単位の地上の高さ範囲に非常によく適合しますが、データには十分ではない可能性があります。実際の地形の地図-地形地図については言及していますが。

CONREC のアプローチをお勧めします：

  • 空のラインセグメントリストを作成
  • データを通常のグリッドスクエアに分割する
  • 各グリッドの正方形について、正方形を4つのコンポーネントの三角形に分割します。
    • 各三角形について、ケース（aからj）を処理します。
      • 線分がケースのいずれかと交差する場合：
        • エンドポイントの計算
        • リストに線分を保存する
  • ラインセグメントリストに各ラインセグメントを描画

線がぎざぎざになっている場合は、小さいグリッドを使用します。ラインが十分に滑らかで、アルゴリズムに時間がかかりすぎる場合は、より大きなグリッドを使用します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top