5

世界地図上の国のように、境界線（等高線）によっていくつかの地域に分割された地図があります。各領域には、特定の表面カバークラスSがあります（たとえば、水は0、草は0.03 ...）。境界線は次のように定義されます。

  • Sのどの値がその両側にあるか（以下の例では、一方が0.03、もう一方が0.0）
  • 境界線がいくつのポイントで構成されているか（以下の例ではn = 7）、および
  • n個の座標ペア（x、y）。

これは一例です。

0.0300      0.0000           7
2660607.5   6332685.5   2660565.0   6332690.5   2660541.5   6332794.5 
2660621.7   6332860.5   2660673.8   6332770.5   2660669.0   6332709.5 
2660607.5   6332685.5

各ピクセルが、ピクセルの中心が位置する領域に対応するSの値を持つラスターマップを作成したいと思います。

境界線はSのステップ変化を表すことに注意してください。Sのさまざまな値は、離散クラス（たとえば、草や水）を表し、平均化できる値ではありません（つまり、濡れた草はありません！）。

また、上記の例のように、すべての境界線が閉ループであるとは限らないことにも注意してください。これは国境に少し似ています。たとえば、米国とカナダの国境は閉ループではなく、両端でカナダと海と米国と海の「国境」という2つの国境で結ばれている線です。（それでも、閉ループの境界線は存在します！）

誰かがこれを行うことができるアルゴリズムを私に指摘できますか？車輪の再発明はしたくない！

4

5 に答える 5

6

この種のジオメトリをベクトル形式で処理する一般的なケースは、特に、説明する構造についてジオメトリが一貫している必要がないため、非常に難しい場合があります。ただし、ラスタライズしたいだけなので、問題を線分のボロノイ図として扱うと、より堅牢になります。

ボロノイ図の近似は、OpenGLで、各線分を1対の四角形として描画してテントの形にすることにより、グラフィカルに行うことができます。zバッファは、最も近いクワッドを優先するために使用されます。したがって、最も近いラインに基づいてピクセルに色を付けます。ここでの違いは、ポリゴンが表す線ではなく、線のどちら側にあるかに基づいてポリゴンに色を付けることです。同様のアルゴリズムについて説明している優れた論文は、Hoffetalのグラフィックハードウェアを使用した一般化ボロノイ図の高速計算です。

3Dジオメトリは、3つの赤/黄色のセグメントと1つの青/緑のセグメントを持つ次のスケッチのようになります。

3Dジオメトリのスケッチ

この手順では、何も閉ループに変換する必要はなく、凝ったジオメトリライブラリも必要ありません。すべてがzバッファによって処理され、最新のグラフィックカードでリアルタイムに実行するのに十分な速度である必要があります。改良点は、同次座標を使用して、ベースを無限に投影することです。

このアルゴリズムは、 http：//www.pasteall.org/9062/pythonのPythonスクリプトに実装しました。興味深い注意点の1つは、セグメントの終点を表す円錐がZファイティングであったため、円錐を使用して線の端をキャップしても、円錐の形状を歪めることなく機能しなかったことです。提供したサンプルジオメトリの場合、出力は次のようになります。

ボロノイレンダリング出力

于 2009-11-09T04:13:24.363 に答える
1

CGALのようなジオメトリアルゴリズムライブラリを使用することをお勧めします。特に、リファレンスマニュアルの「2Dポリゴン」ページの2番目の例は、必要なものを提供するはずです。各「境界線」をポリゴンとして定義し、特定のポイントがポリゴンの内側にあるかどうかを確認できます。つまり、基本的には次のようになります

for every y in raster grid
  for every x in raster grid
    for each defined polygon p
      if point(x,y) is inside polygon p
        pixel[X][Y] = inside_color[p]

外側の領域が重なるので、outside_colorをどうするかよくわかりませんね。とにかく、あなたの例を見ると、すべての外側の地域は水である可能性があるので、あなたはただ決勝を行うことができます

    if pixel[X][Y] still undefined then pixel[X][Y] = water_value

（または、代わりに、ポリゴンリストを反復処理する前にpixel [X] [Y]をwater_valueに設定します）

于 2009-11-06T11:49:55.603 に答える
0
  • まず、すべての境界線を閉じたループ（マップのエッジを含む可能性があります）に変換し、内側の色を識別します。これは可能である必要があります。そうでない場合、データに不整合が生じます。
  • ブレゼンハムのアルゴリズムを使用して、マップ上のすべての境界線を単一の未使用の色で描画します
    • これを行うときに、すべての「境界ピクセル」のリストを保存します
  • その後、国境ごとに
    • それを三角測量する（delaunay）
    • 中心が境界線の内側にある三角形が見つかるまで、三角形を繰り返し処理します（ポリゴンのポイントテスト）。
    • その時点で、境界線の内部の色でマップを塗りつぶします
  • すべての内部領域を入力したら、境界ピクセルのリストを繰り返し処理して、それぞれの色を確認します。
于 2009-11-06T12:09:36.500 に答える
0
  • マーカー「空」と「境界線」として未使用の2色を選択します
  • すべての領域を「空の」色で塗りつぶします
  • すべての領域の境界線を「境界線」の色で描画します
  • ポイントを繰り返し処理して、「空の」色の最初のポイントを見つけます
  • それが属する領域を決定します（グーグル「ポリゴン内のポイント」、おそらくマーティン・デメロが提案したように境界を閉じる必要があります）
  • 領域の色を使用して、このポイントから塗りつぶしアルゴリズムを実行します
  • 次の「空の」ポイントに移動します（検索を再開する必要はありません-続行するだけです）
  • 「空の」ポイントがなくなるまで、以下同様です。
于 2009-11-06T14:10:43.547 に答える
0

私がこれを解決した方法は次のとおりです。

  1. 各セグメントに沿って行進します。一定の間隔Lで停止します。
  2. 各停車地で、トレーサーポイントをセグメントのすぐ左と右に配置します（セグメントから特定の小さな距離dに）。トレーサーポイントは、それぞれ左と右のS値に帰属します。
  3. 最近隣内挿法を実行します。ラスターグリッド上の各ポイントは、最も近いトレーサーポイントのSに関連付けられます。

これは、マップの端など、閉じていない線がある場合でも機能します。

これは「完璧な」分析アルゴリズムではありません。Lとdの2つのパラメータがあります。アルゴリズムは、 d << Lである限り美しく機能します。そうしないと、セグメントの接合部、特に鋭角の接合部の近くで不正確な値（通常は単一ピクセル）が発生する可能性があります。

于 2011-05-21T13:15:54.713 に答える