Я бы хотел автоматически помещать метки 200-200 пузырьков, чтобы выполнялись следующие требования:
Есть ли полезные библиотеки/алгоритмы для этого? (желательно JavaScript или PHP)
(Размещение меток на изображении не отвечает этим требованиям)
Это можно сформулировать как задачу линейного программирования. Вы хотите максимизировать или минимизировать функцию (представляющую "вес" или "доброту" решения) при определенных ограничениях (ваши требования). Вам нужно будет формализовать ваши требования в качестве значений. Что-то вроде этого:
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 больше всего взвешен, поэтому он "наиболее важен". Ограничения - это жесткие ограничения, которые не могут быть нарушены.
Так как это хорошо известная проблема, вы можете решить ее с помощью ряда методов. Алгоритм Simplex популярен. Существует целая глава в Cormen et. al об этих проблемах.
Как насчет этого?
Я предполагаю, что вы работаете с javascript, html и css? Ну и в любом случае приходят в голову два подхода.
Сначала нужно сформулировать его как проблему оптимизации. Вам нужно вычислить идеальное положение для каждой метки. Это будет основано на размере пузырька, желаемом месте (то есть сверху, вниз, влево, вправо) и размере метки (как шрифта, так и длины). Затем вам нужно параметризовать ваши координаты, например, в список из 2N элементов, где N - количество меток. Затем вам нужно инициализировать метки в некотором положении (или популяции при использовании генетического алгоритма) и применить алгоритм оптимизации, который потребует функции стоимости. Это будет зависеть от того, насколько далеко от позиции идеала установлен набор позиций ярлыков, а также все, что нарушает ваши правила, например, перекрытие.
Или, сделайте это проблемой физики. "Прикрепите" каждую метку к ее пузырю с помощью какой-то жесткой ссылки. Дайте каждой этикетке и каждому пузырю отталкивающую силу, а также добавьте глобальную и сильную гравитационную силу (в предпочтительном направлении вверх/влево/вправо/вниз). Имейте короткое физическое моделирование, пока не достигнете равновесия. Математика не должна быть слишком сложной.
Я думаю, что если вы используете D3 внутри своих инструментов, вы можете использовать алгоритм размещения меток на основе силы. Решение изначально принадлежит Max Planck Research Networks, но уже есть готовый пример Javascript, здесь: Ярлык, основанный на силе размещение в D3
Возможно, играйте с некоторыми вспомогательными инструментами, такими как:
К сожалению, я думаю, будет сложно найти это решение, легко доступное в Javascript или PHP. Но, я думаю, ваша проблема может быть разбита на небольшие под-проблемы (на основе ваших правил), чтобы помочь вам разработать свое решение.
Я бы определил, какие из ваших правил наиболее важны. Из взглядов представленного вами графика я бы сказал, что правило №1 и №2 обеспечит наибольшее улучшение удобочитаемости.
Чтобы определить размещение в соответствии с этими правилами, я бы вычислил граничные контейнеры текста и пузырьков и проверил пересечение. При пересечении перейдите в местоположение без пересечения. Если вы не можете найти, используйте пространство с минимальным перекрытием.
Это позволит вам также создать эвристику взвешенного места размещения для левого верхнего и нижнего правого и т.д., чтобы помещать метки в "предпочтительные" местоположения.
Я бы попытался написать небольшой фрагмент алгоритма размещения, используя два пузырька с двумя метками, которые обычно близки и могут накладываться друг на друга. Если вы можете обобщить свой алгоритм размещения для работы с этим небольшим подмножеством, вы должны хорошо двигаться вперед с большим количеством пузырьков.
Кроме того, возможно, вы могли бы использовать что-то по порядку kd-дерева или другого пространства, разбивающего структуру данных, чтобы найти ближайших соседей, чтобы избежать.
Я нашел подход в Java на самом деле для этой проблемы, которая на самом деле работает и называется Force Directed Map Labeling и является академическим опытом с открытым исходным кодом.
Вот документация + исходный код проекта: Принудительная привязка к карте
Как насчет
label.substring(0, Math.sqrt(bubbleValueOrRadius))
Я нашел это в одном из примеров protovis.js.
Этот поток очень хорош в освещении некоторых подходов. Я использую макет силы с несколькими фокусами, поскольку он кажется лучшим общим методом.