5

3 つの点 (A、B、X) と距離 (d) があります。点 X が距離 d より線分 AB 上の任意の点に近いかどうかをテストする関数を作成する必要があります。

問題は、まず、私の解決策が正しいかどうか、そしてより良い (より速い) 解決策を考え出すことです。

私の最初のパスは次のとおりです

AX = X-A
BX = X-B
AB = A-B

    // closer than d to A (done squared to avoid needing to compute the sqrt in mag)
If d^2 > AX.mag^2  return true

    // closer than d to B
If d^2 > BX.mag^2 return true

    // "beyond"  B
If (dot(BX,AB) < 0) return false

    // "beyond"  A
If (dot(AX,AB) > 0) return false

    // find component of BX perpendicular to AB
Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2 < d^2

このコードは、少なくとも 1 つの A/B/d に合格するすべての P を見つけることを目的として、P の大規模なセットと A/B/d トリプレットの大規模なセットに対して実行されることになるため、方法があると思われます。それに基づいて全体的なコストを削減しますが、まだ調べていません。

（ところで：いくつかの並べ替え、いくつかの一時的な値、およびいくつかの代数恒等式が上記のコストを削減できることを認識しています。明確にするためにそれらを省略しました。）

編集: これは 2D の問題です (ただし、3D に一般化するソリューションはクールです

編集: さらに考えてみると、ヒット率は約 50% になると予想しています。X ポイントはネストされた階層で形成できるため、大きなサブツリーをすべてパスおよびすべて失敗としてプルーニングできると期待しています。トリプレットを制限する A/B/d は、より多くのトリックになります。

編集：dはABと同じ大きさのオーダーです。

編集: Artelius がすばらしい解決策を投稿しました。私が完全に理解する前に接線を外れてしまったので、彼が何をしようとしているのか正確に理解しているかどうかはわかりません. とにかく、結果として別の考えが頭に浮かびました：

  • 最初の Artelius のビットは、AB を原点の中心に配置し、X 軸に合わせて配置する行列を事前に計算します。(2回追加、4回追加、2回追加)
  • すべてを第 1 象限 (2 つの腹筋) に折りたたむ
  • ゾーンの中央部分を単位正方形 (2 mul) にするために X&Y でスケーリングします。
  • ポイントがその正方形にあるかどうかをテストする (2 テスト)
  • エンド キャップをテストします (スケーリングされていない値に戻ります
    • 端を原点に配置するために x に変換します (1 追加)
    • 2 乗して加算 (2 mul、1 加算)
    • d^2 (1 cmp) と比較

これが私のソリューションよりも優れていると確信しています。

（これ以上のものがなければ、アルテリウスが「賞」を獲得します:)

4

5 に答える 5

2

うーん、うーん……ヒット率は？ポイント「X」はどのくらいの頻度で近接要件を満たしますか？

既存のアルゴリズムは優れていると思います。追加の最適化は、実際のデータに合わせて調整することで実現します。たとえば、「X」ポイントが99％の確率で近接テストに合格した場合、最適化戦略は、1％の確率でテストに合格した場合とはかなり異なるはずだと思います。

ちなみに、このアルゴリズムを数千のポイントで実行しているポイントに到達したら、すべてのポイントをK次元ツリー（またはKDTree）に編成する必要があります。これにより、「最近傍」の計算がはるかに簡単になります。

あなたの問題は、基本的な最近傍よりも少し複雑です（ポイントへの近接だけでなく、ラインセグメントへの近接をチェックしているため）が、それでもKDTreeは便利だと思います。

于 2008-10-31T21:33:38.617 に答える
2

これを正しく読めば、これは 3D 光線追跡で使用される従来の光線/球体交差テストとほぼ同じです。

この場合、位置 X に半径 d の球があり、線 AB が球と交差するかどうかを調べようとしています。レイ トレーシングとの 1 つの違いは、この場合、特定のライン AB があることです。一方、レイ トレーシングでは、レイは通常 として一般化されorigin + distance * direction、無限ラインに沿ってどれだけ離れているかは気にしませんAB+。

私自身のレイ トレーサーからの疑似コード (「レイ トレーシングの紹介」(ed. Glassner) に記載されているアルゴリズムに基づく):

Vector v = X - A
Vector d = normalise(B - A)  // unit direction vector of AB
double b = dot(v, B - A)
double discrim = b^2 - dot(v, v) + d^2
if (discrim < 0)
     return false            // definitely no intersection

ここまでくれば、条件が満たされる可能性はいくらかあります。交点が AB 線上にあるかどうかを確認する必要があります。

discrim = sqrt(discrim)
double t2 = b + discrim
if (t2 <= 0)
    return false             // intersection is before A

double t1 = b  - discrim

result = (t1 < length(AB) || (t2 < length(AB))
于 2008-10-31T23:05:04.877 に答える
2

(A、B、d) のセットが固定されている場合、それぞれの行列のペアを計算して座標系を変換し、直線 AB が X 軸になり、AB の中点が原点になるようにすることができます。

これは行列を構築する簡単な方法だと思います：

trans = - ((A + B) / 2)        // translate midpoint of AB to origin

rot.col1 = AB / AB.mag         // unit vector in AB direction

                        0 -1    
rot.col2 = rot.col1 * (      ) // unit vector perp to AB
                        1  0 

rot = rot.inverse()            // but it needs to be done in reverse

次に、各 X を取り、 を実行しますrot * (X + trans)。

問題の領域は、x 軸と y 軸の両方で実際に対称になっているため、x 座標と y 座標の絶対値を取得できます。

次に、確認する必要があります。

y < d && x < AB.mag/2            //"along" the line segment
|| (x - AB.mag/2)^2 + y^2 < d^2  // the "end cap".

別のトリックを行うことができます。行列は の係数で縮小できAB.mag/2ます (行列は (A,B) ごとに 1 回だけ計算されることを思い出してください。つまり、実際のチェック自体よりも、それらを見つけるのが遅い方がよいということです)。これは、小切手が次のようになることを意味します。

y < 2*d/AB.mag && x < 1
|| (x - 1)^2 + y^2 < (2*d/AB.mag)^2

AB.mag/2 の 2 つのインスタンスを定数 1 に置き換えると、少し速くなる可能性があります。2*d/AB.magもちろん、事前に計算することもでき(2*d/AB.mag)^2ます。

これが他の方法よりも速く機能するかどうかは、与える入力によって異なります。でもABの長さがdに比べて長ければ、投稿した方法よりかなり早くなると思います。

于 2008-10-31T23:17:23.370 に答える
1

A/B/d のセットの数が多く、間違いなく 2D を使用している場合は、 Rツリーの各エントリが A/ B/D トリプル。これにより、多くの A/B/d トリプルをテストする必要がなくなり、各ポイント X が A/B/d トリプルのバウンディング ボックス内にあるいくつかのトリプルにのみ CPU パワーを集中させることができます。次に、あなたが言及したようなより詳細なテストを行います。

于 2008-12-10T15:14:39.793 に答える
1

このコードは、少なくとも 1 つの A/B/d に合格するすべての P を見つけることを目的として、P の大規模なセットと A/B/d トリプレットの大規模なセットに対して実行されることになるため、方法があると思われます。それに基づいて全体的なコストを削減しますが、まだ調べていません。

d ~ AB の場合、与えられた点 X に対して、X が半径 d で中心が Ai または Bi の多くの球体の 1 つに属しているかどうかを最初にテストできます。写真を見てください：

     ......        .....
  ...........   ...........
 ...........................
.......A-------------B.......
 ...........................
  ...........   ...........
     .....         .....

最初の 2 つのテスト

If d^2 > AX.mag^2 return true
If d^2 > BX.mag^2 return true

は最速のものであり、d ~ AB の場合、それらは成功する確率が最も高いものでもあります (テストがまったく成功した場合)。X を指定すると、最初にすべての「スフィア テスト」を実行し、次にすべての最終テストを実行できます。

戻る (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2
于 2008-10-31T22:18:54.063 に答える