Ray-/세그먼트 교차 시험은 파이썬에서 부동 소수점 정밀도의 BCZ 실패

Question

내가 가레스리스 '좋은 지침에 따라 파이썬에서 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) 

아무 것도 없음을 반환합니다. 은 if 블록 전에 RXS 및 qpxr의 인쇄 문을 추가하면 내 결론은

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

이 기능 때문에 부동 소수점 문제의 첫 번째 경우 문의 조건을 잡으려고 실패 할 수 있습니다. 2.22044604925e-16과 -1.11022302463e-16은 꽤 작지만, 불행히도 정확하게 0은 아닙니다. 저는 float가 바이너리에서 정확한 표현을 가질 수 없다는 것을 알고 있습니다.

내 결론이 맞았습니까? 이 문제를 피하기위한 구현 아이디어가 있습니까? 감사합니다.

Answer 1

예, 결론은 맞습니다. 문제는 "병렬"조건부의 수치 안정성에 있습니다.

결과를 작은 숫자 (예 : eps=1.0E-9)와 비교할 수 있습니다. 그 크기는 좌표 범위에 따라 달라질 수 있습니다 (교차 제품은 두 배의 삼각형 영역을 제공하므로 eps을 MaxVecLen**2으로 정규화하는 것이 합리적 임).

더 복잡하지만 더 정확한 옵션 - 강력한 기하학적 조건어 인 these ones을 사용합니다. 아마도 계산 기하학을위한 Python/NumPy 라이브러리에는 그러한 연산을위한 몇 가지 구현이 포함되어있을 것입니다.

Answer 2

이 문제를 해결할 수있는 간단하고 안전한 방법이 있습니다.

광선의 암시 적 방정식 (S(X, Y) = a X + b Y + c = 0)을 씁니다. 세그먼트의 끝점 좌표를 S 함수에 연결하면 S0 및 S1이라는 두 값을 얻습니다. 그것들이 반대 기호라면 광선을 지탱하는 선과 선 사이에 교차가 있습니다. 이 경우

이 세그먼트를 따라 교차 위치가이 표현은 항상 제공 (계산할 수 있다는 특성을 즐긴다

- S0/(S1 - S0). 

동일 파라미터의 값으로 주어진다의 변화가 부호)와 범위 [0, 1]에서. 교차점을 안전하게 계산할 수 있습니다.

원하는 하프 라인 (광선)에있는 교차점 만 선택하려면 광선의 원점에서 S(Xo, Yo)의 부호 만 계산하면됩니다.

이 절차는 평행선이나 동일 선상의 광선을 감지하지는 않지만 중요하지 않습니다. 어쨌든 건전한 결과를 만들어냅니다.