算法問題的一個基本方法 |
送交者: 高玉寶 2012年07月03日06:25:57 於 [靈機一動] 發送悄悄話 |
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為0,m為-10 如接點兩線的另一端全在後面,則x加2,全在前面則x減2。然後比較m和x,如x大於m,則使m=x,記下這個角度d(即方向)。這樣每個點都檢查下來後,d就是所要的結果。 |
|
|
|
實用資訊 | |