判断点是否在三角形内的算法-收集备用.doc

判断点是否在三角形内的算法-收集备用
1.
比如已知三个顶点 A(xa,za) B(xb,zb) C(xc,zc)判断点是否在三角形内的算法-收集备用
1.
比如已知三个顶点 A(xa,za) B(xb,zb) C(xc,zc)
以及O点(xo,zo)
判断O点在X-Z平面上是否在三角形ABC内
我想到不少方法，但在找最快最简洁的。
－－－－－
我用的是线性规划
判断
O,C是否在AB同侧
O,A是否在BC同侧
O,B是否在AC同侧
都成立就通过，速度还算快，不怎么影响帧数。
＝＝＝＝＝＝＝＝
2. 叉乘法判断点是否在三角形内


沿着三角形的边按顺时针方向走，判断该点是否在每条边的右边（这可以通过叉乘判断），如果该点在每条边的右边，则在三角形内，否则在三角形外。这个算法只用到了三次叉乘，没有除法运算和三角函数、开根号等运算，所以效率很高，而且精度很高（没有浮点误差）。 设三角形三点A(x1,y1)B(x2,y2)C(x3,y3)，已知点M(x,y), 1,先求出三个向量MA,MB,MC. 2,计算MA X MB,MB X MC,MC X MA (X表叉乘) 3,如果此三组的向量叉乘的结果都是同号的（或都正，或都负），即方向相同的，则说明点M在三角形每条边的同侧，即内部。否则必在外部！ 具体示例：
A(0,3) B(0,0) C(3,0) M(1,1)
MA (1,-2)
MB (1,1)
MC (-2,1) MA X MB = 3
MB X MC = 3
MC X MA = 3 N(3,3)
NA (3,0)
NB (3,3)
NC (0,3) NA X NB = 9
NB X NC = 9
NC X NA = -9 根据以上规则可判断M点在内 N点在外
＝＝＝＝＝＝＝＝＝＝＝＝＝
3.
设三角形三个点
A(a1,a2),B(