Space a series of values so they don't overlap

Question

There have been a couple of questions very close to this topic, but none really helped me.

Ive been programming a graphing library, and I need an algorithm to vertically place labels without overlapping. I've been stuck on this for a couple of days now, and managed to distil it to the most basic function:

If given a series of label positions along the Y axis, say, 1 1 2 3 5 6 9, and an upper and a lower limits 10 and 0 respectively, I need a way to space out the values to output 1 2 3 4 5 6 9

333467 should be 234567 weighted to be close to the original coordinates.

This should also work backwards, if values are bunched up at the upper end of the scale, they should be spread as much as possible (before overflowing)

I'm not looking for a definitive answer, but I'd like some help on how to approach this problem. Im completely stuck.

Last train of thought was to scan all labels for possible collisions and position them as one big block, aligning to the centre of all the Y coordinates. But this will not work if there are multiple sets of collisions.

EDIT: To put this algorithm in a bigger context, have a look at these two google chart API pie charts:

1) Top stacked labels

2) Bottom Stacked Labels

The labels are almost springy, they avoid collisions by joining together and moving their entire mass to the center of their mass.

Answer 1

Well, After some thought and advice from other sources i came up with a solution:

Pseudocode:

foreach labels as label
    if label->collidesWith(labels->lowerLimit)
        label->moveAwayFrom(labels->lowerLimit)

    if label->collidesWith(labels->upperLimit)
        label->moveAwayFrom(labels->upperLimit)

    if label->collidesWith(label->previous)
        label->moveAwayFrom(label->previous)
        label->previous->moveAwayFrom(label)

    if label->collidesWith(label->next)
        label->moveAwayFrom(label->next)
        label->next->moveAwayFrom(label)
endforeach

MoveAwayFrom moves 1 pixel at a time. When this function is run multiple times it rejiggles the labels until none of them collide. (in reality im calling this loop 100 times, havent figured out a way to do it more inteligently)

Answer 2

Make the set of labels unique by inserting into an ordered set. Divide the difference between the y-axis upper and lower bound by the number of elements in the set. This is your spacing increment. Iterate over the set in order and position one label every spacing increment.

You didn't say anything about needing to preserve a scale...