查找多邊形的最小邊數的算法

如何設計算法以找到位於兩個同心圓之間的多邊形的最小邊數？查找多邊形的最小邊數的算法

與此類似：

circles

來源

2012-11-12 sanky10987

你可以發佈一個鏈接到截圖來展示你的觀點嗎？ – nhahtdh

此外，最好詳細說明你已經完成的一些想法/努力 – fayyazkl

像這樣的東西 - http://cs.smith.edu/~orourke/MathOverflow/Annulus.jpg – sanky10987

首先想想最簡單的情況：內圈是微觀小的。只要內圓的半徑不爲零，最小邊數就是3。

多邊形何時開始需要四面？畫出一個刻在圓圈中的等邊三角形。當內圓的半徑達到三角形邊的中心點時，多邊形開始需要四條邊。

如果題n條邊的正多邊形到外圈，可以使用餘弦規則計算從各邊的中點，以該圓的中心的距離：

distance_to_midpoint = cos (360/(N * 2)) * radius_of_outer_circle

（說明：如果使用圓的中心點將圓形的等邊三角形繪製到所討論的邊上，則半徑的角度爲360/N。在邊的中點處將三角形分成兩半，形成直角三角形，其斜邊等於然後使用餘弦規則）

現在distance_to_midpoint需要大於o r爲r內圓的半徑，所以解決N：

radius_of_inner_circle = cos(360/(N * 2)) * radius_of_outer_circle 
cos(360/(N*2)) = radius_of_inner_circle/radius_of_outer_circle 
360/(N*2) = acos(radius_i/radius_o) 
N = 180/(acos(radius_i/radius_o))

（我還沒有仔細檢查了這道數學，它真的晚了）。

來源

2012-11-12 06:44:43

我也沒有檢查數學，我讓Mathematica去做，它也同意你的觀點。 –

畫出的切線內圓，標記A，B - 與外圈的切線的交叉點。
從B點向內圓畫一條切線（不同），標記與外圓C的交點。
重複步驟（2），直到新切線穿過第一個切線AB。

該算法將確保您覆蓋每個步驟的最大徑向截面，從而最小化生成的多邊形中的邊數。

如果您只想找到邊的數量，就足以找到來自外圓上同一點的內圓的2個切線之間的角度，並計算完整的360度有多少這樣的角度（加1如果有剩餘的話） - 像@cheeken在評論中建議的

來源

2012-11-12 06:33:40 SomeWittyUsername

謝謝。我認爲這聽起來不錯。 – sanky10987

表示多邊形的半徑，即多邊形外接圓的半徑，由R表示。內切圓的半徑是

r = R*Cos[180°/n]

解決這對n，消除雜散解決方案，給出了否定的結果，你有

n = 180°/ArcCos[r/R]

你必須擺弄一點得到一個整數值爲n，我會把它留給你。

來源

2012-11-12 06:46:34

查找多邊形的最小邊數的算法

回答

相關問題