I need an algorithm to place horizontal text labels for multiple series of points on the screen (basically I need to show timestamps and other information for a history of moving objects on a map; in general there are multiple data points per object). The text labels should appear close to their points–above, below, or on the right side–but should not overlap other points or text labels.
Does anyone know an algorithm/heuristic for this?
1
It may come as a surprise to you that (if you want to ensure that none of the labels overlap) the problem you describe is NP-hard. On the other hand, many approximation algorithms have been devised that are perfectly useful in practice. It really depends on how difficult your specific constraints are. (Disclaimer: I wrote my Master’s thesis on the subject — available here — so I’m probably exactly the wrong person to ask!) As always, Wikipedia and Google are good starting points. And if you’re really a glutton, an exhausting (though not exhaustive) list of papers on the subject can be found here.
3