作者seanwu (Blindest)
站內Prob_Solve
標題Re: [討論] 凸多邊形最大內接圓
時間Fri Aug 17 23:20:29 2007
1F：→ seanwu:把每個邊往內縮h，當面積變成0時h就是半徑了 08/12 23:44
2F：推 yoco315:邊「往內縮」是什麼意思阿？ 08/13 01:55
3F：推 windows2k:往內縮那個作法我看不懂 :p 08/13 08:42
4F：推 seanwu:把每個邊保持平行地向內移動h 08/13 10:48
5F：推 windows2k:h怎麼算出來啊 @@ 08/13 12:13
6F：推 seanwu:好問題...二分搜尋? 08/13 12:22
嗯，提一個做法
將邊往內縮時，一個邊的兩個相鄰邊會往中間夾過來，最後把中間的邊吃掉
持續的內縮，早晚會有一個邊會最先被吃掉，至於每個邊縮多少時會被吃掉，
是可以算得出來的，而擁有最小值的邊就是最先被吃掉的邊
於是在收縮了這個最小值，某個邊被吃掉後，原本的N邊形會變成N-1邊形
(當然會有例外啦..可能有額外的邊也剛好被吃掉了)
遞歸做下去就可以了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 203.68.21.146
7F：推 ephesians:非正多邊形也能這樣做嗎? 08/18 00:47
8F：推 windows2k:收縮多少怎麼算啊 08/18 10:04
9F：推 DJWS:請問大家可以提供一下內縮法的詳細資料嗎？想要好好研究一下~ 08/18 17:13
10F：推 seanwu:非正多邊形當然也可以XD 不然就沒意思了 08/18 22:34
11F：→ seanwu:至於每次收縮的值...可以對每個角做角平分線 08/18 22:34
12F：→ seanwu:一個邊的兩角之平分線交點到該邊的距離 08/18 22:36
13F：→ seanwu:就是那個邊會被吃掉的距離了，找有最小值的邊，以該值收縮 08/18 22:37