并行性和共线射线性/段相交测试失败BCZ浮动精度在python
我想实现一个功能,找到射线性/段交叉口蟒蛇以下加雷思·雷斯伟大的说明: https://*.com/a/14318254/7235455和https://*.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.我明白浮点数不能在二进制中有精确的表示。
我的结论是否正确或我错过了什么?有没有什么想法可以避免这个问题? 非常感谢!
是的,你的结论是对的,问题在于“并行”谓词的数值稳定性。
您可以将结果与小号码进行比较(例如,eps=1.0E-9
)。它的大小可能取决于坐标范围(注意交叉乘积给出加倍的三角形区域,因此通过MaxVecLen**2
正常化eps
看起来合理)。
更复杂但更精确的选项 - 使用稳健的几何谓词,如these ones。用于计算几何的Python/NumPy库可能包含这些操作的一些实现。
有一个简单而安全的方法来解决这个问题。
写出射线的隐式方程()。当您在函数S
中插入段的端点坐标时,会得到两个值,分别为S0
和S1
。如果它们的符号相反,则光线的支撑线与该部分之间存在交叉。
在这种情况下,沿着该段的交叉点的位置,由参数的值,它等于
- S0/(S1 - S0).
该表达式享有始终是可计算的(提供的属性给出有的变化标志)和范围[0, 1]
。它允许安全地计算交点。
要仅选择那些在所需半线(射线)上的交点,只需计算光线原点的S(Xo, Yo)
的符号。
此过程不会检测平行或非共线射线,但它并不重要。无论如何,它会产生合理的结果。
花了我一段时间去挖掘它。您的想法与小数字和正常化进行比较似乎是最实际的。缺点是,它提供了一些虚假的并行/共线,但我想我可以忍受这一点。 – Thodor