並行性和共線射線性/段相交測試失敗BCZ浮動精度在python

我想實現一個功能，找到射線性/段交叉口蟒蛇以下加雷思·雷斯偉大的說明： https://stackoverflow.com/a/14318254/7235455和https://stackoverflow.com/a/565282/7235455 並行性和共線射線性/段相交測試失敗BCZ浮動精度在python

這裏是我的功能：

from math import radians, sin, cos 
import numpy as np 

def find_intersection(point0, theta, point1, point2): 
    # convert arguments to arrays: 
    p = np.array(point0, dtype=np.float) # ray origin 
    q = np.array(point1, dtype=np.float) # segment point 1 
    q2 = np.array(point2, dtype=np.float) # segment point 2 
    r = np.array((cos(theta),sin(theta))) # theta as vector (= ray as vector) 

    s = q2 - q # vector from point1 to point2 
    rxs = np.cross(r,s) 
    qpxs = np.cross(q-p,s) 
    qpxr = np.cross(q-p,r) 
    t = qpxs/rxs 
    u = qpxr/rxs 

    if rxs == 0 and qpxr == 0: 
     t0 = np.dot(q-p,r)/np.dot(r,r) 
     t1 = np.dot(t0+s,r)/np.dot(r,r) 
     return "collinear" 
    elif rxs == 0 and qpxr != 0: 
     return "parallel" 
    elif rxs != 0 and 0 <= t and 0 <= u and u <= 1: # removed t <= 1 since ray is inifinte 
     intersection = p+t*r 
     return "intersection is {0}".format(intersection) 
    else: 
     return None

功能正常工作時，有一個交集。但它不能識別並行性或共線性，因爲條件rxs == 0和qpxr == 0不符合（曾經？）。例如：

p0 = (0.0,0.0) 
theta = radians(45.0) 
p1 = (1.0,1.0) 
p2 = (3.0,3.0) 

c = find_intersection(p0,theta,p1,p2)

它返回無。如果 - 塊之前增加對RXS和qpxr打印語句給

rxs = 2.22044604925e-16 qpxr = -1.11022302463e-16

我的結論是，該功能未能趕上第一if語句，因爲浮點問題的條件。 2.22044604925e-16和-1.11022302463e-16是非常小的，但不幸的是不完全是0.我明白浮點數不能在二進制中有精確的表示。

我的結論是否正確或我錯過了什麼？有沒有什麼想法可以避免這個問題？非常感謝！

來源

2017-09-04 Thodor

是的，你的結論是對的，問題在於「並行」謂詞的數值穩定性。

您可以將結果與小號碼進行比較（例如，eps=1.0E-9）。它的大小可能取決於座標範圍（注意交叉乘積給出加倍的三角形區域，因此通過MaxVecLen**2正常化eps看起來合理）。

更復雜但更精確的選項 - 使用穩健的幾何謂詞，如these ones。用於計算幾何的Python/NumPy庫可能包含這些操作的一些實現。

來源

2017-09-04 10:41:47 MBo

花了我一段時間去挖掘它。您的想法與小數字和正常化進行比較似乎是最實際的。缺點是，它提供了一些虛假的並行/共線，但我想我可以忍受這一點。 – Thodor

有一個簡單而安全的方法來解決這個問題。

寫出射線的隱式方程（）。當您在函數S中插入段的端點座標時，會得到兩個值，分別爲S0和S1。如果它們的符號相反，則光線的支撐線與該部分之間存在交叉。

在這種情況下，沿着該段的交叉點的位置，由參數的值，它等於

- S0/(S1 - S0).

該表達式享有始終是可計算的（提供的屬性給出有的變化標誌）和範圍[0, 1]。它允許安全地計算交點。

要僅選擇那些在所需半線（射線）上的交點，只需計算光線原點的S(Xo, Yo)的符號。

此過程不會檢測平行或非共線射線，但它並不重要。無論如何，它會產生合理的結果。

來源

2017-09-04 21:41:11

並行性和共線射線性/段相交測試失敗BCZ浮動精度在python

回答

相關問題