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

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

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

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

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

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

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

5
задан Reverend Gonzo 19 January 2012 в 19:22
поделиться