17

私はインターネットを見回していましたが、この特定の問題に最適なアルゴリズムを見つけることができませんでした:

この画像で示されているように、顧客は各ポイントとともに一連のポイントと重量データを持っています。

加重ポイント http://chakrit.net/files/stackoverflow/so_heightmap_points.png

そのうち、これらのポイントとその重み値から「高さマップ」または一種の地形データを生成できる GIS プログラムがありますが、1,000 ポイント近くのデータがあり、これらは時間の経過とともに変化するため、これらの高さマップを自動生成する独自のツールを作成します。

これまでのところ、最も近いデータ ポイントまでの距離から各ピクセルの重みを計算し、Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)重みと距離係数をデータ ポイントの色に適用して、その特定のピクセルのグラデーション カラーを生成しようとしました。

ハイトマップの結果 http://chakrit.net/files/stackoverflow/so_heightmap_result.png

データ ポイントの特定の構成にはまだ問題があり、多くのデータ ポイントがある場合、アルゴリズムによって多角形の画像が生成されることがあります。理想的な結果は、多角形ではなく、省略記号のように見えるはずです。

これは、私が望む結果を示す勾配上昇に関するウィキペディアの記事の画像の例です。

山 http://chakrit.net/files/stackoverflow/so_gradient_descent.png

勾配上昇アルゴリズムには興味がありません。私が興味を持っていること; 重み付きのデータポイントが提供された場合、最初にその画像の元の関数を計算するアルゴリズムです。

トポロジカル数学の授業は受けていませんが、微積分はできます。何かが足りないのではないかと思います。Google の検索ボックスに何を入力すればよいかわかりません。

いくつかの指針が必要です。

ありがとう！

4

9 に答える 9

4

非常に複雑な領域である、不規則なデータの 2 次元内挿のアルゴリズムに関する情報を求められました。あなたは ArcGIS を持っていると言うので、自動計算用の組み込み機能を使用して、ArcGIS で自動的に補間することを強くお勧めします。独自の補間アルゴリズムを作成するよりもはるかに簡単になると確信しています。私は ArcGIS の自動化をいくつか行いましたが、それはかなり簡単です。

独自の補間コードを作成する場合は (そうしないことをお勧めします)、最初に適切なアルゴリズムを選択します。それぞれに長所と短所があるためです。以下は、優れた補間ツールであるSurferのヘルプから抜粋したアドバイスです(このツールは非常に簡単に自動化することもできます)。他にもアルゴリズムがありますが、これらは私が試したものです。

  • クリギングはより柔軟な方法の 1 つであり、ほぼすべてのタイプのデータ セットのグリッド化に役立ちます。ほとんどのデータ セットでは、既定の線形バリオグラムを使用したクリギングが非常に効果的です。通常、この方法をお勧めします。クリギングは、ほとんどのデータ セットに対して適切なマップを生成するため、デフォルトのグリッド化方法です。大規模なデータ セットの場合、クリギングはかなり遅くなる可能性があります。クリギングは、データの Z 範囲を超えてグリッド値を推定できます。
  • 逆距離重み付けは高速ですが、データ ポイントの周囲に同心円状の「ブルズアイ」パターンを生成する傾向があります。Inverse Distance to a Power は、データの範囲を超えて Z 値を外挿しません。単純な逆距離加重アルゴリズムは実装が簡単ですが、遅くなります。
  • 線形補間による三角形分割は高速です。小さなデータ セットを使用する場合、線形補間を使用した三角形分割により、データ ポイント間に明確な三角形の面が生成されます。Linear Interpolation を使用した三角測量では、Z 値がデータの範囲を超えて外挿されることはありません。
  • シェパードの方法は、べき乗の逆距離に似ていますが、特に平滑化係数が使用されている場合、「ブルズアイ」パターンを生成する傾向はありません。シェパード法は、データの Z 範囲を超える値を推定できます。

アルゴリズムを実装するには、グーグルを試すか、他の回答のリンクをたどってください。補間を含むオープンソースの GIS パッケージがいくつかあるので、C++ を使って掘り下げるのが好きなら、それらからアルゴリズムを抽出できるかもしれません。あるいは、デビッド・ワトソンによるこの本は明らかに古典と見なされていますが、読みにくいし、サンプルコードはスパゲッティベーシックです!! しかし、私が聞いたところによると、それは利用可能な最高のものです。スタック オーバーフローの他の誰かがよく知っている場合は、私も信じられないので訂正してください。

于 2009-02-21T20:42:36.053 に答える
3

クリギングは、特に GIS の分野では、これを行うための重要な方法の 1 つです。これにはいくつかの優れた数学的特性があります。欠点は、バリオグラムによっては遅くなる可能性があることです。

もっと単純なものが必要な場合は、これをうまく処理する多くの補間ルーチンがあります。Numerical Recipesのコピーを手に入れることができれば、Chapter 3 は補間のための多くのバリアントを説明することに専念しており、コード例とそれらの機能特性の説明が含まれています。

于 2009-02-17T17:02:36.067 に答える
2

重み付きのデータポイントが提供された場合、最初にその画像の元の関数を計算するアルゴリズムです。

それが可能だ。単一のポイントから始めると、常に円になりますが、データポイントに重みを付けてそれを考慮に入れると、画像のように円を楕円形につぶすことができます..

ポリゴンになってしまうのは、計算で離散関数を使用しているためです。最初に最も近い色を見つけてから、色を決定します。

代わりに、ポイントを三角形で囲む 3 つのデータポイントからの距離と重みに基づいてポイントに色を割り当てるグラデーション アルゴリズムを調べる必要があります。

勾配アルゴリズム

何を表示しようとしているかによって異なります。単純化したアルゴリズムは次のようになります。

各ピクセルについて:

  • このピクセルを囲む最小の三角形を形成する 3 つの点を見つけます

  • このポイントを、各データポイントまでの重量と距離の両方の影響を受ける色 (HSV カラー システム) に設定します。

    pixel.color = datapoint[1].weight * distance(pixel, datapoint[1]) * datapoint[1].color + datapoint[2].weight * distance(pixel, datapoint[2]) * datapoint[2].color + datapoint[3].weight * distance(pixel, datapoint[3]) * datapoint[3].color

ここでは + を使用していますが、アプリケーションに適した「平均化」アルゴリズムを決定する必要があります。

-アダム

于 2009-02-17T16:13:24.920 に答える
1

これはかなり古い質問ですが、同様の問題を解決しようとしているときに偶然見つけました。

このタイプの機能を正確に実装するSurfitと呼ばれるオープンソースプロジェクトがあります。

于 2010-02-19T05:17:18.133 に答える
1

サーフェスの補間は、難しい数学的問題のようです。それを行う別の安価な方法は次のとおりです。

For each pixel:
For each point:
pixel.addWeight(weight(point, pixel))

def addWeight(w):
totalweight += w
numberofweights += 1
weight = totalweight / numberofweights

重み関数の例:

def weight(point, pixel):
return point.weight * 1/(1 + sqrt((point.x - pixel.x)^2 + (point.y - pixel.y)^2))

これはかなり強引なアプローチですが、単純です。

于 2009-02-17T16:46:57.680 に答える
1

少し前にWinamp AVSでこのようなものを実装しました。これは、「メタボール」タイプのアプローチを使用して、各データ ポイントから逆二乗距離を計算し (速度の sqrt を回避するため)、上限を設定し (たとえば、1.0 に)、2D グリッド上の各ポイントの距離の合計を取得します。これにより、滑らかに変化する色/高さのマップが得られます。

コードを見たい場合は、J10 AVS パックの「Glowy」プリセットにあります。

編集：見栄えを良くするために他のジャズを追加しました。最も重要な部分は次のとおりです。

d1=s/(sqr(px1-rx)+sqr(py1-ry));
d2=s/(sqr(px2-rx)+sqr(py2-ry));
d3=s/(sqr(px3-rx)+sqr(py3-ry));
d4=s/(sqr(px4-rx)+sqr(py4-ry));
d5=s/(sqr(px5-rx)+sqr(py5-ry));
d6=s/(sqr(px6-rx)+sqr(py6-ry));
d=d1+d2+d3+d4+d5+d6;

6ポイントの合計を取ります。赤、緑、青の出力値に対して行われる他のすべてのことは、見栄えを良くすることです。6 ポイントは多くありませんが、これを 400MHz マシンの 320x200 グリッドでリアルタイムで実行しようとしていたことを覚えておいてください。:)

red =、green =、blue = ... の行を red = d; に置き換えます。など...私が何を意味するかを確認します。すべての美しさがなくなり、データ ポイントの周りで滑らかに変化するブロブのグレースケール イメージが残ります。

別の編集:「s」はすべてのポイントの共有重みであると言うのを忘れていました。それぞれに変更すると、各ポイントに個別の重みが与えられます。たとえば、d1 = 2/(...) および d2 = 1/(.. .) d1 の中心の高さは d2 の 2 倍になります。d1 = 2/max(..., 1.0) のようなもので式の下部をキャップして、ポイントの上部を滑らかにし、中央の無限大でピークにならないようにすることもできます。:)

答えが乱雑で申し訳ありません...コード例を投稿するだけで十分だと思いましたが、調べてみると私のコードはわかりにくく、読みにくいです。:(

于 2009-05-25T10:05:49.793 に答える
0

Blenderが「メタボール」と呼ぶものを探しています(リンク付きのウィキペディアの記事、例)。次のように考えてください。

あなたのオブジェクトは、地面から突き出た円錐です。それらはすべて放物線であり、重さはそれらが地面からどれだけ突き出ているかを示します。または、それらをすべて同じ高さにし、それに応じて放物線の「平坦度」を調整します。重みが大きいとコーンが非常に広くなり、重みが小さいとシャープになります。たぶん両方ともある程度。

これを実装して、どのように見えるかを確認することをお勧めします。

次に、結果の上に布またはゴムシートを掛ける必要があります。布はある程度伸びますが、一般的には重力により垂れ下がります。コーンはそれを維持します。

円錐の中心に近い限り、Z 座標は円錐の表面上の位置になります。円錐の中心を離れると、重力が下がり始め、他の円錐の影響が大きくなります。

于 2009-02-17T16:34:22.310 に答える