尽可能均匀地分布圆上的点

Question

问题陈述

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

目标

我的目标是开发一种算法,它采用角度列表(表示固定点)和一个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之间分配其他5个点(记住它是一个圆圈,所以在这种情况下-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的想法,通过封装一个interval/segment类来简化问题:

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

Answer 1

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

因此,如果段的长度是L,那么您应该将floor(L*(N+M)/(2*pi)) - 1点放入其中.

现在你将剩下一些积分.如果添加了一个点,则按点之间的间距对线段进行排名.实际上将该点添加到排名最低的细分市场.将其中的一个重新插入到排序列表中并再次执行此操作,直到用完为止.

因为每次你将一个点放入一个段,其中结果将尽可能地间隔点,并且点之间的空间不依赖于添加它们的顺序,所以最终会得到最佳间距.

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

(编辑:我希望很明显,这个想法是决定每个段中有多少点,然后只在最后,在数字全部被确定之后,你是否在每个段中平均分配它们.)

Answer 2

您可以使用Interval对象.间隔是两个原始不可移动点之间的圆弧.

以下只是伪代码.不要指望它在任何地方运行.

class Interval {

  private length;
  private point_count;

  constructor(length) {
    this.length = length;
    this.point_count = 0;
  }

  public add_point() {
    this.point_count++;
  }

  public length() {
    return this.length;
  }

  // The current length of each sub-interval
  public sub_length() {
    return this.length / (this.point_count + 1);
  }

  // The sub-interval length if you were to add another point
  public next_sub_length() { 
    return this.length / (this.point_count + 2);
  }

  public point_count() {
    return this.point_count;
  }
}

创建与圆上各点之间的间隔对应的这些对象的列表.每次添加一个点时,选择具有最大next_sub_length()的间隔.当你完成后,重建新圈子并不困难.

这应该为您提供最大可能的最小间隔.也就是说,如果您按照最小间隔的长度对解决方案进行评分,这将为您提供最高分数.我认为这就是你拍摄的内容.

编辑:刚才意识到你在Python中专门询问过这个问题.我是一个Python n00b,但你应该能够轻松地将它转换为Python对象,尽管你不需要getter,因为Python中的所有东西都是公共的.