作者fakespace (虚空)
看板java
标题Re: [问题] 判断点有无在区块内
时间Fri May 30 01:56:11 2008
※ 引述《elru8cjo4 (XD~猴~XD)》之铭言：
: 想请问一下
: A
: / \
: / \
: / ‧D \
: B/_______\C => 三角形 ; A,B,C,D 都是座标点
: 依此图
: 我要怎麽样去判断D这个点是不是在ABC三角形里面？？
: JAVA里面有内建的方法可以用吗？
: 因为会有很多个点,每个点都要判断
: 不知道有什麽好的演算法 > <
: 麻烦大家了 谢谢︿︿
我常会需要判断是否点在 N 边形里.
假设D的座标为(Dx,Dy)
找出 Y=Dy 这条线, 和那三角形的交点. 如果没交点, 在外面.
有两个交点, D的X座标介於那两个交点的X座标之间, 就是在里面. 不然就是在外面.
应用到多边形, 也是画一条 Y=Dy, 然後找出和所有边的交点, 照 X大小排序.
有奇数个交点的X座标大(或小於)於Dx, 那 D(Dx, Dy)就在在N边形里, 反之在外面.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.220.45
1F：推 tkcn:这招好像很好用! 05/30 13:40
2F：推 ClareQ:Java awt里内建的演算法也是这样实做的，不需要自己造轮子 05/31 22:15