Быстрый алгоритм для упаковки двухмерных бинов с минимальным расстоянием между каждым прямоугольником и точкой

Question

Это похоже на проблему упаковки бункера , но с некоторыми изменениями.

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

Этот график (безвозмездно украденный) показывает, что я хотел бы сделать: .

Я знаю, что это проблема оптимизации, но я не знаю, с чего начать. Сначала я поместил его в соответствующий x и переместился вверх / вниз по y, чтобы найти место, которое было доступно, и сохранить область, которая была нарисована. Несмотря на то, что это сработало, на самом деле оно не наилучшим образом использует доступное пространство, и мне интересно, есть ли что-нибудь лучше.

Мне интересно, есть ли какие-нибудь известные алгоритмы, которые атакуют эту или подобные проблемы?

Добавлено примечание: оно не должно быть оптимальным, но оно обязательно должно быть быстрым. Это делается во время рендеринга, поэтому пользовательский интерфейс блокируется во время выполнения.

Answer 1

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

Answer 2

Я бы сделал это так: используйте простой алгоритм «первого соответствия» и начните с произвольного порядка размещения меток.Получите результат, например, сумму квадрата расстояния от каждой аннотированной точки.Я сделал бы расстояние в квадрате, чтобы избежать того, чтобы все они были действительно близко, за исключением одного, который находится очень далеко.

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