作者windows2k (KERORO軍曹)
站內Prob_Solve
標題[討論] 凸多邊形最大內接圓
時間Sat Aug 11 12:14:38 2007
請問有甚麼好作法 @@
有種說法是可以把問題 reduce成求三角形內接圓, 不過不知道怎麼作
有誰可以提示一二的, 還是有別種作法也歡迎提出, 謝謝 :)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.130.43.109
1F：推 PsMonkey:[舉手] 凸「多」邊形一定會有內接圓嗎？ 08/11 14:10
2F：推 ckclark:也許不一定要每個邊都接到吧 08/11 14:31
3F：推 windows2k:二樓是正確的 08/11 15:06
4F：推 ephesians:長方形的確找不到內接圓;若修改問題為正凸邊形,也許還能 08/11 16:41
5F：→ ephesians:討論討論 08/11 16:42
6F：→ ephesians:另外有個問題是,凸多邊型會有二個以上內接圓嗎? 08/11 16:51
7F：推 windows2k:長方形一樣可以有內接圓, 不過可以只接三邊吧 08/11 17:11
8F：→ windows2k:還是我對內接圓的認知有錯誤 XD 08/11 17:11
9F：→ netsphere:若多邊形的每條邊都能與多邊形內部的一個圓形相切 08/11 18:12
10F：→ netsphere:該圓就是多邊形的內接圓 08/11 18:13
11F：→ netsphere:這不是我說的 是wiki說的(指) 08/11 18:13
12F：推 DJWS:這個名詞應該是「內切圓」而非「內接圓」吧 08/11 22:01
13F：→ DJWS:剛剛查了國立編譯館的學術名詞資訊網 08/11 22:18
14F：→ DJWS:發現incircle和inscribed circle都被翻譯做「內切圓」 08/11 22:19
15F：→ DJWS:我想w板友所說的應該是inscribed circle 而非incircle :) 08/11 22:20
16F：推 windows2k:ok, 是我表達錯誤, 不過回到原問題吧 :p 08/11 22:56
17F：→ DJWS:剛剛查了inscribed的定義...要接到每個邊才行 :~ 08/11 23:06
18F：推 ledia:要求最大的意思是內接圓可能會有很多個嗎? 08/12 16:57
19F：→ ledia:不然的話照定義, 不就有就是有, 沒有就是沒有? 08/12 16:57
20F：推 ephesians:定義上本來就說內切嘛,如果可以切一邊,不就無限多個? 08/12 17:15
21F：→ ephesians:如果這樣,名字一定也要改寫為最大內切圓 08/12 17:16
22F：→ ephesians:所以查到的說明:三角形一定有內切圓,多邊形不一定 08/12 17:17
23F：推 seanwu:似乎就是ACM 11257? 討論版上有神奇的做法 08/12 23:43
24F：→ seanwu:把每個邊往內縮h，當面積變成0時h就是半徑了 08/12 23:44
25F：推 yoco315:邊「往內縮」是什麼意思阿？ 08/13 01:55
26F：推 windows2k:往內縮那個作法我看不懂 :p 08/13 08:42
27F：推 seanwu:把每個邊保持平行地向內移動h 08/13 10:48
28F：推 windows2k:h怎麼算出來啊 @@ 08/13 12:13
29F：推 seanwu:好問題...二分搜尋? 08/13 12:22
30F：推 ephesians:內縮應該是說,以某中心點與每一邊所構成的三角形,都 08/14 21:50
31F：→ ephesians:每一邊都往中心方向平移...這方法不錯,但要先知道中心點 08/14 21:51
32F：→ ephesians:不過,這個中心點也就是想找的內切圓圓心,所以 XD 08/14 21:52
33F：→ ephesians:此外,內縮法做到靠近圓心的時候會振盪 08/14 21:53