Pie chart icon placing algorithm

4
votes

I have a problem when trying to draw a pie chart. Design example

Of course, there is no problem with drawing the chart, the problem is the icon placement. Ideally, the icons should be placed on a circle (let's forget the percent labels for now).

However, the design obviously breaks when there are neighbor items with small values.

Implementation example

Could you recommend an algorithm solving this issue? To simplify, as input we have:
PIE_RADIUS - The outer radius of the pie.
ICON_RADIUS - The radius of the icon circle.
ICON_PLACEMENT_RADIUS - The radius of the circle when icon center should be ideally placed.
NUM_ICONS - Number of icons to place.
iconAngles Angle for every icon, in the center of its section

Required output:
Either iconAngles for items placed around the pie or iconPositions when moving the icons out of their ideal circle.

I know how to check whether two icons overlap. We can consider the center of the pie to be at (0, 0).

(The implementation is part of an iOS application but I am interested in a general algorihm).

3
algorithmpie-chartlabels

3 Answers

1
votes

A first naive algorithm , we "push" the icons that overlap with an other icon: 

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

With this first algorithm some icons will be futher from the center than other. But it does not exploit the possible place by changing the angle. By applying this to your second design (with small values) it is clear that the solution will be far away from the ideal one.

A second less naive algorithm, first we allocate a new angle (difference less than DeltaAngleMax) for each icon then we apply the first algo:

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

Choose wisely deltaAngle and DeltaAngleMax. A too little deltaAngle will lead to a big running time.

To go further you should have a look at the force-directed graph drawing algorithm which is much more robust method to achieve your goal, one of the difficulty is to find the correct forces of the nodes (your icons, you have no edges).

1
votes

Just brainstorming:

A genetic algorithm with a fitness function that has a high penalty for overlaps plus a penalty equal to the sum of the squares of the angular distances between each candidate location and its ideal location (centered relative to its slice).

0
votes

The solution I implemented was the following:

  1. Calculate the position for all the icons relative to their slice (icon centered on ICON_PLACEMENT_RADIUS)
  2. Find sequences of overlapping icons (iterate the icons and check if the next is overlapping with the previous).
  3. Calculate the minimum angular distance between two icons (approximately (2.0f * ICON_RADIUS + 1.0f) / ICON_PLACEMENT_RADIUS)
  4. Calculate the center of the sequence (sum all the slices for the sequence and find the center), place the icons together (distance between them is the minimum angular distance).
  5. When all icons placed, check if icons overlap, if yes, merge their sequences and iterate.

Note this algorithm works only if all the number of icons is small comparing to the size of the circle but it's simple and very fast.

The result is:
enter image description here