1

多数の凸型四角形 (指定された 4 つの x、y ポイント) を配列/リストに追加し、それらの四角形に対してポイントが境界内または境界上にあるかどうかをチェックする最も効率的/高速な方法を見つけようとしています。それらのクワッドの。

私は最初にレイ キャスティングを使用しようとしましたが、すべてのポリゴンが四角形になり、すべて凸面であることがわかっているため、少しやり過ぎだと思いました。

現在、各クワッドをエッジを共有する 2 つの三角形に分割し、その領域を使用して、ポイントがこれらの 2 つの三角形のそれぞれにあるかどうかを確認しています。

たとえば、三角形 ABC とテスト ポイント P です。}

チェックを実行するには 4 つの異なる三角形の面積を計算する必要があり、クワッドの最初の三角形が false を返す場合は、さらに 4 つの領域を取得する必要があるため、これは少し遅くなるようです。(浮動小数点エラーを補うために、チェックに少しのイプシロンを含めます)

ポイントを2つの三角形に分割するのではなく、クワッドに対してポイントを1回チェックする、さらに高速な方法があることを願っています。

ポリゴンを配列 [,] に入れることで、チェックの数を減らそうとしました。ポリゴンを追加するとき、x と y の最小値と最大値をチェックし、それらを使用して、同じポリゴンを適切な配列位置に配置します。使用可能なポリゴンに対してポイントをチェックするとき、リストの配列から適切なリストを取得します。

同様の質問を検索してきましたが、現在使用しているものは、ポイントが三角形にあるかどうかを判断する最速の方法であると思いますが、クワッドに対してテストするより良い方法があることを願っています常に凸。私が調べたすべてのポリゴン テストは、多くの辺を持つポリゴンや不規則な形状のポリゴンに対してテストしているようです。

かなり単純な問題である私の長々とした質問を読んでくれてありがとう。

4

2 に答える 2

1

各クワッドで、その各エッジの方程式を保存する余裕があれば、MBoの回答よりも少し時間を節約できます。

たとえば、クワッドの各エッジに内向きの法線ベクトルNがあり、定数d（エッジ上の頂点pの1つに対してNp）がある場合、Nx>の場合に限り、ポイントxはクワッドにあります。 =各エッジのd。つまり、エッジごとに2つの乗算、1つの加算、1つの比較が行われ、ポイントごとに最大4つのテストを実行する必要があります。この手法は、任意の凸多角形で機能します。

于 2012-09-28T13:18:40.063 に答える
1

最速の方法は次のとおりだと思います。

1: 外積記号を使用して、すべてのベクトル ペア (DirectedEdge-CheckedPoint) の相互方向を見つけます。4 つの符号がすべて同じ場合、ポイントは内側にあります

追加: すべてのエッジに対して

EV[i] = V[i+1] - V[i], where V[] - vertices in order
PV[i] = P - V[i]
Cross[i] = CrossProduct(EV[i], PV[i]) = EV[i].X * PV[i].Y - EV[i].Y * PV[i].X

Cross[i] の値は、点 P が i 番目のエッジ (V[i] - V[i+1]) に対して左側の半平面にある場合は正であり、それ以外の場合は負です。すべての Cross[] 値が正の場合、点 p はクワッドの内側にあり、頂点は反時計回りの順序になります。f すべての Cross[] 値が負の場合、点 p はクワッドの内側にあり、頂点は時計回りの順序です。値の符号が異なる場合、ポイントはクワッドの外側にあります。

クワッド セットが多くのポイント クエリで同じである場合、dmuirはすべてのエッジに対して一様な直線方程式を事前に計算することを提案します。一様直線の方程式は a * x + b * y + c = 0 です。(a, b) はエッジの法線ベクトルです。この方程式には重要な特性があります。式 (a * Px + b * Y + c) の符号は、点 P が存在する半平面を決定します (外積の場合と同様)。

2: 四角形を 2 つの三角形に分割し、それぞれにベクトル メソッドを使用します。CheckedPoint ベクトルを基底ベクトルで表します。

P = a*V1+b*V2

a,b>=0 で、それらの合計が <=1 の場合、点は内側にあります

どちらの方法でも、約 10 ～ 15 回の加算、6 ～ 10 回の乗算、および 2 ～ 7 回の比較が必要です (浮動小数点誤差の補正は考慮していません)。

于 2012-09-28T05:46:45.720 に答える