Fast Algorithm for 2D bin packing with minimal distance each rectangle and a point

Question

This is similar to the bin packing problem, but with some changes.

What I have is a timeseries of annotated data, and when I draw the chart, I want to place the annotations in the position that overall minimizes distance from the annotated point.

This chart, (gratuitously stolen) shows what I'd like to do:.

I know this is an optimization problem, but I have no idea where to begin. What I was doing first, was placing it at the corresponding x, and moving up/down y to find a location that was available and save the area that has been drawn. While that worked, it doesn't really make best use of available space, and I'm wondering if there's something better.

I'm wondering if there's any known algorithms out there that attack this or similar problems?

Added note: It doesn't need to be optimal, but it absolutely needs to be fast. This is done during rendering, so the UI is blocked while this executes.

Answer 1

There are a wide range of approaches to this difficult problem. I'd suggest starting at the Wikipedia article on automatic label placement. You might also get some ideas from the realm of force-based algorithms for graph drawing.

Answer 2

I would do it like this- use a simple "first fit" algorithm and start with an arbitrary order for placing the labels. Score the result with something like the sum of the distance squared from each annotated point. I would do the distance squared to avoid having all of them be really close except for one that is a long ways away.

If your first solution is lower than some threshold, use it and move on. If it isn't, take the worst fits (i.e. the labels that are the farthest from the annotated point) and move them up in the placement order and start over. Iterate this until you either get a solution that is good enough or you run out of time, in which case you take the best solution of the lot and go with it.