如下图所示:
由三条线段连接起来的A,B,C三个点在2d平面中构成了一个三角形。
P点位于三角形外, q点位于三角形内，那么用什么方案来判定一个任意点是否位于三角形内部呢?
我们得找到一个规律:
假定你按照顺时针的方向从A点出发向B点前进再到C点继而在到A点，你会发现如果点在三角形内,则点一定位于你的右手，如果在三角形外的点，一定位于你的左手。
ok,规律找到了，就能用实际的算法来实现。从上面的规律可以看出，三角形的三个顶点是有序的，这种结构可以保证更快速的计算
,但是也可以不用有序的结构。下面给出的代码以无序顶点来计算包含关系的:
//
private var temp_0_v:Vector_2D = new Vector_2D(); private var temp_1_v:Vector_2D = new Vector_2D(); private var value_0:Number = 0; private var value_1:Number = 0; /* * 判定当前的三角形是否包含一个点 @param t 当前的任意三角形,有三个属性:t.pA_v,t.pB_v,t.pC_v,每一个属性就 表示一个顶点,而且都是Vector_2D对象 @param pos_v 需要计算的一个点的矢量表示 */ public function contains(t:Triangle, pos_v:Vector_2D):Boolean{ // 计算A->P矢量叉乘A->B矢量 temp_0_v.x = pos_v.x - t.pA_v.x; temp_0_v.y = pos_v.y - t.pA_v.y; temp_1_v.x = t.pB_v.x - t.pA_v.x; temp_1_v.y = t.pB_v.y - t.pA_v.y; value_0 = temp_0_v.cross( temp_1_v ); // 计算B->P矢量叉乘B->C矢量 temp_0_v.x = pos_v.x - t.pB_v.x; temp_0_v.y = pos_v.y - t.pB_v.y; temp_1_v.x = t.pC_v.x - t.pB_v.x; temp_1_v.y = t.pC_v.y - t.pB_v.y; value_1 = temp_0_v.cross( temp_1_v ); // if(value_0 * value_1 < 0){ return false; } // 计算C->P矢量叉乘C->A矢量 temp_0_v.x = pos_v.x - t.pC_v.x; temp_0_v.y = pos_v.y - t.pC_v.y; temp_1_v.x = t.pA_v.x - t.pC_v.x; temp_1_v.y = t.pA_v.y - t.pC_v.y; value_0 = temp_0_v.cross( temp_1_v ); return value_0 * value_1 >= 0; } //
这分代码是我as3 2d库的一个工具类的代码片段。
如果你要用的话,注意实现:Triangle类和Vector_2D类，请见()
通过上面讲的规律,我们就能推出三角形和线段，三角形和三角形相交等的快速实现算法。
由此也可以推出凸多边形相关的算法实现。
下面我们来聊聊三角形吧。
这里从三个角度来看三角形:
1. 三条线段连接起来的三个点在2d平面中构成了一个三角形
2.三角形可以看成是三对平行线的交集
3.三角形可以看做三个半平面的交集
后面，再来看看这三个角度带来的应用