Chart Icon Placement Algorithm

Question

I have a problem while trying to draw a pie chart.

Of course, there is no problem drawing a chart; the problem is placing the icons. Ideally, the icons should be placed on the circle (let's forget the percentage marks at the moment).

However, the design clearly breaks when there are adjacent elements with small values.

Could you recommend an algorithm to solve this problem? To simplify, we have as input:
PIE_RADIUS - The outer radius of the pie.
ICON_RADIUS - The radius of the circle of icons.
ICON_PLACEMENT_RADIUS - The radius of the circle when the center of the icons should be ideally located.
NUM_ICONS - number of icons to place.
iconAngles The angle for each icon, in the center of its section

Required Conclusion:
Either iconAngles for items around the cake, or iconPositions when moving icons from their perfect circle.

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

(The implementation is part of the iOS application, but I'm interested in the general algorithm).

Answer 1

I implemented the following solution:

• Calculate the position for all icons relative to their slice (icon centered in ICON_PLACEMENT_RADIUS )
• Find the sequences of overlapping icons (iterating the icons and checking if the next one matches the previous one).
• Calculate the minimum angular distance between two icons (approximately (2.0f * ICON_RADIUS + 1.0f) / ICON_PLACEMENT_RADIUS )
• Calculate the center of the sequence (sum all the fragments of the sequence and find the center), place the icons together (the distance between them is the minimum angular distance).
• When all the icons are placed, check if the icons overlap, if so, merge their sequences and iterate.

Please note that this algorithm only works if the entire number of icons is small compared to the size of the circle, but it is simple and very fast.

Result:

Answer 2

The first naive algorithm, we “click” icons that overlap with another 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 farther from the center than others. But he does not use the possible place by changing the angle. Applying this to the second project (with small values), it is clear that the solution will be far from ideal.

The second less naive algorithm, first we select a new angle (the difference is less than DeltaAngleMax) for each icon, then we apply the first algorithm:

 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. Too little deltaAngle will lead to a long run time.

To go further, you need to look at the drawing algorithm using a directional graph , which is a much more reliable method to achieve your goal, one difficulty is finding the correct node strengths (your icons, you have no boundaries).

Answer 3

Just a brainstorm:

A genetic algorithm with a suitability function that has a high overlap penalty plus a penalty equal to the sum of the squared angular distances between each candidate’s location and its ideal location (centered relative to its slice).