图形碰撞检测点与三角形

　　点与三角形的碰撞检测有很多方法，基本思想都是使用向量，利用向量之间的关系得出一些数据，然后利用这些数据进行判断。为了完成目的，我们先要建立基本的数据模型（代码使用的语言是ActionScrpit）：

　　1. 向量类：

  1 　　/**
  2      * 向量类，默认使用正交基
  3      */ 
  4     public class SHVector
  5     {
  6         public var x:Number;
  7         public var y:Number;
  8         public var z:Number;
  9         
 10         /**
 11          * 构造函数
 12          */ 
 13         public function SHVector(x:Number, y:Number, z:Number = 0)
 14         {
 15             this.x = x;
 16             this.y = y;
 17             this.z = z;
 18         }
 19         
 20         /**
 21          * 向量的模
 22          */
 23         public function model():Number
 24         {
 25             return Math.sqrt(this.x * this.x + this.y * this.y + this.z * this.z);
 26         }
 27         
 28         /**
 29          * 加法
 30          */ 
 31         public function add(vector:SHVector):SHVector
 32         {
 33             return new SHVector(
 34                 this.x + vector.x,
 35                 this.y + vector.y,
 36                 this.z + vector.z
 37             );
 38         }
 39         
 40         /**
 41          * 减法
 42          */ 
 43         public function sub(vector:SHVector, reverse:Boolean = false):SHVector
 44         {
 45             if (!reverse) {
 46                 return new SHVector(
 47                     this.x - vector.x,
 48                     this.y - vector.y,
 49                     this.z - vector.z
 50                 );
 51             }
 52             else {
 53                 return new SHVector(
 54                     vector.x - this.x,
 55                     vector.y - this.y,
 56                     vector.z - this.z
 57                 );
 58             }
 59         }
 60         
 61         /**
 62          * 点乘（内积）
 63          */
 64         public function dot(vector:SHVector):Number
 65         {
 66             return this.x * vector.x + this.y * vector.y + this.z * vector.z;
 67         }
 68         
 69         /**
 70          * 叉乘（外积）
 71          */ 
 72         public function cross(vector:SHVector):SHVector
 73         {
 74             var resultVector:SHVector = new SHVector(
 75                 this.y * vector.z - this.z * vector.y,
 76                 this.z * vector.x - this.x * vector.z,
 77                 this.x * vector.y - this.y * vector.x
 78             );
 79             
 80             return resultVector;
 81         }
 82         
 83         /**
 84          * 求两条向量的夹角，以弧度为单位
 85          */ 
 86         public function angle(vector:SHVector):Number
 87         {
 88             if (this.model() == 0 ||
 89                 vector.model() == 0)
 90                 return 0;
 91             
 92             return Math.acos(this.dot(vector) / (this.model() * vector.model()));
 93         }
 94         
 95         /**
 96          * 对象信息
 97          */ 
 98         public function toString():String
 99         {
100             return "x:" + this.x + "," +
101                    "y:" + this.y + "," +
102                    "z:" + this.z + "," +
103                    "model:" + this.model();
104         }
105     }

　　2. 坐标点类（只列出了我们需要的方法）：

 1 /**
 2      * 点
 3      */ 
 4     public class SHPoint extends RigidityObject
 5     {        
 6         public var vector:SHVector;
 7         
 8         /**
 9          * 构造函数
10          */ 
11         public function SHPoint(x:Number, y:Number)
12         {
13             super();
14             
15             this.x = x;
16             this.y = y;
17             this.vector = new SHVector(x, y);
18             
19             this.draw();
20         }37         
38         /**
39          * 更新
40          */ 
41         override public function update():void
42         {
43             this.x += this.speedX;
44             this.y += this.speedY;
45             
46             this.vector.x = this.x;
47             this.vector.y = this.y;
48         }
49         
50         /**
51          * 绘制
52          */ 
53         override protected function draw():void
54         {
55             this.graphics.clear();
56             this.graphics.lineStyle(0, 0);
57             this.graphics.drawRoundRect(
58                 0,
59                 0,
60                 2,
61                 2,
62                 0
63             );
64         }
65     }

　　3. 三角形类：

 1 /**
 2      * 三角形
 3      */ 
 4     public class SHTriangle extends RigidityObject
 5     {
 6         public var vx1:Number;
 7         public var vy1:Number;
 8         public var vx2:Number;
 9         public var vy2:Number;
10         public var vx3:Number;
11         public var vy3:Number;
12         
13         public var vector1:SHVector;
14         public var vector2:SHVector;
15         public var vector3:SHVector;
16         
17         /**
18          * 构造函数
19          */ 
20         public function SHTriangle(vx1:Number, vy1:Number, vx2:Number, vy2:Number, vx3:Number, vy3:Number)
21         {
22             super();
23             
24             this.vx1 = vx1;
25             this.vy1 = vy1;
26             this.vx2 = vx2;
27             this.vy2 = vy2;
28             this.vx3 = vx3;
29             this.vy3 = vy3;
30             
31             this.vector1 = new SHVector(vx1, vy1);
32             this.vector2 = new SHVector(vx2, vy2);
33             this.vector3 = new SHVector(vx3, vy3);
34             
35             this.draw();
36         }53         
54         /**
55          * 更新
56          */ 
57         override public function update():void
58         {
59             this.x += this.speedX;
60             this.y += this.speedY;
61             
62             this.vector1.x = this.x + this.vx1;
63             this.vector1.y = this.y + this.vy1;
64             this.vector2.x = this.x + this.vx2;
65             this.vector2.y = this.y + this.vy2;
66             this.vector3.x = this.x + this.vx3;
67             this.vector3.y = this.y + this.vy3;
68         }
69         
70         /**
71          * 绘制
72          */ 
73         override protected function draw():void
74         {
75             this.graphics.clear();
76             this.graphics.lineStyle(1, 0x000000);
77             this.graphics.moveTo(this.vx1, this.vy1);
78             this.graphics.lineTo(this.vx2, this.vy2);
79             this.graphics.lineTo(this.vx3, this.vy3);
80             this.graphics.lineTo(this.vx1, this.vy1);
81         }
82     }

　　建立好数据模型后，就可以开始判断了。假如我们在一个二维坐标系中有一个坐标点P，和一个由三个顶点A,B,C组成的三角形。下面归纳了5种判断的方法：

　　1. 利用三角形内角和为180度的概念。在同一平面内，向量AP和AC，以及AP和AB形成的两个夹角，那么以此内推，向量BP和BA，BP和BC，CP和CA，CP和DB一共就会形成4个夹角。如果坐标点P在三角形内部，那么这6个夹角之和就正好为180度，反而言之，如果内角和大于180度，就可以判断坐标点在三角形外部。求两条向量之间夹角的方式利用了向量的点乘公式。为了便于理解，我们使用角度来命名变量，实际上的值用的弧度作为单位。

 1 static public function detectPointAndTriangleCollision1(point:SHPoint, triangle:SHTriangle):Boolean
 2         {
 3             var vector1P:SHVector = point.vector.sub(triangle.vector1);
 4             var vector2P:SHVector = point.vector.sub(triangle.vector2);
 5             var vector3P:SHVector = point.vector.sub(triangle.vector3);
 6             
 7             // 如果P点正好在定点上
 8             if (vector1P.model() == 0 ||
 9                 vector2P.model() == 0 ||
10                 vector3P.model() == 0)
11                 return true;
12             
13             // 顶点1的情况
14             var vector12:SHVector = triangle.vector2.sub(triangle.vector1);
15             var vector13:SHVector = triangle.vector3.sub(triangle.vector1);
16             var angle21P:Number = Math.acos(vector12.dot(vector1P) / (vector12.model() * vector1P.model()));
17             var angle31P:Number = Math.acos(vector13.dot(vector1P) / (vector13.model() * vector1P.model()));
18             
19             // 顶点2的情况
20             var vector21:SHVector = triangle.vector1.sub(triangle.vector2);
21             var vector23:SHVector = triangle.vector3.sub(triangle.vector2);
22             var angle12P:Number = Math.acos(vector21.dot(vector2P) / (vector21.model() * vector2P.model()));
23             var angle32P:Number = Math.acos(vector23.dot(vector2P) / (vector23.model() * vector2P.model()));
24             
25             // 顶点3的情况
26             var vector31:SHVector = triangle.vector1.sub(triangle.vector3);
27             var vector32:SHVector = triangle.vector2.sub(triangle.vector3);
28             var angle13P:Number = Math.acos(vector31.dot(vector3P) / (vector31.model() * vector3P.model()));
29             var angle23P:Number = Math.acos(vector32.dot(vector3P) / (vector32.model() * vector3P.model()));
30 
31             // 内角和相加不能超过180
32             if ((angle21P + angle31P +
33                  angle12P + angle32P +
34                  angle13P + angle23P) >= 3.1415927)
35                 return false;
36             
37             return true;
38         }

　　2. 同样利用了三角形的夹角，我们想象一下，如果P点在三角形内部，那么向量AP和AC，向量AP和AB之间的夹角应该小于向量AC和AB之间的夹角。利用这个特点，依次判断三角形的每个顶点，如果发现某个顶点不满足这个条件就直接得出P不在三角形中的结论，也就是说三个顶点都必须同时满足这个条件才能得出P点在三角形中的结论。该算法比内角求和效率略高，因为如果P点不在三角形内，就可能在不需要判断每个顶点的情况下就提前得出结论。

 1 static public function detectPointAndTriangleCollision2(point:SHPoint, triangle:SHTriangle):Boolean
 2         {
 3             var vector1P:SHVector = point.vector.sub(triangle.vector1);
 4             var vector2P:SHVector = point.vector.sub(triangle.vector2);
 5             var vector3P:SHVector = point.vector.sub(triangle.vector3);
 6             
 7             // 如果P点正好在定点上
 8             if (vector1P.model() == 0 ||
 9                 vector2P.model() == 0 ||
10                 vector3P.model() == 0)
11                 return true;
12             
13             // 顶点1的情况
14             var vector12:SHVector = triangle.vector2.sub(triangle.vector1);
15             var vector13:SHVector = triangle.vector3.sub(triangle.vector1);
16             var angle213:Number = Math.acos(vector12.dot(vector13) / (vector12.model() * vector13.model()));
17             var angle21P:Number = Math.acos(vector12.dot(vector1P) / (vector12.model() * vector1P.model()));
18             var angle31P:Number = Math.acos(vector13.dot(vector1P) / (vector13.model() * vector1P.model()));
19             
20             if (angle21P > angle213 ||
21                 angle31P > angle213)
22                 return false;
23             
24             // 顶点2的情况
25             var vector21:SHVector = triangle.vector1.sub(triangle.vector2);
26             var vector23:SHVector = triangle.vector3.sub(triangle.vector2);
27             var angle123:Number = Math.acos(vector21.dot(vector23) / (vector21.model() * vector23.model()));
28             var angle12P:Number = Math.acos(vector21.dot(vector2P) / (vector21.model() * vector2P.model()));
29             var angle32P:Number = Math.acos(vector23.dot(vector2P) / (vector23.model() * vector2P.model()));
30             
31             if (angle12P > angle123 ||
32                 angle32P > angle123)
33                 return false;
34             
35             // 顶点3的情况
36             var vector31:SHVector = triangle.vector1.sub(triangle.vector3);
37             var vector32:SHVector = triangle.vector2.sub(triangle.vector3);
38             var angle132:Number = Math.acos(vector31.dot(vector32) / (vector31.model() * vector32.model()));
39             var angle13P:Number = Math.acos(vector31.dot(vector3P) / (vector31.model() * vector3P.model()));
40             var angle23P:Number = Math.acos(vector32.dot(vector3P) / (vector32.model() * vector3P.model()));
41             
42             if (angle13P > angle132 ||
43                 angle23P > angle132)
44                 return false;
45             
46             return true;
47         }

　　3. 同向法。使用了向量叉乘的概念：两个向量叉乘的结果也是一个向量，该向量的方向是垂直于这两个向量组合成的平面，具体方向可以根据右手法则判断出。三角形的三条边都按照顺时针（或逆时针）方向得出三个向量，如果点P在三角形内部，那么点P和每个顶点A,B,C组成的向量与三角形的三条边向量叉乘后的三条垂直向量都会指向同一个方向，否则，点P不在三角形内部。为了判断3条垂直向量的方向是否一致，可以利用向量的点乘，三条向量两两进行点乘（点乘的结果是一个标量），如果结果小于0，即这两条垂直向量反向。

 1 static public function detectPointAndTriangleCollision3(point:SHPoint, triangle:SHTriangle):Boolean
 2         {
 3             var v1:SHVector = null;
 4             var v2:SHVector = null;
 5             
 6             var vector12:SHVector = triangle.vector2.sub(triangle.vector1);
 7             var vector23:SHVector = triangle.vector3.sub(triangle.vector2);
 8             var vector31:SHVector = triangle.vector1.sub(triangle.vector3);
 9             
10             // 检测顶点1的情况，p为待检测的顶点，检测顶点p和定点3是否在向量12的同侧
11             var vector1P:SHVector = point.vector.sub(triangle.vector1);
12             var vector13:SHVector = triangle.vector3.sub(triangle.vector1);
13             
14             v1 = vector12.cross(vector1P);
15             v2 = vector12.cross(vector13);
16             if (v1.dot(v2) < 0) {
17                 return false;
18             }
19             
20             // 检测顶点2的情况
21             var vector2P:SHVector = point.vector.sub(triangle.vector2);
22             var vector21:SHVector = triangle.vector1.sub(triangle.vector2);
23             
24             v1 = vector23.cross(vector2P);
25             v2 = vector23.cross(vector21);
26             if (v1.dot(v2) < 0) {
27                 return false;
28             }
29             
30             // 检测顶点3的情况
31             var vector3P:SHVector = point.vector.sub(triangle.vector3);
32             var vector32:SHVector = triangle.vector2.sub(triangle.vector3);
33             
34             v1 = vector31.cross(vector3P);
35             v2 = vector31.cross(vector32);
36             if (v1.dot(v2) < 0) {
37                 return false;
38             }
39             
40             return true;
41         }

　　4. 利用几何学中点和直线的关系。几何学中表示直线的方程式ax + by + c = 0，如果某个点（x1，y1）在直线上，将坐标点的值带入方程会得到d = ax1 + by1 + c，如果：

　　d = 0：点在直线上；

　　d > 0：点在直线下方（右方）；

　　d < 0：点在直线上方（左方）；

　　根据这个性质，要判断点P是否在三角形内部，我们就需要判断点P是否在三条直线的同一个方向上。首先需要根据两个顶点求出参数a，b，c，假如我们需要求出顶点A和顶点B所在的直线方程，那么：

　　a = y_b - y_a；

　　b = x_a - x_b；

　　c = x_b * y_a - x_a * y_b;

　　在求出a，b，c之后，就可以使用直线方程求d。

　　不过在求出参数之前，我们需要注意一点就是直线没有方向，直线方程可以在两边同时乘以负数，直线方程的意义不会变化，但是这种不确定性对于我们求d值会造成影响。为了规避这种影响，我们需要保证在求三条直线方程的时候，三个顶点以顺时针（或者逆时针）的一个方向进行计算，也就是说在求每条直线方程的两个顶点统一用终点减去起点（或者用起点减去终点）求出斜率。这样就可以保证d的一致性，在求出三个d值（d1，d2，d3）后，如果其中任意两个d相乘的结果小于0，即表示P点不在三角形内部。

 1 static public function detectPointAndTriangleCollision4(point:SHPoint, triangle:SHTriangle):Boolean
 2         {
 3             var a:Number = 0;
 4             var b:Number = 0;
 5             var c:Number = 0;
 6             
 7             var d1:Number = 0;
 8             var d2:Number = 0;
 9             var d3:Number = 0;
10             
11             // 顶点1和顶点2的直线方程
12             a = triangle.vector2.y - triangle.vector1.y;
13             b = triangle.vector1.x - triangle.vector2.x;
14             c = triangle.vector2.x * triangle.vector1.y - triangle.vector1.x * triangle.vector2.y;
15             d1 = a * point.vector.x + b * point.vector.y + c;
16             
17             // 顶点2和顶点3的直线方程
18             a = triangle.vector3.y - triangle.vector2.y;
19             b = triangle.vector2.x - triangle.vector3.x;
20             c = triangle.vector3.x * triangle.vector2.y - triangle.vector2.x * triangle.vector3.y;
21             d2 = a * point.vector.x + b * point.vector.y + c;
22             
23             if (d1 * d2 < 0)
24                 return false;
25             
26             // 顶点3和顶点1的直线方程
27             a = triangle.vector1.y - triangle.vector3.y;
28             b = triangle.vector3.x - triangle.vector1.x;
29             c = triangle.vector1.x * triangle.vector3.y - triangle.vector3.x * triangle.vector1.y;
30             d3 = a * point.vector.x + b * point.vector.y + c;
31             
32             if (d2 * d3 < 0)
33                 return false;
34             
35             return true;
36         }

　　5. 使用了基座标的概念。

　　（图片来博客：http://www.cnblogs.com/graphics/archive/2010/08/05/1793393.html）

　　如图，我们把AC和AB看做两个基座标轴，就像笛卡尔坐标系中的x轴和y轴。有了坐标轴，我们就可以用该坐标轴表示任意向量了，于是有AP = u * AC + v * AB（这里也可以看作是向量加法的概念），为了保证在P点在三角形内部，u和v必须满足一定的关系：

　　u>0：AP的"x"坐标点在AP的正方向上；

　　v>0：AP的"y"坐标点在AB的正方向上；

　　u+v<=1：根据两个特殊点B，C，我们可以看出u+v的关系;

　　现在我们只需要求出u和v即可，除了利用向量加法得出一个方程外，我们还可以利用点乘的几何意义（平行四边形的面积公式），得出u和v的另一个关于面积计算的方程。但是这个计算过程比较麻烦。下面给出一个来自互联网（博客：http://www.cnblogs.com/graphics/archive/2010/08/05/1793393.html）的更加简练的算法，该算法直接在上诉方程两边分别乘以向量AC和AB得出两个方程，在求解u和v。

 1 static public function detectPointAndTriangleCollision5(point:SHPoint, triangle:SHTriangle):Boolean
 2         {
 3             var vectorAP:SHVector = point.vector.sub(triangle.vector1);
 4             var vectorAB:SHVector = triangle.vector2.sub(triangle.vector1);
 5             var vectorAC:SHVector = triangle.vector3.sub(triangle.vector1);
 6             
 7             var dotACAC:Number = vectorAC.dot(vectorAC);
 8             var dotACAB:Number = vectorAC.dot(vectorAB);
 9             var dotACAP:Number = vectorAC.dot(vectorAP);
10             var dotABAB:Number = vectorAB.dot(vectorAB);
11             var dotABAP:Number = vectorAB.dot(vectorAP);
12             
13             var num1:Number = 1 / (dotACAC * dotABAB - dotACAB * dotACAB);
14             
15             var u:Number = (dotABAB * dotACAP - dotACAB * dotABAP) * num1;
16             if (u < 0 || u > 1)
17                 return false;
18             
19             var v:Number = (dotACAC * dotABAP - dotACAB * dotACAP) * num1;
20             if (v < 0 || v > 1)
21                 return false;
22             
23             return u + v <= 1;
24         }

图形碰撞检测 点与三角形

图形碰撞检测点与三角形