为均匀分布点上圆越好 [英] Distribute points on a circle as evenly as possible
问题描述
问题陈述
我有以下问题：我有与它的点的特定数量（零个或多个）的圆。这些位置是固定的。现在我来定位另一组在圆，点，如所有的点一起被作为均匀地分布在圆周越好。
目标
我的目标是现在开发一个算法，取角度的列表（再presenting固定点）和一个int值（重presenting许多额外的点应该如何放置），并返回角度的列表再次（只包含角度，其中附加分应该撒谎）。
的点不必须真正均匀分布（从对方相同的距离），而是尽可能均匀，这只是可能的。甲完美的解决方案可能不存在的大部分时间，如某些点被固定。
各个角度的范围在于-pi和+ PI之间。
示例
什么，我想archieve一些例子：
fixed_points = [-pi，-pi / 2，π/ 2]
V V V
| --------- | --------- | --------- | --------- |
-pi -pi / 2 0 PI / 2 PI
fill_circle（fixed_points，1）
＃应返回：[0]
fill_circle（fixed_points，2）
＃应该返回：[-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之间的其他5个点+ PI（记住这是一个循环，所以在这种情况下-pi = + PI）：
vvxvxxxxx
| --------- | --------- | --------- | --------- |
-pi -pi / 2 0 PI / 2 PI
previous尝试
我开始递归算法，对于两点间的最大间隔首先搜索并设置在两者之间的新点右边。但是它没有给出令人满意的结果。考虑例如这样的结构，与需要两个点被插入
V V V
| --------- | --------- | --------- | --------- |
-pi -pi / 2 0 PI / 2 PI
第一步：插入右在最大间隔中间
v v x垂直
| --------- | --------- | --------- | --------- |
-pi -pi / 2 0 PI / 2 PI
第二步骤：插入右在最大间隔中间
- ＆GT;所有的间隔均匀地大，因此他们中的一个将采取
v x V V V
| --------- | --------- | --------- | --------- |
-pi -pi / 2 0 PI / 2 PI
不是一个非常好的解决方案，因为它可能是更好的分布（见上：-pi / 6 + PI / 6）
。对不起，长的问题，我希望你明白我想archieve。
我不需要一个完整的工作的算法，而是开发一个正确的想法。也许一些伪code，如果你喜欢。将非常感谢一些提示，把我在正确的方向。在此先感谢！
更新：已完成的算法：
感谢大家的答案！这表明了，我基本上只是需要我已有算法的非贪婪版本。我真的很喜欢 haydenmuhls 的想法简化问题通过封装的间隔/段班一点点：
类板块：
高清__init __（个体经营，角，prev_angle，wrap_around）：
self.angle =角
self.length = ABS（角 - prev_angle + \
（如果wrap_around否则为0 2 * math.pi））
self.num_points = 0
高清sub_length（个体经营）：
返回self.length /（self.num_points + 1）
高清next_sub_length（个体经营）：
返回self.length /（self.num_points + 2）
高清add_point（个体经营）：
self.num_points + = 1
这使得实际的算法非常容易易读的：
高清分发（角度，N）：
＃没分给？均匀地分布在他们周围的圈子
如果len（角度）== 0：
返回[2 * math.pi / N * I - 中的xrange math.pi为I（N）]
＃排序的角度和分裂圈成段
S，PI，RET =排序（角度），math.pi，[]
段= [段（S [I]，S [I-1]，我== 0）因为我在的xrange（LEN（S））]
＃计算所有子段，如果该点的长度
＃将添加;取最大的点添加到
对于_中的xrange（N）：
最大（段，关键=拉姆达X：x.next_sub_length（））add_point（）
＃所有拆分段和返回点的角度
为赛格段：
对于k中的xrange（seg.num_points）：
一个= seg.angle - seg.sub_length（）*（K + 1）
＃确保所有返回的值-pi和+ PI之间
ret.append（A - 2 * PI如果＆GT; PI否则A + 2 * PI如果＆LT; -pi否则一）
返回RET
您可以使用一个间隔的对象。的间隔为2的原始的，不可移动的点之间的圆弧
下面只是伪code。不要指望它在任何地方运行。
类间隔{
私人长度;
私人point_count;
构造函数（长）{
this.length =长度;
this.point_count = 0;
}
公共add_point（）{
this.point_count ++;
}
公共长度（）{
返回this.length;
}
//每个子间隔的当前长度
公共sub_length（）{
返回this.length /（this.point_count + 1）;
}
//子区间长度，如果你要再添点
公共next_sub_length（）{
返回this.length /（this.point_count + 2）;
}
公共point_count（）{
返回this.point_count;
}
}
创建这些对象相应于您的圆点之间的间隔的列表。每次添加一个点，选择具有最大next_sub_length的时间间隔（）。当您完成后，它会不会很难重建新的圈子。
这应该给你的最大可能的最小间隔的距离。也就是说，如果你的分数由它的最小间隔长度的解决方案，这会给你的最高分。我想，这是你一直在拍摄什么。
编辑：刚刚意识到您专门询问了在Python。我相当一个Python的n00b，但你应该能够将其转换为一个Python对象很轻松了，但你不需要的干将，因为一切都在Python是公开的。
Problem statement
I have the following problem: I have a circle with a certain number (zero or more) of points on it. These positions are fixed. Now I have to position another set of points on the circle, such as all points together are as evenly distributed around the circle as possible.
Goal
My goal is now to develop a algorithm taking a list of angles (representing the fixed points) and an int value (representing how many additional points should be placed) and returning a list of angles again (containing only the angles where the additional points should lie).
The points dont have to be really evenly distributed (all same distance from each other), but rather as evenly as it is just possible. A perfect solution may not exist most of the time, as certain points are fixed.
The range of all angles lie in between -pi and +pi.
Examples
Some examples of what I am trying to archieve:
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]
or:
fixed_points = [-pi, -pi*3/4, -pi/4]
v v v
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
fill_circle(fixed_points, 6)
This last example should return something like: One point is to set right in between -pi*3/4 and -pi/4, that is: -pi/2 and distribute the other 5 points between -pi/4 and +pi (remember it is a circle, so in this case -pi = +pi):
v v x v x x x x x
|---------|---------|---------|---------|
-pi -pi/2 0 pi/2 pi
Previous try
I started with a recursive algorithm that first searches for the largest interval between two points and sets the new point right in between. However it doesnt give satisfying results. Consider for example this configuration, with two points needed to be inserted:
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
Not a very nice solution, as it could have been much better distributed (see above: -pi/6 and +pi/6).
Sorry for the long question, I hope you understand what I want to archieve.
I dont need a complete working algorithm, but rather the right idea for developing one. Maybe some pseudocode if you like. Would be very grateful for some hints to push me in the right direction. Thanks in advance!
Update: Completed algorithm:
Thank you all for your answers! It showed up I basically just needed a non-greedy version of my already existing algorithm. I really liked haydenmuhls idea to simplify the problem a little bit by encapsulating an interval/segment class:
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
This makes the actual algorithm incredibly easy and readable:
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
You could use an Interval object. An interval is an arc of the circle between two of the original, immovable points.
The following is just pseudo-code. Don't expect it to run anywhere.
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;
}
}
Create a list of these objects corresponding to the intervals between points on your circle. Each time you add a point, select the interval with the largest next_sub_length(). When you're done, it won't be hard to reconstruct the new circle.
This should give you the spacing with the the largest possible minimum interval. That is, if you score a solution by the length of its smallest interval, this will give you the highest score possible. I think that's what you've been shooting for.
Edit: Just realized that you specifically asked about this in Python. I'm quite a Python n00b, but you should be able to convert this to a Python object easily enough, though you won't need the getters, since everything in Python is public.
这篇关于为均匀分布点上圆越好的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
