问题陈述

我有以下问题:我有一个圆，上面有一定数量(零个或多个)点。这些位置是固定的。现在我必须在圆上定位另一组点，例如所有点一起尽可能均匀地分布在圆周围。

目标

我现在的目标是开发一种算法，采用角度列表(表示固定点)和 int 值(表示应该放置多少额外点)并再次返回角度列表(仅包含角度应该有额外的点)。

这些点不必真正均匀分布(彼此之间的距离相同)，而是尽可能均匀。大多数时候可能不存在完美的解决方案，因为某些点是固定的。

所有角度的范围都在-pi和+pi之间。

示例

我正在努力实现的一些示例:

fixed_points = [-pi, -pi/2, pi/2]

 v         v                   v
 |---------|---------|---------|---------|
-pi     -pi/2        0        pi/2       pi

fill_circle(fixed_points, 1)
# should return: [0]

fill_circle(fixed_points, 2)
# should return: [-pi/6, pi/6]

或:

fixed_points = [-pi, -pi*3/4, -pi/4]

 v    v         v
 |---------|---------|---------|---------|
-pi     -pi/2        0        pi/2       pi

fill_circle(fixed_points, 6)

最后一个示例应该返回类似:一个点设置在 -pi*3/4 和 -pi/4 之间，即:-pi/2 并在 -pi/4 和 -pi/4 之间分配其他 5 个点+pi(记住它是一个圆圈，所以在这种情况下 -pi = +pi):

 v    v    x    v   x   x    x   x    x
 |---------|---------|---------|---------|
-pi     -pi/2        0        pi/2       pi

以前的尝试

我从一个递归算法开始，它首先搜索两点之间的最大间隔，然后在两者之间设置新点。然而，它并没有给出令人满意的结果。例如，考虑这个配置，需要插入两个点:

 v         v                   v
 |---------|---------|---------|---------|
-pi     -pi/2        0        pi/2       pi

first step: insert right in the middle of largest interval
 v         v         x         v
 |---------|---------|---------|---------|
-pi     -pi/2        0        pi/2       pi

second step: insert right in the middle of largest interval 
-> all intervals are evenly large, so one of them will be taken
 v    x    v         v         v
 |---------|---------|---------|---------|
-pi     -pi/2        0        pi/2       pi

不是一个很好的解决方案，因为它本来可以更好地分布(见上文:-pi/6 和 +pi/6)。

抱歉这个问题太长了，我希望你明白我想要实现的目标。

我不需要一个完整的工作算法，而是开发一个正确的想法。如果你喜欢的话，也许是一些伪代码。将非常感谢一些提示，将我推向正确的方向。提前致谢!

更新:完成的算法:

谢谢大家的回答!它显示我基本上只需要我现有算法的非贪婪版本。我真的很喜欢 haydenmuhls通过封装一个区间/段类来稍微简化问题的想法:

class Segment:
    def __init__(self, angle, prev_angle, wrap_around):
        self.angle = angle
        self.length = abs(angle - prev_angle + \
                          (2*math.pi if wrap_around else 0))
        self.num_points = 0
    
    def sub_length(self):
        return self.length / (self.num_points + 1)
    
    def next_sub_length(self):
        return self.length / (self.num_points + 2)
    
    def add_point(self):
        self.num_points += 1

这使得实际的算法非常简单易读:

def distribute(angles, n):
    # No points given? Evenly distribute them around the circle
    if len(angles) == 0:
        return [2*math.pi / n * i - math.pi for i in xrange(n)]
    
    # Sort the angles and split the circle into segments
    s, pi, ret = sorted(angles), math.pi, []
    segments = [Segment(s[i], s[i-1], i == 0) for i in xrange(len(s))]
    
    # Calculate the length of all subsegments if the point
    # would be added; take the largest to add the point to
    for _ in xrange(n):
        max(segments, key = lambda x: x.next_sub_length()).add_point()

    # Split all segments and return angles of the points
    for seg in segments:
        for k in xrange(seg.num_points):
            a = seg.angle - seg.sub_length() * (k + 1)
            # Make sure all returned values are between -pi and +pi
            ret.append(a - 2*pi if a > pi else a + 2*pi if a < -pi else a)
    
    return ret

最佳答案

假设你已经给出了 M 个点，还需要添加 N 个点。如果所有点的间距均匀，那么它们之间就会有 2*pi/(N+M) 的间隙。因此，如果您在 M 点处切割以提供 M 角度段，您当然可以将点放入一个段中(彼此均匀间隔)，直到空间更小大于或等于 2*pi/(N+M).

所以，如果一个段的长度是L，那么你应该放置floor(L*(N+M)/(2*pi)) - 1指向它。

现在你会留下一些积分。如果再添加一个点，则按点之间的间距对段进行排序。实际上将点添加到排名最低的段。将那个重新插入您的排序列表并再次执行此操作，直到用完点。

由于每次将点放入线段中，结果将是尽可能宽的点，并且点之间的空间不取决于您添加它们的顺序，因此您最终会得到最佳间距。

(编辑:其中“最佳”表示“点之间的最大最小距离”，即尽可能避免点彼此重叠的最坏情况。)

(编辑:我希望很清楚这个想法是决定每个段有多少分，然后只有在最后，在所有数字都确定后，你是否在每个段内平均分配它们。 )

关于python - 尽可能均匀地将点分布在一个圆上，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3479736/