Linear arrangement algorithm

Question

I am not sure if title is correct.

I have few labels which have set their positions in y scale in range:

range = [0, 100px]

for example: 5 labels in positions:

positions = [5px, 6px, 8px, 72px, 76px]

Now I want my algorithm to correct these positions to not let them be closer than 10px to each other and do minimal corrections.

I am expecting calling my function like this:

result = calculateNewPositions(range, positions, min(10px, 100px / positions.length))

and result in this case should be:

[0px, 10px, 20px, 69px, 79px]

What is name of this alghoritm or how to implement that?

Answer 1

Here's an algorithm that should work pretty well for most cases, and tries to make as minimal amount of adjustments as necessary from the original values.

1. Iterate through each pair of elements.
2. If the space is not large enough, move them apart from each other by 1, making sure not to violate the range.
3. Repeat until all the elements have enough space between them.

And here is a sample implementation:

function calculateNewPositions(positions, minSpacing, rangeMin, rangeMax) {
  var temp = positions.slice(0);
  var madeChange;
  do {
    madeChange = false;
    for (var i = 0; i < temp.length - 1; i++)
      if (temp[i + 1] - temp[i] < minSpacing) {
        if (temp[i] > rangeMin) { temp[i]--; madeChange = true; }
        if (temp[i + 1] < rangeMax) { temp[i + 1]++; madeChange = true; }
      }
  } while (madeChange);
  return temp;
}

Demo: https://jsfiddle.net/aaxmuw2t/

Example Result: [0, 10, 20, 69, 79]

Note that this algorithm is very simplistic and may not always yield the best result for really complex arrays with lots of close numbers. For example, if you input [33, 34, 35, 36], you get [19, 29, 40, 50], which has an extra unnecessary space.

Answer 2

calculateNewPositions = function(positions, minDelta) {
   var newPositions = [0]
   positions.slice(1).forEach(function(pos, index) {
     var delta = positions[index + 1] - positions[index]
     newPositions.push(newPositions[index] + Math.max(delta, minDelta))
   })
   return newPositions
}

https://tonicdev.com/lipp/pos-diff