0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 二维平面上判断点是否在三角形内

AB^AM = (4,0)^(1,2) = 4*2 - 0*1 = 8

AB^AN = (4，0)^(3，4) = 4*4 – 0*3 = 16

AB^AO = (4,0)^(3,-4) = 4*-4 – 0*3 = –16

p点在三角形内部的充分必要条件是：1 >= u >= 0,   1 >= v >= 0,   u+v <= 1。

（u = 0时，p在AB上， v = 0时，p在AC上，两者均为0时，p和A重合）

t1 = PA^PB,

t2 = PB^PC,

t3 = PC^PA,

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 `#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``#include` ` ``using` `namespace` `std;`   `//类定义：二维向量` `class` `Vector2d` `{` `public``:` `    ``double` `x_;` `    ``double` `y_;`   `public``:` `    ``Vector2d(``double` `x, ``double` `y):x_(x), y_(y){}` `    ``Vector2d():x_(0), y_(0){}`   `    ``//二维向量叉乘, 叉乘的结果其实是向量，方向垂直于两个向量组成的平面，这里我们只需要其大小和方向` `    ``double` `CrossProduct(``const` `Vector2d vec)` `    ``{` `        ``return` `x_*vec.y_ - y_*vec.x_;` `    ``}`   `    ``//二维向量点积` `    ``double` `DotProduct(``const` `Vector2d vec)` `    ``{` `        ``return` `x_ * vec.x_ + y_ * vec.y_;` `    ``}`   `    ``//二维向量减法` `    ``Vector2d Minus(``const` `Vector2d vec) ``const` `    ``{` `        ``return` `Vector2d(x_ - vec.x_, y_ - vec.y_);` `    ``}`   `    ``//判断点M,N是否在直线AB的同一侧` `    ``static` `bool` `IsPointAtSameSideOfLine(``const` `Vector2d &pointM, ``const` `Vector2d &pointN, ` `                                        ``const` `Vector2d &pointA, ``const` `Vector2d &pointB)` `    ``{` `        ``Vector2d AB = pointB.Minus(pointA);` `        ``Vector2d AM = pointM.Minus(pointA);` `        ``Vector2d AN = pointN.Minus(pointA);`   `        ``//等于0时表示某个点在直线上` `        ``return` `AB.CrossProduct(AM) * AB.CrossProduct(AN) >= 0;` `    ``}` `};`   `//三角形类` `class` `Triangle` `{` `private``:` `    ``Vector2d pointA_, pointB_, pointC_;`   `public``:` `    ``Triangle(Vector2d point1, Vector2d point2, Vector2d point3)` `        ``:pointA_(point1), pointB_(point2), pointC_(point3)` `    ``{` `        ``//todo 判断三点是否共线` `    ``}`   `    ``//计算三角形面积` `    ``double` `ComputeTriangleArea()` `    ``{` `        ``//依据两个向量的叉乘来计算，可参考http://blog.csdn.net/zxj1988/article/details/6260576` `        ``Vector2d AB = pointB_.Minus(pointA_);` `        ``Vector2d BC = pointC_.Minus(pointB_);` `        ``return` `fabs``(AB.CrossProduct(BC) / 2.0);` `    ``}`   `    ``bool` `IsPointInTriangle1(``const` `Vector2d pointP)` `    ``{` `        ``double` `area_ABC = ComputeTriangleArea();` `        ``double` `area_PAB = Triangle(pointP, pointA_, pointB_).ComputeTriangleArea();` `        ``double` `area_PAC = Triangle(pointP, pointA_, pointC_).ComputeTriangleArea();` `        ``double` `area_PBC = Triangle(pointP, pointB_, pointC_).ComputeTriangleArea();`   `        ``if``(``fabs``(area_PAB + area_PBC + area_PAC - area_ABC) < 0.000001)` `            ``return` `true``;` `        ``else` `return` `false``;` `    ``}`   `    ``bool` `IsPointInTriangle2(``const` `Vector2d pointP)` `    ``{` `        ``return` `Vector2d::IsPointAtSameSideOfLine(pointP, pointA_, pointB_, pointC_) &&` `            ``Vector2d::IsPointAtSameSideOfLine(pointP, pointB_, pointA_, pointC_) &&` `            ``Vector2d::IsPointAtSameSideOfLine(pointP, pointC_, pointA_, pointB_);` `    ``}`   `    ``bool` `IsPointInTriangle3(``const` `Vector2d pointP)` `    ``{` `        ``Vector2d AB = pointB_.Minus(pointA_);` `        ``Vector2d AC = pointC_.Minus(pointA_);` `        ``Vector2d AP = pointP.Minus(pointA_);` `        ``double` `dot_ac_ac = AC.DotProduct(AC);` `        ``double` `dot_ac_ab = AC.DotProduct(AB);` `        ``double` `dot_ac_ap = AC.DotProduct(AP);` `        ``double` `dot_ab_ab = AB.DotProduct(AB);` `        ``double` `dot_ab_ap = AB.DotProduct(AP);`   `        ``double` `tmp = 1.0 / (dot_ac_ac * dot_ab_ab - dot_ac_ab * dot_ac_ab);` `        `  `        ``double` `u = (dot_ab_ab * dot_ac_ap - dot_ac_ab * dot_ab_ap) * tmp;` `        ``if``(u < 0 || u > 1)` `            ``return` `false``;` `        ``double` `v = (dot_ac_ac * dot_ab_ap - dot_ac_ab * dot_ac_ap) * tmp;` `        ``if``(v < 0 || v > 1)` `            ``return` `false``;`   `        ``return` `u + v <= 1;` `    ``}`   `    ``bool` `IsPointInTriangle4(``const` `Vector2d pointP)` `    ``{` `        ``Vector2d PA = pointA_.Minus(pointP);` `        ``Vector2d PB = pointB_.Minus(pointP);` `        ``Vector2d PC = pointC_.Minus(pointP);` `        ``double` `t1 = PA.CrossProduct(PB);` `        ``double` `t2 = PB.CrossProduct(PC);` `        ``double` `t3 = PC.CrossProduct(PA);` `        ``return` `t1*t2 >= 0 && t1*t3 >= 0;` `    ``}` `};`     `int` `main()` `{` `    ``Triangle tri(Vector2d(0,0), Vector2d(6,6), Vector2d(12,0));` `    ``srand``(``time``(0));` `    ``for``(``int` `i = 0; i < 20; ++i)` `    ``{` `         ``Vector2d point((``rand``()*1.0 / RAND_MAX) * 12, (``rand``()*1.0 / RAND_MAX) * 6);` `         ``cout<

+ 关注