c - 检查点是否在线段上

Question

我很困惑，我想检查一个点是否位于线段上。我用谷歌搜索，但我基本上收到了两个不同的答案。

http://en.wikipedia.org/wiki/Line_segment

和

http://www.softwareandfinance.com/Turbo_C/Check_Point_Lies_line_Segment.html

正确答案是什么？我希望这个算法（用 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

然后你必须检查它的边界框（找到最大 x，y，最小 x，y）

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

Answer 2

Before proceeding it would be helpful to know if you just have a graphical representation of the line somehow or if you actually have the formula that created the line. Since you said "line" and not "plane" I presume we are talking about a 2D line.

If you have the formula for the line then the answer is simple, substitute the points x,y value into the formula and if the formula is valid then the point is on the line.

For example, if the line was y = 2x + 1.5 and your point is (1,1)

1 = 1(1) + 1.5 1 = 3.5 is false, so the point doesn't lie on the line

The same works for any line formula in 2D or 3D regardless of the number of variables or the form of the line..

x + 2y = 0 1.5x + 12y - 4z = 84

Just pop in the point you are working with and if both sides of the equation are equal then the point is on the line (or plane).

If you are looking for a graphical solution, such as having a bitmap of a road map or something like that and wanting to know if the place where someone clicked is "on the line of the road" then that's a completely different problem.

Answer 3

两者都是对的。

Only keep in mind that Turbo C is terribly old and now outside the standard. void main() for example should not be used (it is int main() instead)

Also don't use comparisons (==) in floating point in C, because floating point is imprecise, this is why the Turbo C code has < 0.001 %% > 0.001 style.