javascript - 线性排列算法

Question

我不确定标题是否正确。

我几乎没有在 y 范围内设置位置的标签:

range = [0, 100px]

例如:5个标签的位置:

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

现在我希望我的算法修正这些位置，使它们彼此之间的距离不超过 10 像素，并进行最少的修正。

我期待这样调用我的函数:

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

在这种情况下，结果应该是:

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

这个算法的名称是什么或如何实现它？

Answer 1

这里的算法在大多数情况下应该都能很好地工作，并会尝试对原始值进行尽可能少的必要调整。

1. 遍历每对元素。
2. 如果空间不够大，将它们彼此分开 1，确保不要超出范围。
3. 重复，直到所有元素之间都有足够的空间。

这是一个示例实现:

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;
}

演示:https://jsfiddle.net/aaxmuw2t/

示例结果:[0, 10, 20, 69, 79]

请注意，此算法非常简单，对于具有大量接近数字的非常复杂的数组，可能并不总能产生最佳结果。例如，如果您输入 [33, 34, 35, 36]，您将得到 [19, 29, 40, 50]，其中有多余的空格。