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