からポイントを選択するための最も効率的な方法は何ですか、例えば：ポイント「P」のセットで構成
路を有するパスの内側
私はランダムにポイントを置くのセットを持って、内側と外側の両方にある。だから、ランダムな点へのパス上のポイントに内のすべてのポイントを比較するために、「N」と呼ばれる
、おそらく指数関数的に複雑になります。何かのように O（n）= n^pもし私が間違っていないならそれはO（n）= n * p
だから私はあなたが最小限の領域で経路を細分することができると考えている完全に外側にあり、他方は完全に内側にある。図のように
緑のセットは、黒外とオレンジが再び数回
がこれを可能にし、より重要なのですが反復されるように、内部のだろうそれは効率的ですか？
ポイントポリゴンテストの文献を検討することを検討してください。
このように多くの点で、私は賢明で効率的な方法を模索しています。あなたがやろうとしているこの繰り返しよりもはるかに多くのこと。
いずれにしても、複雑さはO（np）でなくO（n^p）です。 – lhf
ありがとう、それはまさに私が探していたものでした。私は話題を読んで、興味深い研究対象と思われます。 –
確かに可能です。しかし、これらの領域を見つけるのがどれほど費用がかかり、また点を内部の&の外側に分割するのがどれほどコストがかかっているのか分かりませんが、その効率を評価する方法はありません。
サンプリングベースのアプローチが最善の策かもしれません。パーティクルフィルタではなく、同じ種類のアイデアです。シーケンシャルモンテカルロ法もまた調べるべきものです。彼らはあなたのマップを構築するために内部または外部である場合に
http://en.wikipedia.org/wiki/Particle_filter
http://en.wikipedia.org/wiki/Monte_Carlo_method
Essenteniallyは、ランダムな点のサンプリングとテストを取ります。十分なマップが得られるまで、サンプルメソッドを何度も繰り返します。効率と結果のバランスを取るために、サンプル数とリピート数を調整することができます。
同様の（空間的ではなく幾何学的な）アプローチは、先に凸包を使用して、外の点を除外することがあります。パス。
次に、パスを船体にないサブパス（「凹面」と呼ぶ）に再帰的に分解し、それらに同じ凸包法を適用します。すべての子が親によって定義された凸の境界から減算されるように、領域のツリー（それぞれが凸包の根で囲まれている）で終わるでしょう。
残念なことに、これだけでは効率的なクエリが保証されません（特定のノードの子ノードの深さまたは数に上限がないため、パスがなくても子境界が重複する可能性があるので注意してください）。 ..）。あなたはまだ何らかの形の加速構造が必要ですが、あなたの地域が凸面になっているので、はるかに簡単なはずです。
パスの元の表現は何ですか？暗黙の関数？パラメトリック？ビットマップ？ポリライン？答えはこれによって大きく変わる
私はポリゴンのようなポイントのセットとしてパスを持っていると言いました。一般的なアドバイスと、他のフォームを探す場所も高く評価されます。 –
+1ペイントプラクティス –