餅圖圖標放置算法

Question

嘗試繪製餅圖時出現問題。

當然，繪製圖表沒有問題，問題在於圖標的放置。 理想情況下，圖標應放置在一個圓上（讓我們暫時忘記百分比標籤）。

然而，當有相鄰項目的值很小時，設計顯然會中斷。

您建議的算法解決這一問題？爲了簡化，作爲輸入，我們有：
PIE_RADIUS - 餡餅的外半徑。
ICON_RADIUS - 圖標圓的半徑。
ICON_PLACEMENT_RADIUS - 圖標中心應放在理想位置時的圓的半徑。
NUM_ICONS - 放置圖標的數量。
iconAngles角度爲每個圖標，在其截面中心

需要的輸出：
要麼iconAngles用於移動圖標，把自己的理想圓的時候周圍放置餡餅或iconPositions項目。

我知道如何檢查兩個圖標是否重疊。 我們可以認爲餡餅的中心位於(0, 0)。

（該實現是iOS應用程序的一部分，但我對通用算法感興趣）。

Answer 1

我實現該解決方案是以下內容：

1. 計算位置對於所有相對於它們的切片（圖標中心ICON_PLACEMENT_RADIUS）
2. 查找重疊的圖標（迭代的圖標，並檢查的序列的圖標下一個與前一個重疊）。
3. 計算兩個圖標（約(2.0f * ICON_RADIUS + 1.0f)/ICON_PLACEMENT_RADIUS）
4. 計算序列的中心（總結所有片的序列並找到中心）之間的最小的角距離，圖標放置在一起（在它們之間的距離是最小的角距離）。
5. 放置所有圖標時，檢查圖標是否重疊，如果是，則合併它們的序列並重復。

注意這個算法只能如果所有圖標的數量是比較小的圈子的大小，但它的簡單和速度非常快。

結果是：

Answer 2

頭一個幼稚的算法，我們以「推」與另一圖標重疊圖標：

FOR iconToPlace in icons do: 
    isPlaced = false 

    WHILE(not isPlaced) DO: 
     isPlaced = true 
     FOR icon in icons DO: 
      IF overlap(iconToPlace, icon) AND iconToPlace != icon THEN: 
       isPlaced = false 
       push(iconToPlace) // same angle but the icon is now further 
       BREAK 
      ENDIF 
     ENDFOR 
    ENDWHILE 

ENDFOR 

有了這個第一算法一些圖標會futher從中心以外。但它沒有通過改變角度來利用可能的地方。通過將其應用於第二個設計（具有較小的值），顯然該解決方案將遠離理想的解決方案。

第二少幼稚算法中，首先我們分配一個新的角度（大於DeltaAngleMax差更小）的每個圖標，然後我們應用第一算法中：

icons = SORT(icons) 
iconsRef = icons 
isFinished = false 
WHILE(not isFinished) DO: 
    isFinished = true 
    FOR i = 0 TO i = NUM_ICONS-1 DO: 
     IF overlap(icons(i), icons(i+1 % NUM_ICONS)) 
     AND not overlap(icons(i), icons(i-1 % NUM_ICONS)) //seems useless 
     AND not overlap(icons(i)-DeltaAngle % 360, icons(i-1 % NUM_ICONS)) 
     AND ABS(icons(i)-iconsRef(i)) <= DeltaAngleMax THEN: 
      //overlap with next icon but not with previous, 
      //if we decrease angle we still not overlap with previous icon and 
      //the futur delta angle is less than DeltaAngleMax 
      //then we can move the icon : 
      icons(i) = icons(i)-DeltaAngle 
      isFinished = false 
     ELSE IF overlap(icons(i), icons(i-1 % NUM_ICONS)) 
     AND not overlap(icons(i), icons(i+1 % NUM_ICONS)) //seems useless 
     AND not overlap(icons(i)+DeltaAngle % 360, icons(i+1 % NUM_ICONS)) 
     AND ABS(icons(i)-iconsRef(i)) <= DeltaAngleMax THEN: 
      //vice et versa: 
      icons(i) = icons(i)+DeltaAngle 
      isFinished = false 
    ENDFOR 
ENDWHILE 

APPLY_FIRST_ALGO 

明智地選擇deltaAngle和DeltaAngleMax。太少的deltaAngle會導致很大的運行時間。

要走得更遠，你應該看看the force-directed graph drawing算法，這是更健壯的方法來實現你的目標，其中一個難點是找到節點的正確力量（你的圖標，你沒有邊緣）。

Answer 3

只要頭腦風暴：

的遺傳算法使用具有用於重疊的高懲罰加上等於每個候選位置及其理想位置之間的角距離的平方之和的懲罰健身功能（相對中心到它的片段）。