如何半斷點在三角形內..

作者 l314 (紅蟲) 站內 P_RedBug

標題 [ACM]如何判斷點在三角形內..
時間 Mon Sep 11 16:24:08 2006
───────────────────────────────────────


在網路上找到的方法有:

1.http://tinyurl.com/mr6oo
vector A=P2-P1
B=P3-P1
d1 and d2 are scalars

Q is in/on the triangule if and only if

d1 A + d2 B = Q

d1, d2, d1+d2 皆必須在 interval (0,1)

two variables, two equations. you can solve it and use the constraint
to verify.

蟲曰:但是這個要解方程式，轉成程式碼不知道複雜度高不高..


2.http://bbs.gamedev.csdn.net/Web/45315/ShowPost.aspx
可以用地圖學中求國土面積的格林公式求解,

這個格林公式是專為大量邊界計算的高效公式,

設三角形ABC與點P,A->B->C是逆時針的,

則用格林公式,求得四邊形ABCP的面積S1,

再用格林公式,求三角形ABC的面積S2,

if ((S1與S2同號 && abs(S1)>abs(S2)) || (S1與S2異號)) {

則P在三角形ABC之外

} else {

otherwise.

}

蟲曰:格林公式看起來，好像要學過微分方程才看能得懂..

化為可計算的公式可能還需要數值分析的知識吧...XD

似乎愈是簡單的演算法，就愈要愈難的數學公式support..


3.http://dormforce.net/Blog/tangb4c/archive/2006/08/05/10083.aspx
http://www.aougu.net/display.php?id=193

三角型外有點P，三角型ABC，先算ABC的面積，然後算三角形APB，BPC，CPA的面積，

加起來的和如果等於ABC的面積的話，那就是在三角型內（或邊上）了

蟲曰：此法看起來最簡單，也很好寫程式，

但計算每一邊長，並用海頓公式計算四個三角形面積，

不知道是否比向量分析快...

而且若點很接近三角形，算出的面積誤差值，可能導致結果誤判..


4.向量分析(高中數學的算法)

設三角形由A,B,C三點構成，和一點P,

分別測試P與三頂點之連線，是否與AB,BC,AC三線段相交，

若都無相交，便是在三角形內...

要用到的數學只有內積..


5.http://www.aougu.net/display.php?id=193

最簡單的方法，

設三角形由A,B,C三點構成，和一點P,

檢查P點的座標值，是否同時滿足在任意兩個頂點的x坐標之間 &&

任意其餘兩個縱坐標之間就行了....
要用到的數學只有內積..


5.http://www.aougu.net/display.php?id=193

最簡單的方法，

設三角形由A,B,C三點構成，和一點P,

檢查P點的座標值，是否同時滿足在任意兩個頂點的x坐標之間 &&

任意其餘兩個縱坐標之間就行了....


蟲曰：這個方法看似很簡單，但...我自己畫圖驗證，

可以輕易找到反例耶..應該是錯誤的方法...>,<

--
╭ ＊ Origin：[ 狂 狷 年 少 ] whshs.cs.nccu.edu.tw < 140.119.164.16 > ╮
│ ＊ From：redbug.dorm9.nccu.edu.tw │
┼─ ＫＧＢＢＳ ──────────────────────────┼