每個 polygon 會遮蔽其中一段連續的點
所以只要找出遮蔽的範圍就好做了
我的做法是先對每個 polygon 的頂點做極角排序
由於那些頂點會縮在 180o 的範圍內, 用cross product就可以找出紅色那兩點
由於不想handle precision, 我所有計算都用哂 integer
之後麻煩在要找出射線和 boarder 的交點
經過一輪數學運算, 終於截到式
有個tricky的位, 就係「開始遮蔽點」和「結束遮蔽點」做除法一個是 round up 和 round off
最後一個bug就係我無handle到有些障礙物一個點都無遮到
No comments:
Post a Comment