Linear Algorithm

Question

I'm not sure the name is correct.

I have several labels that have set their positions on the y scale in the range:

range = [0, 100px] 

for example: 5 marks in positions:

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

Now I want my algorithm to correct these positions so that they are not closer than 10px to each other and perform minimal corrections.

I expect to call my function as follows:

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

and the result in this case should be:

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

What is the name of this algorithm or how to implement it?

Answer 1

Here is an algorithm that should work very well for most cases, and tries to make as little as possible minimal adjustments from the original values.

• Iterate through each pair of elements.
• If the space is not large enough, separate them from each other by 1, making sure that this does not violate the range.
• Repeat until all items have enough space between them.

And here is an example 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]

Please note that this algorithm is very simplified and may not always give the best result for really complex arrays with a lot of close numbers. For example, if you enter [33, 34, 35, 36] , you will get [19, 29, 40, 50] , which has 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

Answer 3

Finally, I did something like this:

 var fixPositions = function(range, pos, delta, strict) { var i; var leftSpaces = []; var halfDelta = strict ? delta / 2 : 0; delta = Math.min(delta, (range[1] - range[0] / (pos.length + (strict ? 0 : 1)))); // calculate all spaces that are greater than delta leftSpaces.push(Math.max(pos[0] - range[0] - halfDelta, 0)); for (i = 1; i < pos.length; i++) { leftSpaces.push(Math.max(pos[i] - pos[i-1] - delta, 0)); } leftSpaces.push(Math.max(range[1] - pos[pos.length-1] - halfDelta, 0)); // save indexes of big spaces var nonZeroSpacesIdx = []; leftSpaces.map(function(space, i) { if (space > 0) { nonZeroSpacesIdx.push(i); } }); // sort indexes by spaces sizes (start from smaller) nonZeroSpacesIdx.sort(function(a, b) { return leftSpaces[a] - leftSpaces[b]; }); // loop until spaces sum are greater than range var spacesSum = Infinity; while (nonZeroSpacesIdx.length > 0 && spacesSum > 0) { spacesSum = 0; for (i = 0; i < nonZeroSpacesIdx.length; i++) { spacesSum += leftSpaces[nonZeroSpacesIdx[i]]; } var missingDiff = (spacesSum + (pos.length - 1) * delta + halfDelta * 2) - (range[1] - range[0]); if (missingDiff <= 0) { break; } // find min diff which can be substracted from all spaces var minDiff = Math.min(missingDiff / nonZeroSpacesIdx.length, leftSpaces[nonZeroSpacesIdx[0]]); for (i = 0; i < nonZeroSpacesIdx.length; i++) { leftSpaces[nonZeroSpacesIdx[i]] -= minDiff; } // remove index of first space if its equal zero if (leftSpaces[nonZeroSpacesIdx[0]] <= 0) { nonZeroSpacesIdx.shift(); } } // reconstruct new positions var newPos = []; newPos.push(range[0] + leftSpaces[0] + halfDelta); for (i = 1; i < leftSpaces.length - 1; i++) { newPos[i] = newPos[i-1] + leftSpaces[i] + delta; } return newPos; }; // result should be from range: [5, 95] console.log(fixPositions([0, 100], [5, 6, 8, 72, 76], 10, true)); // result should be from range: [0, 100] console.log(fixPositions([0, 100], [5, 6, 8, 72, 76], 10, false)); 

https://jsfiddle.net/fcwu1oyu/14/

It does not give exact values ​​for my input, but it does the job for my pie charts:

Answer 4

Work solution

The code pushes two pairs too close on one side. This is symmetrical and sometimes leads to far shifted values ​​that can be corrected.

 function disperse(values, threshold, range) { var delta = Array.apply(null, { length: values.length }).map(function () { return 0; }), converged = false; while (!converged) { converged = true; delta = delta.map(function (d, i, dd) { if (i < dd.length - 1 && dd.length > 1 && values[i + 1] + dd[i + 1] - values[i] - d < threshold) { converged = false; dd[i + 1] += 1; return d - 1; } return d; }); } converged = false; // try to minimise difference while (!converged) { converged = true; delta = delta.map(function (d, i) { var space; if (i < delta.length - 2) { space = values[i + 1] + delta[i + 1] - values[i] - d; if (d < 0 && space > threshold) { converged = false; return d + space - threshold; } } return d; }); } // respect lower range delta.reduce(function (r, d, i, dd) { if (values[i] + d < r) { dd[i] = r - values[i]; return r + threshold; } return values[i] + threshold + d; }, range[0]); // respect upper range delta.reduceRight(function (r, d, i, dd) { if (values[i] + d > r) { dd[i] = r - values[i]; return r - threshold; } return values[i] + d; }, range[1]); return values.map(function (v, i) { return v + delta[i]; }); } document.write('<pre>' + JSON.stringify(disperse([5, 6, 8, 72, 76], 10, [0, 100]), 0, 4) + '</pre>'); document.write('<pre>' + JSON.stringify(disperse([5, 6, 7, 8, 72, 76], 10, [0, 100]), 0, 4) + '</pre>'); document.write('<pre>' + JSON.stringify(disperse([24, 28, 92, 94, 95], 10, [0, 100]), 0, 4) + '</pre>');