判断一个点在三角形内的算法

1.线性规划方法 判断：O,C是否在AB同侧 O,A是否在BC同侧 O,B是否在AC同侧 都成立就通过。

2.根据面积来计算 这个比较容易理解，如果一个点p在三角形内部或者边线上，那么p与三角形的其中两个顶点组成的三个三角形面积与原三角形面积应该相等，这时候问题就转化为如何计算三角形的面积了。 三角形面积=底*高/2 还可以用这个公式： s= (t0.x * t1.y + t1.x * t2.y + t2.x * t0.y - t1.x * t0.y - t2.x * t1.y - t0.x * t2.y)*0.5 //t0,t1,t2是三角形的三个顶点 function getArea(t0:Vector2D,t1:Vetor2D,t2:Vector2D):Number { var area:Number=(t0.x * t1.y + t1.x * t2.y + t2.x * t0.y - t1.x * t0.y - t2.x * t1.y - t0.x * t2.y)*0.5; area = area > 0 ? area : -area; return area; } function isPointInside(p:Vector2D):Boolean { var triangleArea:Number=getArea(t0,t1,t2); var area0:Number=getArea(p,t0,t1); var area1:Number=getArea(p,t0,t2); var area2:Number=getArea(p,t1,t2); var d:Number=triangleArea-area0-area1-area2; d= d>0 ? d : -d; if(d < 0.0001) return true; return false; }
3.先说一个关于矢量叉积的内容：矢量叉积：计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。 　　叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系： 　　若 P × Q > 0 , 则P在Q的顺时针方向。 　　若 P × Q < 0 , 则P在Q的逆时针方向。 　　若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。 上一篇我们所用的面积公式就来自于矢量叉积。
A(x1,y1) B(x2,y2) C(x3,y3) P(x0,y0)如图所示：我们要判断一个点P是否在三角形ABC内，我们只需要判断直线AP,BP,CP与对应的线段BC,AC,AB是否都相交，如果有任意一条不相交，则不在三角形内。现在剩下的事情就是如何判断直线与线段是否相交的问题了。以AP与BC相交为例：根据矢量叉积判断两矢量相互之间的顺逆时针关系，如果AP与BC相交，我们可以得出： ( BA × PA ) * ( CA × PA）<=0 //BA,PA,CA代表矢量,如BA= (x2-x1,y2-y1);//x0,y0是要判断的点，其它点是三角形的三个顶点//这里经过了一下优化，合并了几个相同的数function isOnSameSide(x0:Number,y0:Number,x1:Number,y1:Number, x2:Number,y2:Number,x3:Number,y3:Number):Boolean{ var a:Number; var b:Number; var c:Number; a = y0 - y1; b = x1 - x0; c = x0 * y1 - x1 * y0; if( (a * x2 + b * y2 + c) * (a * x3 + b * y3 + c) > 0) return true; return false;}//p是要检测的点,v0,v1,v2是三角形的三个顶点。function isPointInside2(p:Vector2D):Boolean{ if(isOnSameSide(p.x,p.y,v0.x,v0.y,v1.x,v1.y,v2.x,v2.y) isOnSameSide(p.x,p.y,v1.x,v1.y,v2.x,v2.y,v0.x,v0.y) isOnSameSide(p.x,p.y,v2.x,v2.y,v0.x,v0.y,v1.x,v1.y)) return false; return true;}这个方法要优于上一个方法。