作者Domos (Domos)
看板java
标题Re: [问题] 判断点有无在区块内
时间Tue May 27 15:25:21 2008
※ 引述《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