线性排列算法 [英] Linear arrangement algorithm

问题描述

我不确定标题是否正确。

I am not sure if title is correct.

我有几个标签在y范围内设置了它们的位置：

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

range = [0, 100px]

<例如：5个位置标签：

for example: 5 labels in positions:

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

现在我希望我的算法纠正这些位置，让它们彼此之间的距离不要超过10px并进行最小的修正。

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]

这个alghoritm的名称是什么或如何实现？

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

推荐答案

这是一个算法，对于大多数情况应该可以很好地工作，并尝试ma ke作为原始值所需的最小调整量。

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. 遍历每对元素。


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 ]

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

请注意，此算法非常简单，并且对于具有大量紧密数字的真正复杂数组而言，可能无法始终产生最佳结果。例如，如果您输入 [33,34,35,36] ，则会得到 [19,29,40,50] ，这有额外的不必要空间。

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.

这篇关于线性排列算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！