并行性和共线射线性/段相交测试失败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

回答

相关问题