4

尝试绘制饼图时遇到问题。 设计实例

当然，绘制图表没有问题，问题在于图标的放置。理想情况下，图标应该放在一个圆圈上（让我们暂时忘记百分比标签）。

但是，当存在具有较小值的相邻项时，设计显然会中断。

实现示例

你能推荐一个解决这个问题的算法吗？为简化起见，作为输入，我们有：
PIE_RADIUS- 饼图的外半径。
ICON_RADIUS- 图标圆的半径。
ICON_PLACEMENT_RADIUS- 理想放置图标中心时的圆的半径。
NUM_ICONS- 要放置的图标数量。
iconAngles每个图标的角度，位于其部分的中心

所需输出：对于放置在饼图周围的项目或
将图标移出理想圆圈时。iconAnglesiconPositions

我知道如何检查两个图标是否重叠。我们可以认为馅饼的中心在(0, 0)。

（实现是 iOS 应用程序的一部分，但我对一般算法感兴趣）。

4

3 回答 3

1

第一个朴素算法，我们“推送”与另一个图标重叠的图标：

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

使用第一个算法，一些图标将比其他图标离中心更远。但它并没有通过改变角度来利用可能的位置。通过将此应用于您的第二个设计（具有小值），很明显该解决方案将远离理想的解决方案。

第二个不那么天真的算法，首先我们为每个图标分配一个新的角度（差异小于 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 会导致运行时间过长。

为了更进一步，您应该查看力导向图形绘制算法，这是实现目标的更强大的方法，其中一个困难是找到节点的正确力（您的图标，您没有边缘）。

于 2013-04-03T15:10:34.227 回答
1

只是头脑风暴：

一种具有适应度函数的遗传算法，该算法对重叠具有较高的惩罚加上等于每个候选位置与其理想位置（相对于其切片居中）之间的角距离平方和的惩罚。

于 2013-04-03T18:17:18.407 回答
0

我实施的解决方案如下：

  1. 计算所有图标相对于其切片的位置（以 为中心的图标ICON_PLACEMENT_RADIUS）
  2. 查找重叠图标的序列（迭代图标并检查下一个是否与前一个重叠）。
  3. 计算两个图标之间的最小角距离（大约(2.0f * ICON_RADIUS + 1.0f) / ICON_PLACEMENT_RADIUS）
  4. 计算序列的中心（对序列的所有切片求和并找到中心），将图标放在一起（它们之间的距离是最小角距离）。
  5. 放置好所有图标后，检查图标是否重叠，如果是，则合并它们的序列并迭代。

请注意，此算法仅在所有图标数量与圆的大小相比都很小时才有效，但它简单且非常快。

结果是：
在此处输入图像描述

于 2013-04-03T18:45:00.067 回答