Алгоритм размещения пиктограммы диаграммы

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) для каждого значка, то мы применяем первый 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 

выбирать мудро deltaAngle и DeltaAngleMax. Слишком мало deltaAngle приведет к большому времени работы.

Чтобы идти дальше, вы должны взглянуть на алгоритм the force-directed graph drawing, который является гораздо более надежным методом для достижения вашей цели. Одна из трудностей состоит в том, чтобы найти правильные силы узлов (ваши значки, у вас нет границ).

Answer 3

Только мозговой штурм:

Генетический алгоритм с фитнес-функцией, которая имеет высокий штраф за наложения плюс штраф, равной сумму квадратов угловых расстояний между каждым кандидатом местоположением и его идеальным расположением (в центре по отношению на его срез).