(1) 在二维空间中,三点坐标表示为:A(xa,ya), B(xb,yb), P(xp,yp)。
AB确定的直线方程(点斜式)为:
y = k * (x - xa) + ya
P点若位于直线上,首先应该满足直线的方程:
yp = k * (xp - xa) + ya。
若上式成立,说明A、B、P共线,接下来只需判断 P 位于 A 和 B 中间,即
(xa < xb && xa <= xp <= xb) || (xa > xb && xa >= xp >= xb)
(ya < yb && ya <= yp <= yb) || (ya > yb && ya >= yp >= yb)
同时成立。否则,P 不在线段AB上。
注意到直线方程中有除法运算,需做一步AB是否重合的判断,否则除数为零。上式稍作变形,便可去掉除法运算,即:
(y - ya) / (yb - ya) = (x - xa) / (xb - xa)
进而
(y - ya) * (xb - xa) - (yb - ya) * (x - xa) = 0。
上式成立的条件,(x,y)与A或B点重合,或者(x,y)、A、B三点共线。接下来再做 P 是否位于AB中间的判断即可。
A x B = xa*yb - ya*xb
由直线方程的启示,不难理解叉积为零,则可判定两向量共线或者一个向量为零。
变形后的直线方程和向量的叉积是二维空间向三维空间推广的基础。
(2) 在三维空间中,三点坐标分别为A(xa,ya,za), B(xb,yb,zb), P(xp,yp,zp)。
AB确定的直线方程相应变为:
(y - ya) / (yb - ya) = (x - xa) / (xb - xa) = (z - za) / (zb - za)。
按(1)中所述,将P点代入直线方程成立后,只需再多做一步 z 轴坐标的判断:
(za < zb && za <= zp <= zb) || (za > zb && za >= zp >= zb)。
所有条件同时成立,则 P 点位于线段 AB 上。
三维空间中的叉积判断就是接下来的方法2。
方法2:利用向量的叉积做判断[3]。
二维空间中的叉积定义已经介绍,三维空间的描述可以参考「4」,叉积可以作为判定两个向量是否共线的一个工具,三维空间中的叉积结果会得到一个新的向量。
先求得两个向量:v1 = B - A, v2 = P - A。然后 v1 和 v2 做叉积:v = v1 x v2,如果 v 是零向量,即 v 的x、y、z分量都为 0,则v1 和 v2 至少有一个为零或者两个向量共线。
参考:
[1]http://stackoverflow.com/questions/328107/how-can-you-determine-a-point-is-between-two-other-points-on-a-line-segment
[2]http://stackoverflow.com/questions/7050186/find-if-point-lay-on-line-segment
function SameSide(p1,p2, a,b)cp1 = CrossProduct(b-a, p1-a)cp2 = CrossProduct(b-a, p2-a)if DotProduct(cp1, cp2) >= 0 then return trueelse return falsefunction PointInTriangle(p, a,b,c)if SameSide(p,a, b,c) and SameSide(p,b, a,c) and SameSide(p,c, a,b) thenreturn trueelsereturn false
(v0・v1)(v0・v1) / ((v0・v0)(v1・v1))
= |v0|^2 * |v1|^2 * (cos<v0,v1> )^2 / (|v0|^2 * |v1|^2)
= (cos<v0,v1>)^2
= 1