3

（x、y）ポイントのセットがあり、それらのポイントから、このポイントのセットの「内部」にある任意のポイントの値を補間したいと思います。（下の写真の黄色い領域）。

例の画像

問題は、次のような良い方法が見つからないことです。

  1. 補間されたポイントの境界となるポリゴンを見つけます（緑色の線）
  2. ポイントがポリゴンの内側にあるかどうかをテストします。Point in Polygonアルゴリズムを見つけましたが、特定の範囲内のすべてのポイントを取得して、それらがポリゴンに属しているかどうかをテストするのが良い考えかどうかはわかりません。（max（x）-min（x））*（max（y）-min（y））よりも少ないポイント数をテストできる方法を見つけたいと思います。理想的には、どのポイントをテストするかを知る方法です。私の反復を行います。

編集：第2部では、画像内のすべてのポイント（ピクセル）を反復処理しています。実行したいのは、黄色のフィールドのポイントのみを反復処理することです。

リードはありますか？

追伸：何か助けがあれば、C++でコーディングしています。

4

1 に答える 1

8

あなたが見ている緑色の線は、点のセットの凸包と呼ばれ、それを計算するための多くの優れた効率的なアルゴリズムがあります。それらの最良のものは時間O（n log h）で実行されます。ここで、hは船体上で見つかったポイントの数であり、nはポイントの総数です。完全に恥知らずな自己宣伝として、私はこれらのアルゴリズムの1つのC++実装を個人のサイトで利用できます。

2番目の質問については、凸包ができたら、どの点が外皮ではなく、純粋にポリゴンの内側にあるかを簡単に判断できます。すべてのポイントのハッシュテーブルを作成してから、凸包を反復処理して、ハルに含まれるすべてのポイントを削除します。ハッシュテーブルに残っているのは、ポリゴン内に含まれているが境界上にはないポイントのセットです。

お役に立てれば！

于 2012-06-18T19:47:53.007 に答える