Алгоритм размещения меток пузырьковой диаграммы?(желательно в JavaScript)

Question

Я бы хотел автоматически разместить 100-200 пузырьковых меток, чтобы были выполнены следующие требования:

• Ярлыки не должны перекрываться
• Этикетки предпочтительно не должны перекрывать пузырьки
• Метка должна быть близка к пузырю
• Предпочтительное положение этикетки (вверху слева, сверху, снизу, справа и т. Д.) Должно соблюдаться в некоторой степени
• Размер шрифта может варьироваться

Есть ли полезные библиотеки / алгоритмы для этого? (желательно JavaScript или PHP)

(размещение этикетки на изображении не соответствует этим требованиям)

Answer 1

Как насчет этого?

Эффективный алгоритм для маркировки точечной диаграммы

Answer 2

Я думаю, что если вы используете D3 в своих инструментах, вы можете использовать «силовой» алгоритм размещения меток. Решение изначально принадлежит Max Planck Research Networks , но уже есть готовый пример Javascript, здесь: Размещение меток на основе силы в D3

Answer 3

Я полагаю, вы работаете с Javascript, HTML и CSS?Ну, в любом случае на ум приходят два подхода.

Сначала сформулируем это как проблему оптимизации.Вам необходимо рассчитать идеальную позицию для каждого ярлыка.Это будет основано на размере пузыря, желаемом месте (то есть сверху, внизу, слева, справа) и размере метки (как шрифта, так и длины).Затем вам нужно параметризовать ваши координаты, например, в список из 2N элементов, где N - количество меток.Затем вам нужно инициализировать метки в некоторой позиции (или популяции, если используется генетический алгоритм) и применить алгоритм оптимизации, который потребует функции стоимости.Это будет зависеть от того, насколько далеко набор позиций меток от идеального, а также от всего, что нарушает ваши правила, например от наложения.

Или, сделайте это проблемой физики.«Прикрепите» каждый ярлык к пузырю с помощью жесткой связи.Придайте каждой метке и каждому пузырьку отталкивающую силу, а также добавьте глобальную и более сильную гравитационную силу (в предпочтительном направлении сверху / слева / справа / вниз).Проведите короткое физическое моделирование, пока не достигнете равновесия.Математика не должна быть слишком сложной.

Answer 4

Это можно сформулировать как задачу линейного программирования.Вы хотите максимизировать или минимизировать функцию (представляющую «вес» или «добротность» решения) с учетом определенных ограничений (ваших требований).Вам нужно будет оформить ваши требования как ценности.Примерно так:

Variables:
x1 = 1 if Labels overlap, 0 otherwise
x2 = some measure of "how much" a label overlaps a bubble
x3 = distance from label to bubble //Label should be close to bubble
x4 = distance between ideal and actual label position
x5 = difference between actual and ideal font size


minimize x1 + 10*x2 + x3 + 20*x4 + 5*x5

subject to constraints:
    x1   = 0  // labels can never overlap
    x2   < /* maximum amount a label is allowed to overlap a bubble */
    ...
    x5   < 6 // font size does not vary by more than +/- 6 pts.

Я составил коэффициенты и ограничения, вы можете использовать их для настройки результата в зависимости от того, какие функции наиболее важны для вас.Коэффициенты увеличивают значение требования (в этом случае f4 является наиболее взвешенным, поэтому оно «наиболее важно». Ограничения - это жесткие ограничения, которые не могут быть нарушены.

Поскольку это хорошо известная проблема,теперь вы можете решить ее, используя ряд методов. Алгоритм Симплекс популярен. В Cormen et. al есть целая глава об этих проблемах.

Answer 5

Возможно, поиграйте с некоторыми вспомогательными инструментами, такими как:

• protovis
• d3

Answer 6

Я нашел подход в Java на самом деле для этой проблемы, который на самом деле работает и называется Force Directed Map Labeling и является опытом академии с открытым исходным кодом.

Вот документация + исходный код проекта: Маркировка силы направленной карты

Answer 7

К сожалению, я думаю, что будет трудно найти это решение легкодоступным в Javascript или PHP. Но я думаю, что ваша проблема может быть разбита на небольшие подзадачи (основанные на ваших правилах), чтобы помочь вам разработать свое решение.

Я бы определил, какие из ваших правил наиболее важны. Судя по представленному вами графику, я бы сказал, что правила № 1 и № 2 обеспечат максимальное улучшение читаемости.

Чтобы определить размещение по этим правилам, я бы вычислил граничные контейнеры с текстом и пузырьками и проверил на пересечение. На перекрестке переместитесь в место без пересечения. Если не удается найти, используйте пробел с минимальным перекрытием.

Это позволит вам также создать эвристику взвешенного размещения для верхнего левого, нижнего правого и т. Д., Чтобы помочь разместить метки в «предпочтительных» местах.

Я бы попытался написать небольшой фрагмент алгоритма размещения, используя два пузырька с двумя метками, которые обычно близки и потенциально могут перекрываться. Если вы можете обобщить алгоритм размещения для работы с этим небольшим подмножеством, вы должны хорошо продвигаться вперед с большим количеством пузырьков.

Кроме того, возможно, вы могли бы использовать что-то в порядке kd-дерева или другой структуры данных разделения пространства, чтобы найти ближайших соседей, которых следует избегать.

Answer 8

Эта тема очень хороша в освещении некоторых подходов. Я использую макет силы с несколькими фокусами, так как это кажется наилучшим общим методом.

Answer 9

Как насчет

label.substring (0, Math.sqrt (bubbleValueOrRadius))

Я нашел это в одном из примеров protovis.js.