2

光線間の2Dで最も近い交差点を見つけるにはどうすればよいですか？

x = x0 + t*cos(a), y = y0 + t*sin(a)

およびmポリライン：

{(x1,y1), (x2,y2), ..., (xn,yn)}

早く？

まず、すべての線分と各線分をループすることから始めました。 {(x1,y1),(x2,y2)}解決：

x1 + u*(x2-x1) = x0 + t*cos(a)

y1 + u*(y2-y1) = y0 + t*sin(a)

クラメルの法則により、その後、交差点を距離で並べ替えましたが、それは遅かったです:-(

ところで：ポリラインはたまたまで単調に増加していxます。

4

2 に答える 2

2

座標系の変換

まず、セットアップをより簡単な座標の何かに変換することをお勧めします。

  1. あなたのポイントを取るp = (x, y)。
  2. (-x0, -y0)光線が中央から始まるように移動します。
  3. -a光線がx軸上にくるように回転させます。

これまでのところ、上記の操作では、ポイントごとに4つの加算と4つの乗算が必要です。

ca = cos(a) # computed only once
sa = sin(a) # likewise

x' = x - x0
y' = y - y0
x'' = x'*ca + y'*sa 
y'' = y'*ca - x'*sa

交差点の確認

y''これで、ポリラインのセグメントは、その値の符号が変更された場合にのみ光線と交差することがわかりますy1'' * y2'' < 0。x''このチェックが完了するまで、値の計算を延期することもできます。さらに、セグメントとx軸との交差がx > 0で発生する場合にのみ、セグメントは光線と交差します。これは、いずれかの値がゼロより大きい場合にのみ発生する可能性がありますx1'' > 0 or x2'' > 0。両方x''がゼロより大きい場合は、交差点があることがわかります。

次の段落は一種のオプションです。理解していなくても心配しないでください。後で説明する代替案があります。
一方x''が正でもう一方が負の場合は、さらに確認する必要があります。y''の符号が負から正に変わったと仮定しy1'' < 0 < y2''ます。からの線は、三角形がによって形成され、原点が反時計回りに向けられている場合にのみ、x >0でx軸と交差しp1''ます。行列式の符号を調べることにより、その三角形の方向を決定できますp2''p1''p2''x1''*y2'' - x2''*y1''、反時計回りの三角形の場合は正になります。符号の変更の方向が異なる場合は、方向も異なる必要があります。したがって、これをまとめるために、次のことを確認できます。

(x1'' * y2'' - x2'' * y1'') * y2'' > 0

その場合は、交差点があります。これまでのところ、費用のかかる部門は含まれていなかったことに注意してください。

交差点の計算

交差点が存在するかどうかを判断するだけでなく、実際に特定の交差点を見つけたいので、次にその交差点を計算する必要があります。それを呼びましょうp3。それは方程式を満たさなければなりません

(x2'' - x3'')/(y2'' - y3'') = (x1'' - x3'')/(y1'' - y3'') and 
                       y3'' = 0

その結果、

x3'' = (x1'' * y1'' - x2'' * y2'')/(y1'' - y2'')

前の段落の三角形の向きのチェックの代わりに、いつでもこのx3''値を計算して、負であることが判明した結果を破棄することができます。コードは少なくなりますが、分割は多くなります。パフォーマンスに疑問がある場合はベンチマーク。

光線の原点に最も近いポイントを見つけるには、最小x3''値で結果を取得し、それを元の位置に戻すことができます。

x3 = x3''*ca + x0
y3 = x3''*sa + y0

あります。

上記のすべては、すべての数値が正または負のいずれかであると想定していることに注意してください。ゼロがある場合は、実際に計算したいものの正確な解釈、これらの境界ケースをどのように処理したいかによって異なります。

于 2012-10-05T15:57:58.537 に答える
1

すべてのセグメントとの交差をチェックしないようにするには、 Quadtree、BSP treeなどのスペース パーティションが必要です。スペース パーティションでは、スペース パーティションとの光線の交差をチェックする必要があります。

この場合、ポイントは x 座標でソートされる(min x, min y)-(max x, max y)ため、ポリラインの一部をボックスで空間分割することができます。ルート ボックスはすべてのポイントの最小-最大であり、ポリラインの最初と 2 番目の部分の 2 つのボックスに分割されます。パーツ内のセグメントの数が同じか、1 つのボックスにセグメントが 1 つ多くあります。このボックス分割は、1 つのセグメントのみがボックス内に収まるまで再帰的に行われます。

レイの交差をチェックするには、ルート ボックスから開始し、それがレイと交差しているかどうかをチェックします。交差している場合は、2 つのサブボックスで交差をチェックし、最初に近くのサブボックスをテストし、次に遠くのサブボックスをテストします。

レイボックスの交差をチェックすることは、レイが2つの位置の間で軸に沿った線と交差しているかどうかをチェックしています。これは、4 つのボックス境界に対して行われます。

于 2012-10-05T15:26:28.937 に答える