Ray- /セグメント交差テストのpython

Question

にフロート精度のbczを失敗した私は、ガレス・リース偉大指示に従ってpythonでray- /セグメントの交差点を見つけるために、機能を実装しようとしています： https://stackoverflow.com/a/14318254/7235455とhttps://stackoverflow.com/a/565282/7235455

交差点がある場合

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ためのprint文を追加すると、私の結論です

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

は、関数があるため、浮動小数点の問題の最初のif文の条件をキャッチに失敗できます。 2.22044604925e-16と-1.11022302463e-16はかなり小さいですが、残念ながら正確に0ではありません。浮動小数点数はバイナリで正確な表現を持つことはできません。

私の結論は正しいですか、私は何かを逃しましたか？この問題を回避するための実装方法はありますか？ ありがとう！

Answer 1

はい、あなたの結論は正しいです、問題は "並列"述語の数値的安定性にあります。

結果を小さい数字（たとえば、eps=1.0E-9）と比較できます。その大きさは座標範囲に依存することがあります（クロスプロダクトは三角形の面積が2倍になるので、epsをMaxVecLen**2で正規化すると妥当です）。

より複雑でより正確なオプション - 堅牢な幾何学的述語（these onesなど）を使用する。おそらく計算幾何学のためのPython/NumPyライブラリには、そのような操作のためのいくつかの実装が含まれています。

Answer 2

この問題に対処する簡単で安全な方法があります。

光線の暗黙の方程式（​​）を書きます。セグメントの端点の座標を関数Sに差し込むと、S0とS1の2つの値が得られます。それらが反対の符号である場合、線の支持線とセグメントとの間に交差点が存在する。この場合

は、セグメントに沿った交差点の位置は、この式は常に計算可能であるという特性を享受

- S0/(S1 - S0). 

に等しいパラメータの値、によって与えられる（の変化が提供されます標識）、範囲は[0, 1]です。交差点を安全に計算することができます。

希望のハーフライン（光線）にある交差点のみを選択するには、光線の起点にあるS(Xo, Yo)の符号を計算するだけです。

この手順では、平行光線や共線光線は検出されませんが、問題はありません。いずれにせよ、それは健全な結果をもたらす。