饼图图标放置算法

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

只要头脑风暴：

的遗传算法使用具有用于重叠的高惩罚加上等于每个候选位置及其理想位置之间的角距离的平方之和的惩罚健身功能（相对中心到它的片段）。