尽可能均匀地在圆上分布点
问题描述
我遇到了一个问题：我有一个圆圈，上面有一些固定的点（可能是零个或多个）。这些点的位置是固定的。现在，我需要在这个圆圈上放置另一组点，目的是让所有的点尽可能均匀地分布在圆圈上。
目标
我的目标是开发一个算法，这个算法接收一个角度列表（代表固定点的位置）和一个整数值（代表需要放置多少个额外的点），然后返回一个角度列表（只包含额外点应该放置的角度）。
这些点不需要完全均匀分布（也就是说，彼此之间的距离不一定相同），但要尽量做到均匀。因为某些点是固定的，所以通常情况下可能不存在完美的解决方案。
所有角度的范围在 -π 到 +π 之间。
示例
以下是我想要实现的一些示例：
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)
最后一个例子应该返回类似这样的结果：一个点应该放在 -π*3/4 和 -π/4 之间，也就是 -π/2，然后把其他5个点分布在 -π/4 和 +π 之间（记住这是一个圆圈，所以在这种情况下 -π = +π）：
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
这不是一个很好的解决方案，因为它本可以分布得更好（见上面：-π/6 和 +π/6）。
抱歉问题有点长，希望你能理解我想要实现的目标。
我不需要一个完整的工作算法，而是希望得到开发一个的正确思路。如果你愿意，可以给我一些伪代码。我会非常感激你能给我一些提示，帮助我朝正确的方向前进。谢谢！
更新：完成的算法：
感谢大家的回答！我发现我基本上只需要一个非贪心版本的现有算法。我非常喜欢 haydenmuhl 的想法，通过封装一个区间/段类来简化问题：
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
9 个回答
假设这些点之间的间隔是 a_1 到 a_n。如果我们把每个区间分成最小大小为 d 的小段，那么在这个区间里可以放入 floor(a_i/d) - 1 个点。这意味着 sum(floor(a/d) for a in interval_lengths) 必须大于或等于 n + s，其中 n 是我们想要添加的点的数量，s 是已经存在的点的数量。我们希望选择尽可能大的 d，最好的办法可能是用二分查找来找到合适的 d。
一旦我们选择了 d，就可以在每个区间里，每隔 d 的距离添加一个点，直到这个区间里剩下的距离少于 2d。
编辑 你只需要找到一个 d，使得 sum(floor(a/d) for a in interval_lengths) == n + s，然后每隔 a_i/(floor(a_i/d) - 1) 的距离在第 i 个区间里放入 floor(a_i/d) - 1 个点。用二分查找可以很快找到这个 d。
进一步编辑
这里有代码可以用来找到 d
def get_d(n, a, lo=0, hi=None):
s = len(a)
lo = 360./(s + n)
hi = 2. * lo
d = (lo + hi)/2
c = sum(floor(x/d) for x in a)
while c != (n + s):
if c < (n + s):
hi = mid
else:
lo = mid
d = (lo + hi)/2
c = sum(floor(x/d) for x in a)
return d
假设你已经有了M个点，现在还需要添加N个点。如果这些点均匀分布，那么它们之间的间隔就是2*pi/(N+M)。所以，如果你在M个点处切割，就会得到M个角度的段落。你可以在每个段落中放置点（彼此均匀分布），直到段落中的空间小于或等于2*pi/(N+M)。
那么，如果一个段落的长度是L，你应该在里面放置floor(L*(N+M)/(2*pi)) - 1个点。
现在你会有一些点剩下。你需要根据如果再添加一个点后，点之间的间隔来给段落排名。实际上，把这个点添加到排名最低的段落中。然后把这个段落重新放回你的排序列表中，继续这个过程，直到所有的点都用完。
因为每次你都是把点放到一个段落中，使得结果是点之间的间隔尽可能大，而点之间的间隔并不依赖于你添加它们的顺序，所以最后你会得到最优的间隔。
（补充说明：“最优”是指“点之间的最小距离最大化”，也就是说，尽量避免点重叠的最坏情况。）
（补充说明：希望大家明白，这个方法是先决定每个段落放多少个点，最后再在每个段落内均匀分布这些点。）
你可以使用一个叫做“区间”的对象。区间就是在圆上两个固定点之间的弧。
下面的内容只是伪代码，不要指望它能在任何地方运行。
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;
}
}
创建一个列表，里面放这些对象，代表你圆上各个点之间的区间。每次你添加一个点时，选择那个下一个长度最大的区间。当你完成后，重建新的圆形也不会太难。
这样做可以让你得到间隔最大的最小区间。也就是说，如果你用最小区间的长度来给解决方案打分，这样的做法会让你得到最高的分数。我觉得这正是你想要的结果。
补充：我刚意识到你特别提到想用Python来做。我对Python还很陌生，但你应该能很容易地把这个转换成Python对象，虽然你不需要获取器，因为在Python中所有东西都是公开的。