检查点是否位于线段上

Question

我很困惑,我想检查一个点是否在一个线段上.我谷歌它,但我基本上收到两个不同的答案.

和

什么是正确的答案？我希望这个算法(用C语言更好)用于几何应用程序,比如postgis.

Answer 1

浮点运算不能存储您想要的每个数字.在某些时候,它必须近似.现在,我猜,你从维基百科得到的算法告诉你:

y=mx+b

你知道m,你知道b,现在插入并确保方程式成立.非常适合数学.(平方根2)的平方等于4的平方根.

但现在想象你在电脑上做到了.4的平方根将完全为2,因为计算机非常适合保存小整数.但是,你的右手边,2的平方根,将会有点偏离.你不得不切断它的一些数字,所以当你平方时,它可能是1.999998或类似的东西.为了适应这种情况,你需要检查一下y is approx. mx+b,所以:

tolerance = .01
x,y
rhs = m*x + b //right hand side
dif = abs(rhs - y)
if dif < tolerance //the point is approximately on the segment

然后你必须检查它的边界框(找到max x,y,min x,y)

当然,这些方法并不完美(http://xkcd.com/217/),但对于大多数实际应用来说,它们都足够真实.如果您真的需要确切的数字,我建议使用Wolfram Alpha(我听说有一些API或其他东西)或只是编写自己的确切数字库.