作者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