Re: [幾何] 求圓裡面包含n個單位圓的半徑

[bugmens (2013新年快樂)]

※ 引述《flymath (flymath)》之銘言：
: 想請問一下
: 一個最小圓內部若能包含3個單位圓的情形：就是三圓兩兩相切(圓心連線是正三角形).
:                                                             大圓再外切
:                   4個單位圓            四圓兩兩相切(圓心連線是正方形)
:                      .
:                      .
:                      .
:                   7個單位圓         圓心連線是正六邊形.中間再放一個圓 ●●
:                                                                      ●●●
:                                                                       ●●
:                   所以我以為只要圓心連線是正多邊形即可
: 但是要放入10個單位圓好像就沒有規律性了(不是圓心連線是正九邊形.中間再放一個圓)
: 請問各位前輩
: 這種幾何問題能解決嗎??
: 感謝
數個半徑為1的小圓至少要多少半徑的大圓才能將小圓裝進去
http://en.wikipedia.org/wiki/Circle_packing_in_a_circle
連結有論文可以看

我自己則是用LibreOffice的非線性規劃解正方形中裝入數個小圓的問題
設定限制條件,目標函數後就讓軟體跑出可行解出來
http://i.imgur.com/MN3VOpn.gif
http://i.imgur.com/EZq2kFE.gif

相關內容請google   circle packing

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.164.223.90
推 flymath     :感謝^^....可以請問一下您使用非線性規劃的方法嗎
假設變數
    小圓圓心(x1,y1),(x2,y2),(x3,y3)
    小圓半徑1
    大圓圓心(0,0)
    大圓半徑R

限制條件
                       2        2
    小圓彼此外切(x1-x2) +(y1-y2) >= 4
                       2        2
                (x2-x3) +(y2-y3) >= 4
                       2        2
                (x3-x1) +(y3-y1) >= 4
    小圓落在大圓裡面
                      2        2       2
                (x1-0)  +(y1-0) <=(R-1)
                      2        2       2
                (x2-0)  +(y2-0) <=(R-1)
                      2        2       2
                (x3-0)  +(y3-0) <=(R-1)

目標函數
    求大圓半徑R的最小值


因為限制條件有平方所以此類問題不能用一般的線性規劃解題
幸好LibreOffice有提供非線性規劃的功能
http://i.imgur.com/MN3VOpn.gif
按下左下角"選項"按鈕,選擇"DEPS"
目標儲存格: 大圓半徑
將結果最佳化為: 最小
藉由更動儲存格: 小圓圓心坐標,大圓半徑
儲存格參照: 小圓彼此外切
            小圓落在大圓裡面
按下右下角"解決"按鈕


關於Calc的非線性規劃介紹
http://extensions.services.openoffice.org/project/NLPSolver
http://wiki.openoffice.org/wiki/NLPSolver
※ 編輯: bugmens         來自: 203.64.46.72         (03/06 11:45)