将角度分配，使连续的角度之间最远

Question

我正试图找到一种方法，将圆周上的n个角度分布开来（假设最多有360个角度，每个角度之间相差1度，因此为 0:1:359）。

这些角度应根据需要生成，以使相邻角度之间的距离尽可能远。角度不能重复，也不能修改以适应新的角度。

例子：

0, 180, 90, 270, 135, 315, 225, 45

等等。

我尝试过编写它，但似乎无法完全理解如何编码。如果我稍微简化分配角度的方式，可能会更容易实现。

我尝试根据最后一个角度生成，同时计算当前“波浪”中生成的角度数，因为圆将被划分的方式将会上升（4次，8次等）。

package uniform_angles;

public class UniformAngles {

    public static void main(String[] args) 
    {
        int TOTAL_ANGLES = 360;

        // init number of angles to generate
        int numberOfAngles = 12;
        // store positions in array
        int[] positions = new int[numberOfAngles];

        // init first angle (special case for 0)
        int delta = 180;
        positions[0] = 0;
        int firstOrderPassCount = 1;
        //int secondOrderPassCount = 1;

        // generate
        for (int i = 1; i < numberOfAngles; i++) {
            if ((firstOrderPassCount*delta) == TOTAL_ANGLES) {
                delta /= 2;
            }

            int nextPos = (positions[i-1] + delta) % TOTAL_ANGLES;

            if ((nextPos % delta) == 0) {
                positions[i] = (positions[i-1] + (2*delta)) % TOTAL_ANGLES;
            }
            firstOrderPassCount++;
        }

        for (int i = 0; i < numberOfAngles; i++) {
            System.out.println(positions[i]);
        }
    }
}

- christophebedard

---

添加新角度后是否有可能重新平衡？ - Tim Biegeleisen

我认为你已经回答了自己的问题。如果你只能添加角度，那么很明显你将把圆分成1、2、4、8、16等部分。下一个要添加的角度计算起来非常简单。（尽管当你不再精确地除以2时，会有点棘手。）你尝试过什么？ - Gene

理想情况下，生成的角度应该保持不变，因为目标是在保留现有角度的同时根据需要生成更多的角度。 - christophebedard

我现在明白了...你在圆上添加一堆点（从而定义角度），然后，你想要一个算法来添加新的角度，同时最大化所有角度之间的空间。是这样吗？ - Tim Biegeleisen

似乎你所需要做的就是对弧进行排序，然后将找到的最大值除以它。 - Reblochon Masque

Answer 1

这个问题在“尽可能远离彼此”方面含糊不清。看起来您的意思是新角度应该位于已发出最大内角对称轴之间。如果是这样，那么您只需要简单的循环即可：

#include <stdio.h>

int main(void) {
  printf("0 ");
  for (int parts = 1; parts < 90; parts *= 2)
    for (int i = 0; i < parts; ++i)
      printf("%d ", 180 / parts +  360 * i / parts);
  printf("\n");
  return 0;
}

这会发出

0 180 90 270 45 135 225 315 22 67 112 157 202 247 292 337 11 33 56 78 
101 123 146 168 191 213 236 258 281 303 326 348 5 16 27 38 50 61 72 83 
95 106 117 128 140 151 162 173 185 196 207 218 230 241 252 263 275 286 
297 308 320 331 342 353 2 7 13 18 24 30 35 41 47 52 58 63 69 75 80 86 92 
97 103 108 114 120 125 131 137 142 148 153 159 165 170 176 182 187 193 
198 204 210 215 221 227 232 238 243 249 255 260 266 272 277 283 288 294 
300 305 311 317 322 328 333 339 345 350 356 

如果您需要更多的部分，那么我们可以使用浮点数进行角度计算，并四舍五入到最近的整数。第一对循环在简单四舍五入产生重复值时停止。这是在发射256个角度后。为了获得剩下的104个角度，我们遍历数组并打印剩余零的索引。这些必须由已经发射的角度括起来。

#include <stdio.h>

int main(void) {
  printf("0\n");
  int p[360] = {1, 0};
  for (int parts = 1; ; parts *= 2)
    for (int i = 0; i < parts; ++i) {
      int d = 0.5 + 180.0 / parts + 360.0 * i / parts;
      if (p[d]) goto done;
      p[d] = 1;
      printf("%d\n", d);
    }
 done:
  for (int i = 0; i < 360; ++i) if (!p[i]) printf("%d\n", i);
  return 0;
}

抱歉我用的是C语言而不是Java。目前无法使用Java环境，但应该很容易移植。请注意，最好预先计算出360个值的表格，并将它们存储在一个常量数组中。

- Gene

---

“新的角度应该位于已发射最大内角的一对射线的中间。”这并不是我想要的。非常抱歉我的表述含糊。新的角度应该尽可能“远离”前一个角度（考虑到它会回到360度等于0度的情况）。你需要在圆形上线性地遍历（例如[22 67 112 157 202 247 292 337]），同时改变分割因子。 - christophebedard

Answer 2

关于您的问题，有一个有趣的小知识点：看起来您想要生成的是一维低差异序列（也称拟随机蒙特卡罗序列）。

如果您看一下Van der Corput/Halton或Sobol在一维中的序列，它们看起来像：

0 [1/2, 1/4, 3/4, 1/8, 5/8, 3/8, 7/8, 1/16, ...]

基本上，每步将[0...1]区间在最大距离处分割。

Van der Corput/Halton: https://en.wikipedia.org/wiki/Van_der_Corput_sequence Sobol: http://www.deltaquants.com/sobol-sequence-simplified 有一个很好的Java库来处理这种情况：http://commons.apache.org/proper/commons-math/javadocs/api-3.3/org/apache/commons/math3/random/HaltonSequenceGenerator.html 或者 http://commons.apache.org/proper/commons-math/javadocs/api-3.3/org/apache/commons/math3/random/SobolSequenceGenerator.html。

PS：当然，你需要将QRNG映射回你的角度区间，[0...2pi]或[0...360]

- Severin Pappadeux

---

哇，这正是我正在寻找的！我确实尝试过谷歌搜索，但显然我不知道该搜索什么。它运行得非常好。非常感谢 :) - christophebedard

Answer 3

正如@ReblochonMasque所建议的那样，我们可以通过将最远离上一个生成角度的最长弧线分成若干部分来选择新角度。我们所说的两个角度之间的“距离”是它们之间的最短差值（例如，dist(30,300)=90）。

public class GenArcs {

    private Vector<Double> positions;

    public GenArcs() {
        positions = new Vector<Double>();
    }

    /**
     * Generate next angle
     * @return next angle
     */
    public double generate() {
        double newAngle = -1.0;

        if (positions.size() > 1) {
            Vector<Double> cpy = new Vector<Double>(positions);

            Collections.sort(cpy);

            // find longest arcs
            Vector<Double> arcs = computeArcLengths(cpy);
            Vector<Integer> longestArcIndexes = getLongestArcIndexes(arcs);

            // compute potential new angles
            Vector<Double> potentialNewAngles = computePotentialAngles(longestArcIndexes, arcs, cpy);

            // choose angle farthest from last angle
            newAngle = getFarthestAngle(potentialNewAngles, positions.get(positions.size()-1));
        } else if (positions.size() == 1) {
            // second angle (since distance between 0.0 and 0.0 is 0.0, so generated angle would still be 0.0; could fix in computeArcLengths(), but eh)
            newAngle = (positions.get(positions.size()-1) + 180) % 360;
        } else {
            // first angle
            newAngle = 0.0;
        }

        positions.add(newAngle);
        return newAngle;
    }

    public Vector<Double> getAngles() {
        return new Vector<Double>(positions);
    }

    /**
     * Compute the absolute difference between two angles on a circle [0,360[
     * @param first : first angle
     * @param second : second angle
     * @return difference
     */
    private static double getAngleDifference(double first, double second) {
        double firstMod = first % 360.0;
        double secondMod = second % 360.0;

        double diff = (firstMod <= secondMod) ? (secondMod - firstMod) : (360.0 - firstMod + secondMod);

        return diff;
    }

    /**
     * Choose angle farthest from given angle
     * @param potentialAngles : potential valid angles
     * @param angle : reference angle (latest generated angle)
     * @return farthest angle from given angle
     */
    private static double getFarthestAngle(Vector<Double> potentialAngles, double angle) {
        int farthestIndex = 0;

        for (int i = 1; i < potentialAngles.size(); ++i) {
            double farthestLength = Math.min(getAngleDifference(angle, potentialAngles.get(farthestIndex)), getAngleDifference(potentialAngles.get(farthestIndex), angle));
            double iLength = Math.min(getAngleDifference(angle, potentialAngles.get(i)), getAngleDifference(potentialAngles.get(i), angle));
            farthestIndex = (iLength > farthestLength) ? i : farthestIndex;
        }

        return potentialAngles.get(farthestIndex);
    }

    /**
     * 
     * @param longestArcIndexes : indexes of the longest arcs
     * @param arcsLengths : lengths of arcs, in order
     * @param angles : angles, sorted
     * @return angles corresponding to longest arcs
     */
    private static Vector<Double> computePotentialAngles(Vector<Integer> longestArcIndexes, Vector<Double> arcsLengths, Vector<Double> angles) {
        Vector<Double> potentialAngles = new Vector<Double>();

        for (int i = 0; i < longestArcIndexes.size(); ++i) {
            int arcIndex = longestArcIndexes.get(i);
            double arcLength = arcsLengths.get(arcIndex);
            double firstAngle = angles.get(arcIndex);
            double potentialAngle = (firstAngle + (arcLength/2.0)) % 360.0;
            potentialAngles.add(potentialAngle);
        }

        return potentialAngles;
    }

    /**
     * Find index(es) of the longest arc
     * @param arcs : arc lengths, in sorted order
     * @return indexes of the longest arcs
     */
    private static Vector<Integer> getLongestArcIndexes(Vector<Double> arcs) {
        Vector<Integer> arcIndexes = new Vector<Integer>();
        double longestArc = Collections.max(arcs);

        int index = arcs.indexOf(longestArc);
        while(index >= 0) {
            arcIndexes.add(index);
            index = arcs.indexOf(longestArc, index+1);
        }

        return arcIndexes;
    }

    /**
     * Computes and returns a vector of arc lengths from a vector of angles
     * @param vec : vector of angles (sorted)
     * @return vector of arc lengths, in the same order
     */
    private static Vector<Double> computeArcLengths(Vector<Double> vec) {
        Vector<Double> arcs = new Vector<Double>();

        for (int i = 0; i < vec.size(); ++i) {
            double firstPos = vec.get(i);
            double secondPos = vec.get((i+1) % vec.size());

            double arcLength = getAngleDifference(firstPos, secondPos);

            arcs.add(arcLength);
        }

        return arcs;
    }
}

使用示例。

public class UniformAnglesTest {

    public static void main(String[] args) {
        final int TOTAL_ANGLES = 20;

        GenArcs genArcs = new GenArcs();

        // generate
        for (int i = 0; i < TOTAL_ANGLES; i++) {
            double newPosArcs = genArcs.generate();

            System.out.println("---------------\ni = " + i);
            System.out.println("arcs   : " + newPosArcs);
        }
    }
}

- christophebedard

Answer 4

也许值得进一步扩展Severin的答案，您发现它很有用。

这个问题已经被研究了一个多世纪。解决这个问题的方法通常在于利用低差异序列的特殊属性。

构造低差异序列的方法有很多种。其中包括Weyl/Krocker、Van der Corput/Halton、Sobol和Niederreiter序列等。在所有这些情况下，它们提供了一种方法，在不需要“重新平衡”之前放置点的情况下，在d维中分布n个点的方法。例如，在二维中，以下是每个序列的前100个项的样子：

然而，可能不是很清楚的是，对于您的问题，只需要1维解决方案。(请注意，它通常被称为1维，因为您需要与位于2维平面中的圆周的1维周长相对应的角度。)

此外，尽管许多构造(例如 van der Corput)在1-d中提供非常好的结果，但Weyl/Kronecker解决方案(如下所述)是1-d问题的唯一最优解。

考虑无限序列，

x[n] = (s + k*n )% 1

其中'seed' float s和恒定的'parameter' float k。

请注意，$(%1)$，发音为'mod 1'运算符，取参数的小数部分。

此定义产生一个数组/列表，其中每个x[n]位于区间[0,1]中。

s的选择不会影响序列的基本特性，因此出于简单起见，通常设置为零，但软件开发人员经常将其包括在内，因为它通过设置不同的种子可以为创建不同的序列提供选项。

关键是，在形成低差异序列时，某些常数k的选择比其他常数更好。

最重要的是，有一个值的k是可以证明是最优的。

最优情况是当k= phi = (1+sqrt(5))/2 = 1.61803398875...，即黄金比例。

这就是为什么这个问题通常被称为黄金比例调度问题，因为解决方案使用了"黄金角度"。同样可能感兴趣的是，黄金螺旋的构造也直接与这个序列相关。

有关为什么这个值是最优的以及为什么k= sqrt(2)是下一个最佳选项的进一步解释，请参见类似的StackExchange帖子"黄金比例模1分布"。

最后，要将x[n]转换为角度，只需乘以360即可。

理想情况下，角度应存储为浮点数，以允许完全表示0到360度之间的所有实数值，并允许无限的点列表。然而，如果您真的只想要整数值，就像您在问题中建议的那样，那么取floor(360*x[n])仍将为n<90产生出色的结果，并且对于n<360也会产生相当不错的结果。

- Martin Roberts