-----------------------------------------3D---------------------------------------
文章出處：https://www.cnblogs.com/graphics/archive/2010/08/05/1793393.html
原作者：zdd
注明：我只是為了自己學(xué)習(xí)照搬
概述：給定三角形ABC和一點P(x,y,z)，判斷點P是否在ABC內(nèi)。這是游戲設(shè)計中一個常見的問題。需要注意的是，這里假定點和三角形位于同一個平面內(nèi)。
本文介紹三種不同的方法，由淺入深
一內(nèi)角和法
連接點P和三角形的三個頂點得到三條線段PA，PB和PC，求出這三條線段與三角形各邊的夾角，如果所有夾角之和為180度，那么點P在三角形內(nèi)，否則不在，此法直觀，但效率低下。
二同向法
假設(shè)點P位于三角形內(nèi)，會有這樣一個規(guī)律，當(dāng)我們沿著ABCA的方向在三條邊上行走時，你會發(fā)現(xiàn)點P始終位于邊AB，BC和CA的右側(cè)。我們就利用這一點，但是如何判斷一個點在線段的左側(cè)還是右側(cè)呢？我們可以從另一個角度來思考，當(dāng)選定線段AB時，點C位于AB的右側(cè)，同理選定BC時，點A位于BC的右側(cè)，最后選定CA時，點B位于CA的右側(cè)，所以當(dāng)選擇某一條邊時，我們只需驗證點P與該邊所對的點在同一側(cè)即可。問題又來了，如何判斷兩個點在某條線段的同一側(cè)呢？可以通過叉積來實現(xiàn)，連接PA，將PA和AB做叉積，再將CA和AB做叉積，如果兩個叉積的結(jié)果方向一致，那么兩個點在同一測。判斷兩個向量的是否同向可以用點積實現(xiàn)，如果點積大于0，則兩向量夾角是銳角，否則是鈍角。
代碼如下，為了實現(xiàn)程序功能，添加了一個Vector3類，該類表示三維空間中的一個向量。
// 3D vector
class Vector3
{
public:
Vector3(float fx, float fy, float fz)
:x(fx), y(fy), z(fz)
{
}
// Subtract
Vector3 operator - (const Vector3& v) const
{
return Vector3(x - v.x, y - v.y, z - v.z) ;
}
// Dot product
float Dot(const Vector3& v) const
{
return x * v.x + y * v.y + z * v.z ;
}
// Cross product
Vector3 Cross(const Vector3& v) const
{
return Vector3(
y * v.z - z * v.y,
z * v.x - x * v.z,
x * v.y - y * v.x ) ;
}
public:
float x, y, z ;
};
// Determine whether two vectors v1 and v2 point to the same direction
// v1 = Cross(AB, AC)
// v2 = Cross(AB, AP)
bool SameSide(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
{
Vector3 AB = B - A ;
Vector3 AC = C - A ;
Vector3 AP = P - A ;
Vector3 v1 = AB.Cross(AC) ;
Vector3 v2 = AB.Cross(AP) ;
// v1 and v2 should point to the same direction
return v1.Dot(v2) >= 0 ;
}
// Same side method
// Determine whether point P in triangle ABC
bool PointinTriangle1(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
{
return SameSide(A, B, C, P) &&
SameSide(B, C, A, P) &&
SameSide(C, A, B, P) ;
}
//類定義：二維向量 2D vector
Laya ts寫法
//確定兩個向量v1和v2是否指向相同的方向
public SameSide(A: Laya.Vector3, B: Laya.Vector3, C: Laya.Vector3, P: Laya.Vector3) {
let AB: Laya.Vector3 = new Laya.Vector3();
let AC: Laya.Vector3 = new Laya.Vector3();
let AP: Laya.Vector3 = new Laya.Vector3();
Laya.Vector3.subtract(B, A, AB);
Laya.Vector3.subtract(C, A, AC);
Laya.Vector3.subtract(P, A, AP);
let v1: Laya.Vector3 = new Laya.Vector3();
let v2: Laya.Vector3 = new Laya.Vector3();
Laya.Vector3.cross(AB, AC, v1);
Laya.Vector3.cross(AB, AP, v2);
// 判斷v1和v2是否指向同一個方向
let num = Laya.Vector3.dot(v1, v2)
return num >= 0;
}
//確定三角形ABC三點中的點P
public PointinTriangle1(A: Laya.Vector3, B: Laya.Vector3, C: Laya.Vector3, P: Laya.Vector3) {
return this.SameSide(A, B, C, P) && this.SameSide(B, C, A, P) && this.SameSide(C, A, B, P);
}
三 重心法
上面這個方法簡單易懂，速度也快，下面這個方法速度更快，只是稍微多了一點數(shù)學(xué)而已
三角形的三個點在同一個平面上，如果選中其中一個點，其他兩個點不過是相對該點的位移而已，比如選擇點A作為起點，那么點B相當(dāng)于在AB方向移動一段距離得到，而點C相當(dāng)于在AC方向移動一段距離得到
所以對于平面內(nèi)任意一點，都可以由如下方程來表示
P = A + u * (C – A) + v * (B - A) // 方程1
如果系數(shù)u或v為負值，那么相當(dāng)于朝相反的方向移動，即BA或CA方向。那么如果想讓P位于三角形ABC內(nèi)部，u和v必須滿足什么條件呢？有如下三個條件
u >= 0
v >= 0
u + v <= 1
幾個邊界情況，當(dāng)u = 0且v = 0時，就是點A，當(dāng)u = 0,v = 1時，就是點B，而當(dāng)u = 1, v = 0時，就是點C
整理方程1得到P – A = u(C - A) + v(B - A)
令v0 = C – A, v1 = B – A, v2 = P – A，則v2 = u * v0 + v * v1，現(xiàn)在是一個方程，兩個未知數(shù)，無法解出u和v，將等式兩邊分別點乘v0和v1的到兩個等式
(v2) ? v0 = (u * v0 + v * v1) ? v0
(v2) ? v1 = (u * v0 + v * v1) ? v1
注意到這里u和v是數(shù)，而v0，v1和v2是向量，所以可以將點積展開得到下面的式子。
v2 ? v0 = u * (v0 ? v0) + v * (v1 ? v0) // 式1
v2 ? v1 = u * (v0 ? v1) + v * (v1? v1) // 式2
解這個方程得到
u = ((v1?v1)(v2?v0)-(v1?v0)(v2?v1)) / ((v0?v0)(v1?v1) - (v0?v1)(v1?v0))
v = ((v0?v0)(v2?v1)-(v0?v1)(v2?v0)) / ((v0?v0)(v1?v1) - (v0?v1)(v1?v0))
是時候上代碼了，這段代碼同樣用到上面的Vector3類
// Determine whether point P in triangle ABC
bool PointinTriangle(Vector3 A, Vector3 B, Vector3 C, Vector3 P)
{
Vector3 v0 = C - A ;
Vector3 v1 = B - A ;
Vector3 v2 = P - A ;
float dot00 = v0.Dot(v0) ;
float dot01 = v0.Dot(v1) ;
float dot02 = v0.Dot(v2) ;
float dot11 = v1.Dot(v1) ;
float dot12 = v1.Dot(v2) ;
float inverDeno = 1 / (dot00 * dot11 - dot01 * dot01) ;
float u = (dot11 * dot02 - dot01 * dot12) * inverDeno ;
if (u < 0 || u > 1) // if u out of range, return directly
{
return false ;
}
float v = (dot00 * dot12 - dot01 * dot02) * inverDeno ;
if (v < 0 || v > 1) // if v out of range, return directly
{
return false ;
}
return u + v <= 1 ;
Laya ts寫法
//確定三角形ABC三點中的點P
public PointinTriangle2(A: Laya.Vector3, B: Laya.Vector3, C: Laya.Vector3, P: Laya.Vector3) {
let v0: Laya.Vector3 = new Laya.Vector3();
let v1: Laya.Vector3 = new Laya.Vector3();
let v2: Laya.Vector3 = new Laya.Vector3();
Laya.Vector3.subtract(C, A, v0);
Laya.Vector3.subtract(B, A, v1);
Laya.Vector3.subtract(P, A, v2);
let dot00 = Laya.Vector3.dot(v0, v0);
let dot01 = Laya.Vector3.dot(v0, v1);
let dot02 = Laya.Vector3.dot(v0, v2);
let dot11 = Laya.Vector3.dot(v1, v1);
let dot12 = Laya.Vector3.dot(v1, v2);
let inverDeno = 1 / (dot00 * dot11 - dot01 * dot01);
let u = (dot11 * dot02 - dot01 * dot12) * inverDeno;
if (u < 0 || u > 1) //如果u超出范圍，直接返回
{
return false;
}
let v = (dot00 * dot12 - dot01 * dot02) * inverDeno;
if (v < 0 || v > 1) // 如果v超出范圍，直接返回
{
return false;
}
return u + v <= 1
}
-----------------------------------------2D---------------------------------------
文章轉(zhuǎn)載：http://www.cnblogs.com/TenosDoIt/p/4024413.html
原作者：tenos
注明：我只是為了自己學(xué)習(xí)照搬
二維平面上判斷點是否在三角形內(nèi)
已知三角形的三個頂點坐標(biāo)，判斷某個點是否在三角形中（在三角形的邊上，我們也視作在三角形中），本文給出了三種方法。
算法1
面積法，如上圖所示，如果點P在三角形ABC的內(nèi)部，則三個小三角形PAB, PBC, PAC的面積之和 = ABC的面積，反之則不相等。三角形的三個頂點坐標(biāo)求其面積，可以根據(jù)向量的叉乘，參考鏈接地址
該算法詳見后面代碼中的函數(shù)：IsPointInTriangle1
算法2
首先看一下這個問題，如何判斷某兩個點在某條直線的同一側(cè)（代碼中函數(shù)：IsPointAtSameSideOfLine）
根據(jù)向量的叉乘以及右手螺旋定則，AB^AM （表示叉乘，這里向量省略了字母上面的箭頭符號）的方向為向外指出屏幕，ABAN也是向外指出屏幕，但AB^AO的方向是向內(nèi)指向屏幕，因此M,N在直線AB的同側(cè)，M ,O在直線AB的兩側(cè)。實際計算時，只需要考慮叉積的數(shù)值正負
假設(shè)以上各點坐標(biāo)為A(0,0), B(4,0), M(1,2), N(3,4), O(3,-4)， 則：
AB^AM = (4,0)^(1,2) = 42 - 01 = 8
AB^AN = (4，0)^(3，4) = 44 – 03 = 16
AB^AO = (4,0)^(3,-4) = 4-4 – 03 = –16
由上面的數(shù)值可知，可以根據(jù)數(shù)值的正負判斷叉乘后向量的方向。即，如果叉積AB^AM 和 ABAN的結(jié)果同號，那么M,N兩點就在直線的同側(cè)，否則不在同一側(cè)。特殊地，如果點M在直線AB上，則ABAM的值為0。（如果是在三維坐標(biāo)系中，求出的叉積是一個向量，可以根據(jù)兩個向量的點積結(jié)果正負來判斷兩個向量的是否指向同一側(cè)）
以上的問題解決了，就很容易的用來判斷某個點是否在三角形內(nèi)，如果P在三角形ABC內(nèi)部，則滿足以下三個條件：P,A在BC的同側(cè)、P,B在AC的同側(cè)、PC在AB的同側(cè)。某一個不滿足則表示P不在三角形內(nèi)部。
該算法詳見后面代碼中的函數(shù)：IsPointInTriangle2
算法3
該方法也用到了向量。對于三角形ABC和一點P，可以有如下的向量表示：
p點在三角形內(nèi)部的充分必要條件是：1 >= u >= 0, 1 >= v >= 0, u+v <= 1。
已知A,B,C,P四個點的坐標(biāo)，可以求出u，v，把上面的式子分別點乘向量AC和向量AB
解方程得到：
解出u，v后只需要看他們是否滿足“1 >= u >= 0, 1 >= v >= 0, u+v <= 1”，如滿足，則，p 在三角形內(nèi)。
（u = 0時，p在AB上， v = 0時，p在AC上，兩者均為0時，p和A重合）
該算法詳見后面代碼中的函數(shù)：IsPointInTriangle3
算法4
該算法和算法2類似，可以看作是對算法2的簡化，也是用到向量的叉乘。假設(shè)三角形的三個點按照順時針（或者逆時針）順序是A,B,C。對于某一點P，求出三個向量PA,PB,PC, 然后計算以下三個叉乘（^表示叉乘符號）：
t1 = PA^PB,
t2 = PB^PC,
t3 = PC^PA,
如果t1，t2，t3同號（同正或同負），那么P在三角形內(nèi)部，否則在外部。
該算法詳見后面代碼中的函數(shù)：IsPointInTriangle4
原代碼是C語言寫的我轉(zhuǎn)換成了TS
//經(jīng)過測試，算法4最快，算法3次之，接著算法2，算法1最慢。直觀的從計算量上來看，也是算法4的計算量最少。
//以下是代碼，定義了兩個類：二維向量類 和 三角形類
//類定義：二維向量
class V2 {
constructor(x: number, y: number) {
this.x_ = x;
this.y_ = y;
}
private x_: number = 0;
private y_: number = 0;
//二維向量叉乘, 叉乘的結(jié)果其實是向量，方向垂直于兩個向量組成的平面，這里我們只需要其大小和方向
CrossProduct(vec: V2): number {
return this.x_ * vec.y_ - this.y_ * vec.x_;
}
//二維向量點積
DotProduct(vec: V2): number {
return this.x_ * vec.x_ + this.y_ * vec.y_;
}
//二維向量減法
Minus(vec: V2): V2 {
return new V2(this.x_ - vec.x_, this.y_ - vec.y_);
}
//判斷點M,N是否在直線AB的同一側(cè)
static IsPointAtSameSideOfLine(pointM: V2, pointN: V2, pointA: V2, pointB: V2): boolean {
let AB = pointB.Minus(pointA);
let AM = pointM.Minus(pointA);
let AN = pointN.Minus(pointA);
//等于0時表示某個點在直線上
return AB.CrossProduct(AM) * AB.CrossProduct(AN) >= 0;
}
}
//三角形類
class Triangle {
private pointA_: V2;
private pointB_: V2;
private pointC_: V2;
constructor(point1: V2, point2: V2, point3: V2) {
this.pointA_ = point1;
this.pointB_ = point2;
this.pointC_ = point3;
}
//計算三角形面積
ComputeTriangleArea() {
//依據(jù)兩個向量的叉乘來計算，可參考http://blog.csdn.net/zxj1988/article/details/6260576
let AB: V2 = this.pointB_.Minus(this.pointA_);
let BC: V2 = this.pointC_.Minus(this.pointB_);
// 原文： fabs(AB.CrossProduct(BC) / 2.0);
return Math.abs(AB.CrossProduct(BC) / 2.0);
}
//算法1
IsPointInTriangle1(pointP: V2) {
let area_ABC = this.ComputeTriangleArea();
let area_PAB = new Triangle(pointP, this.pointA_, this.pointB_).ComputeTriangleArea();
let area_PAC = new Triangle(pointP, this.pointA_, this.pointC_).ComputeTriangleArea();
let area_PBC = new Triangle(pointP, this.pointB_, this.pointC_).ComputeTriangleArea();
// 原文： if (fabs(area_PAB + area_PBC + area_PAC - area_ABC) < 0.000001)
if (Math.abs(area_PAB + area_PBC + area_PAC - area_ABC) < 0.000001)
return true;
else return false;
}
//算法2
IsPointInTriangle2(pointP: V2) {
return V2.IsPointAtSameSideOfLine(pointP, this.pointA_, this.pointB_, this.pointC_) &&
V2.IsPointAtSameSideOfLine(pointP, this.pointB_, this.pointA_, this.pointC_) &&
V2.IsPointAtSameSideOfLine(pointP, this.pointC_, this.pointA_, this.pointB_);
}
//算法3
IsPointInTriangle3(pointP: V2) {
let AB = this.pointB_.Minus(this.pointA_);
let AC = this.pointC_.Minus(this.pointA_);
let AP = pointP.Minus(this.pointA_);
let dot_ac_ac = AC.DotProduct(AC);
let dot_ac_ab = AC.DotProduct(AB);
let dot_ac_ap = AC.DotProduct(AP);
let dot_ab_ab = AB.DotProduct(AB);
let dot_ab_ap = AB.DotProduct(AP);
let tmp = 1.0 / (dot_ac_ac * dot_ab_ab - dot_ac_ab * dot_ac_ab);
let u = (dot_ab_ab * dot_ac_ap - dot_ac_ab * dot_ab_ap) * tmp;
if (u < 0 || u > 1)
return false;
let 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;
}
//算法4
IsPointInTriangle4(pointP: V2) {
let PA = this.pointA_.Minus(pointP);
let PB = this.pointB_.Minus(pointP);
let PC = this.pointC_.Minus(pointP);
let t1 = PA.CrossProduct(PB);
let t2 = PB.CrossProduct(PC);
let t3 = PC.CrossProduct(PA);
// return t1 * t2 >= 0 && t1 * t3 >= 0;
return t1 * t2 >= 0 && t1 * t3 >= 0 && t2 * t3 >= 0;
}
}
