| 算法問題的一個基本方法（修改版） |
| 送交者: 高玉寶 2012年07月04日11:02:26 於 [靈機一動] 發送悄悄話 |
|
A polygon, either convex or concave. A point, in the same plane of the polygon, either inside or outside the polygon. From this point, find a direction which cuts most sides of the polygon. 先算出點與多邊形各接點連線的角度，然後把多邊形各接點根據其角度從小到大 排列，然後從最小的那接點開始，依次檢查各接點。為了方便敘述，就稱角度小 的一方位左方，角度大的一方為右方。 設x為點與所檢查那接點的射線所經過的邊線數，m為點的射線能經過的最多射線 數，d為點的射線能經過的最多射線數的那方向，即角度（也就是要找的答案）。 d的初始值為角度最小的接點角度。x和m的初始值根據左邊第一接點的情況而定。 1。左邊第一接點的兩連線（每個接點有兩連線）的另一端全在射線的右邊，則設 x和m為2。 2。如全在射線的左邊，則設x和m為0。 3。一端在左一端在右，則設x和m為1。 然後檢查下面的各點（從第二接點開始），如 1。接點兩線的另一端全在右邊，則x加2。 2。全在左邊，則x減2。x減2後，如x小於0，則使x為0。 3。一端在左一端在右，如x是0，則使x為1，否則x不變。 然後比較m和x。如x大於m，則使m=x，使d為這接點的角度。 這樣每個點都檢查下來後，d（稍偏右一點）就是所要的結果。 |
|
|
|
|
 |
 |
| 實用資訊 | |
