如何判斷一個點是否在一個三角形内。
測試樣例：
class POINT{
int x;
int y;
public POINT(int x,int y){
this.x = x;
this.y = y;
}
}
思路一： 面積法：如果一個點在三角形内，其與三角形的三個點構成的三個子三角形的面積等于大三角形的面積。否則，大于大三角形的面積。
是以，這個問題就轉化成如何在知道三角形的三個點的情況下，求這個三角形的面積的問題了。
因為所有點的坐标已知，我們有幾種方式計算面積：
1）首先可以計算出每條邊的長度及周長，我們就可以利用海倫公式計算面積，然後進行比較。
S=p(p−a)(p−b)(p−c)−−−−−−−−−−−−−−−−−√ S = sqrt{p(p-a)(p-b)(p-c)}
S=
p(p−a)(p−b)(p−c)
p=(a+b+c)2 p = frac{(a+b+c)}{2}
p=
2
(a+b+c)
2）向量法：先求出這個三角形的對應的平行四邊形的面積。然後這個面積的1/2就是三角形的面積了。
先随意選擇兩個點，如B、C通過其坐标相減得向量（B，C）。記得誰減另一個就是指向誰。然後求出其中一個點和剩下一個點的向量。這兩個向量的叉乘的便是平行四邊形的面積。除以2就是三角形的面積。（注意這裡是叉乘 (cross product)，而非點乘（dot product））。
（補充）向量之間的積分為兩種：叉乘和點乘。叉乘求面積，點乘求投影。這是兩者的意義。而且，叉乘理論得到的是一個向量，而點乘得到的是一個标量。
代碼：private static final double ABS_DOUBLE_0 = 0.0001;
public static boolean isInTriangle(POINT A, POINT B, POINT C, POINT P) {
double ABC = triAngleArea(A, B, C);
double ABp = triAngleArea(A, B, P);
double ACp = triAngleArea(A, C, P);
double BCp = triAngleArea(B, C, P);
double sumOther = ABp + ACp + BCp;
if (-ABS_DOUBLE_0 < (ABC - sumOther) && (ABC - sumOther) < ABS_DOUBLE_0) { // 若面積之和等于原三角形面積，證明點在三角形内
return true;
} else {
return false;
}
}
private static double triAngleArea(POINT A, POINT B, POINT C) { // 由三個點計算這三個點組成三角形面積
POINT ab,bc;
ab = new POINT(B.x - A.x,B.y - A.y);//
bc = new POINT(C.x - B.x,C.y - B.y);
return Math.abs((ab.x * bc.y - ab.y * bc.x) / 2.0);
}
思路二： 同向法：假設點P位于三角形内，會有這樣一個規律，當我們沿着ABCA的方向在三條邊上行走時，你會發現點P始終位于邊AB，BC和CA的右側。我們就利用這一點，但是如何判斷一個點線上段的左側還是右側呢？我們可以從另一個角度來思考，當選定線段AB時，點C位于AB的右側，同理標明BC時，點A位于BC的右側，最後標明CA時，點B位于CA的右側，是以當選擇某一條邊時，我們隻需驗證點P與該邊所對的點在同一側即可。問題又來了，如何判斷兩個點在某條線段的同一側呢？可以通過叉積來實作，連接配接PA，将PA和AB做叉積，再将CA和AB做叉積，如果兩個叉積的結果方向一緻，那麼兩個點在同一測。
public static boolean isInTriangle(POINT A, POINT B, POINT C, POINT P) {
int a = 0, b = 0, c = 0;
POINT MA = new POINT(P.x - A.x,P.y - A.y);
POINT MB = new POINT(P.x - B.x,P.y - B.y);
POINT MC = new POINT(P.x - C.x,P.y - C.y);
a = MA.x * MB.y - MA.y * MB.x;
b = MB.x * MC.y - MB.y * MC.x;
c = MC.x * MA.y - MC.y * MA.x;
if((a <= 0 && b <= 0 && c <= 0)||
(a > 0 && b > 0 && c > 0))
return true;
return false;
}
思路三： 重心法：我們都知道，三角形的三個點在同一個平面上，如果選中其中一個點，其他兩個點不過是相對該點的位移而已，比如選擇點A作為起點，那麼點B相當于在AB方向移動一段距離得到，而點C相當于在AC方向移動一段距離得到。
是以對于平面内任意一點，都可以由如下方程來表示。
P=A+u∗(C−A)+v∗(B−A) P = A + u * (C-A) + v * (B-A)
P=A+u∗(C−A)+v∗(B−A)
如果系數u或v為負值，那麼相當于朝相反的方向移動，即BA或CA方向。那麼如果想讓P位于三角形ABC内部，u和v必須滿足什麼條件呢？有如下三個條件：
u >= 0
v >= 0
u + v <= 1
幾個邊界情況：
當u = 0，v = 0 時，就是點A；
當u = 0，v = 1 時，就是點B；
當u = 1，v = 0 時，就是點C。
整理方程1得到：
P−A=u(C−A)+v(B−A) P-A = u(C-A) + v(B-A)
P−A=u(C−A)+v(B−A)
令 v0 = C – A, v1 = B – A, v2 = P – A，則
v2=u∗v0+v∗v1 v2 = u * v0 + v * v1
v2=u∗v0+v∗v1
現在是一個方程，兩個未知數，無法解出u和v，是以将等式兩邊分别點乘v0和v1的到兩個等式：(
ps.下面公式中的·符号代表“點乘”)
(v2)⋅v0=(u∗v0+v∗v1)⋅v0 (v2)·v0 = (u * v0 + v * v1)·v0
(v2)⋅v0=(u∗v0+v∗v1)⋅v0
(v2)⋅v1=(u∗v0+v∗v1)⋅v1 (v2)·v1 = (u * v0 + v * v1)·v1
(v2)⋅v1=(u∗v0+v∗v1)⋅v1
注意到這裡u和v是數，而v0，v1和v2是向量，是以可以将點積展開得到下面的式子。
v2⋅v0=u∗(v0⋅v0)+v∗(v1⋅v0) v2·v0 = u * (v0·v0) + v * (v1·v0)
v2⋅v0=u∗(v0⋅v0)+v∗(v1⋅v0)
v2⋅v1=u∗(v0⋅v1)+v∗(v1⋅v1) v2·v1 = u * (v0·v1) + v * (v1·v1)
v2⋅v1=u∗(v0⋅v1)+v∗(v1⋅v1)
解這個方程得到:
u=((v1⋅v1)(v2⋅v0)−(v1⋅v0)(v2⋅v1))/((v0⋅v0)(v1⋅v1)−(v0⋅v1)(v1⋅v0)) u = ((v1·v1)(v2·v0)-(v1·v0)(v2·v1)) / ((v0·v0)(v1·v1) - (v0·v1)(v1·v0))
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)) v = ((v0·v0)(v2·v1)-(v0·v1)(v2·v0)) / ((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))
代碼private static boolean isInTriangle(POINT p, POINT a, POINT b, POINT c) {
POINT AB, AC, AP;
AB = new POINT(b.x - a.x, b.y - a.y);
AC = new POINT(c.x - a.x, c.y - a.y);
AP = new POINT(p.x - a.x, p.y - a.y);
float dot00 = dotProduct(AC, AC);
float dot01 = dotProduct(AC, AB);
float dot02 = dotProduct(AC, AP);
float dot11 = dotProduct(AB, AB);
float dot12 = dotProduct(AB, AP);
float inverDeno = 1 / (dot00 * dot11 - dot01 * dot01);
// 計算重心坐标
float u = (dot11 * dot02 - dot01 * dot12) * inverDeno;
float v = (dot00 * dot12 - dot01 * dot02) * inverDeno;
return (u >= 0) && (v >= 0) && (u + v < 1);
}
private static float dotProduct(POINT p1, POINT p2) {
return p1.x * p2.x + p1.y * p2.y;
}
點選“java架構”