algorithm - 饼图图标放置算法

Question

我在尝试绘制饼图时遇到问题。

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

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

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

要求的输出:
iconAngles 用于放置在饼图周围的项目，或者 iconPositions 将图标移出理想的圆圈。

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

(该实现是 iOS 应用程序的一部分，但我对通用算法感兴趣)。

Answer 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 太小会导致运行时间过长。

要更进一步，您应该看看 the force-directed graph drawing算法是实现目标的更强大的方法，困难之一是找到正确的节点力(你的图标，你没有边缘)。