快速幾何接近式謂詞

Question

我有3個點（A，B和X）和距離（d）。我需要做一個函數來測試點X比線段AB上的任何點的距離d更近。

問題是，首先，我的解決方案是否正確，然後提出更好（更快）的解決方案。

我第一遍是如下

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 

此代碼將最終成爲一個大的集合P的的和一大組的A/B/d三聯體與找到P的全部的是通的意圖運行對於至少一個A/B/D，所以我懷疑有一種方法可以降低總體成本，但我還沒有研究過。

（順便說一句：我知道一些重新排序，一些臨時的價值觀和一些代數恆等式可以降低上述成本我只是省略了對它們的清晰度。）

---

編輯：這是一個這可以推廣到3D 2D問題（但解決辦法是冷靜

編輯：在進一步的思考，我想到的命中率是50％左右，可在嵌套層次結構來形成X點，所以我希望能。把大的子樹修剪爲全通和全失敗，限制三元組的A/B/d將更多的是tr ICK。

編輯：d與AB的數量級相同。

---

編輯：Artelius發佈了一個不錯的解決方案。我不確定自己在完全理解它之前是否正確地理解了他正在切入的內容。反正另一個想法浮現在腦海的結果：

• 首先Artelius'位，預cacluate將放置AB爲中心的矩陣吃的起源和與X軸對齊。 （2增加了，4個MULS和2相加）
• 它摺疊所有入第一象限（2個絕對）
• 規模在X & y以使該區域的中央部分到一個單位區域（2 MUL）
• 測試如果點是在正方形（2試驗）被如此退出
• 測試端蓋（返回到未縮放的值
  • 平移x到末端放置在原點（1只添加）
  • 平方並加（2 mul，1加）
  • 比較d^2（1個CMP）

我相當肯定，這勝過我的解決方案。

（如果沒有更好的走來宋Artelius得到「獎賞」 :)

Answer 1

如果您的設置（A，B，d）在固定，你可以計算一對矩陣來翻譯座標系，所以t 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），這意味着它的更好，找到他們是慢，比實際檢查本身）縮減。這意味着你的支票就變成了：

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

已經取代AB.mag/2的兩個實例與常數1，這可能是一個觸摸更快。當然，你可以預先計算2*d/AB.mag和(2*d/AB.mag)^2爲好。

這是否會制定出比其他方法更快取決於你給它的輸入。但是如果AB的長度比d長，我認爲它會比你發佈的方法快得多。

Answer 2

Hmmmmmmm ....什麼是命中率是多少？點「X」多少次符合接近度要求？

我認爲你現有的算法是好的，任何額外的優化都將來自調整到真實的數據。例如，如果「X」點在99％的時間內符合接近測試，那麼我認爲您的優化策略應該與僅在1％時間內通過測試的情況相比有很大不同。

---

順便說一句，當你到那裏你有千點運行該算法的時候，你應該組織所有點到K維樹（或KDTree）。它使得「最近鄰居」的計算更加簡單。

你的問題比基本的最近鄰居要複雜一點（因爲你正在檢查鄰近線段而不是鄰近點），但我仍然認爲KDTree會方便。

Answer 3

這段代碼最終會運行一大堆P和一大組A/B/d三元組，以期找到至少有一個A/B/d通過的所有P，所以我懷疑有一種方法可以降低整體成本，但我還沒有研究過。

在d〜AB的情況下，對於給定點X，您可以首先測試X是否屬於半徑爲d的多個球體中的一個，並且中心爲Ai或Bi。看圖片：

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

前兩個測試

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

是最快的，如果D〜AB他們也是那些具有最高概率成功（因爲測試成功，在所有）。鑑於X，你可以做所有的「球體測試」第一，然後將所有最終的：

Return (BX.mag)^2 - (dot(AB,BX)/AB.mag)^2

Answer 4

如果我讀這正確的，那麼這是幾乎一樣的經典射線/球相交測試所用在3D光線追蹤中。

在這種情況下，您在半徑爲d的位置X處有一個球體，並且您試圖找出AB線是否與球體相交。與射線追蹤的區別在於，在這種情況下，您已經得到了一條特定的AB線，而在射線追蹤中，射線通常被廣義化爲origin + distance * direction，並且您不在乎沿無限線AB+多遠。

在從我自己的光線追蹤的僞代碼（基於「概論射線追蹤」（主編格拉斯納給出的算法）：

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 

如果你走了這麼遠， 。再有就是一些機會，你的條件滿足你一定要找出交點（S）是否在直線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)) 

Answer 5

如果A/B/d集合的數量很大，而且您肯定是2D的，請考慮使用R-trees（或其八角形等效項），其中R樹中的每個條目都是最小的邊界框A/B/d三聯。這將讓你消除了設計人員測試了很多A的/ B/d三元&集中你的CPU功率只有很少的人，每個點X是A的邊框/ B/d三倍之內。然後做一個更像你提到的那個更詳細的測試。