Re: [問題] 判斷點有無在區塊內
※ 引述《elru8cjo4 (XD~猴~XD)》之銘言：
: 想請問一下
: A
: / \
: / \
: / ‧D \
: B/_______\C => 三角形 ; A,B,C,D 都是座標點
: 依此圖
: 我要怎麼樣去判斷D這個點是不是在ABC三角形裡面？？
: JAVA裡面有內建的方法可以用嗎？
: 因為會有很多個點,每個點都要判斷
: 不知道有什麼好的演算法 > <
: 麻煩大家了 謝謝︿︿
用向量的觀點來看
把BA AC CB 都看成向量(注意，順序不能錯)
D在三角形向部 iff D在BA AC CB的同一側
具體來看，假設你站在B，向A看，D會在你的右手邊
A C
C B
判斷的方式，可以用BA 和 BD 的夾角來看
取其sin 值，+ - 不同邊， 0 在線段上
由以下公式可以算出sin 值
A(x1, y1) B(x2, y2) D(x3, y3)
面積 = 面積
1 | (x1-x2) (x3-x2) 0| 1
---| (y1-y2) (y3-y2) 0| = --- sin * |A||B|
2 | 1 1 1| 2
由於我們只是要知道sin的值
所以只要計算 (x1-x2)(y3-y2) - (x3-x2)(y1-y2) 的值出來
如果三個方向 都正 或都負 就在內部 (零表示在線上)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.242.95
討論串 (同標題文章)