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

可以使用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;
  }
}

编辑:

假设你有 M 已经给出的分数,以及 N 需要补充更多。如果所有的点都是均匀分布的,那么就有 2*pi/(N+M) 在他们之间。所以,如果你切你的头发 给分 米 线段的角度,您当然可以将点放置到线段中(彼此均匀间隔),直到空间小于或等于 2*pi/(N+M) .

所以,如果一段的长度是 L floor(L*(N+M)/(2*pi)) - 1 指向它。

现在你还剩下一些分数。如果再添加一个点,则按点之间的间距对线段进行排序。实际上,将点添加到具有最低秩的段。重新把这个插入到你的排序列表中,然后再这样做,直到你的点数用完为止。

因为每次将一个点放置到一个线段中时,结果将是间距尽可能大的点,并且点之间的间距不取决于添加它们的顺序,因此最终会得到最佳间距。

(编辑:其中“最佳”是指“点之间的最大最小距离”,即尽可能避免最坏情况下点相互重叠。)

假设点之间的间隔是1。。。是的。如果我们把每个片段分成最小尺寸d的片段,我们就可以 floor(a_i/d) - 1 线段中的点。这意味着 sum(floor(a/d) for a in interval_lengths) 必须大于或等于 n + s

你所需要的就是找到这样的人 sum(floor(a/d) for a in interval_lengths) == n + s ,然后分配 我每段 a_i/(floor(a_i/d) - 1)

进一步编辑

下面是查找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

求N个点的分布,其中任意两点与M个点之间的最小距离的长度是最大的。 L 您有M个长度的现有段,假设它们存储在列表中 s . 如果这个长度是 我 首先

min(s) > L

 f(L) = sum(ls/L -1 for ls in s)

因此,您可以使用二进制搜索来找到最优L,它取最小L=0和最大L=min(s),并检查sum(ls/L-1表示s中的ls)>=N。 对于每一段s[i],你可以把s[i]/L-1点均匀地放在它上面。

更新 min(s) > L . 这对于重新定义的术语来说已经足够了,但是对于最初的术语来说却是错误的。我已将此条件更改为 max(s) > L . 在二进制搜索中还增加了对小于L的段的跳过。 代码:

from math import pi,floor
def distribute(angles,n):
    s = [angles[i] - angles[i-1] for i in xrange(len(angles))]
    s = [ls if ls > 0 else 2*pi+ls for ls in s]
    Lmin, Lmax = 0., max(s)
    while Lmax - Lmin >1e-9:
        L = (Lmax + Lmin)/2
        if sum(max(floor(ls/L) -1,0) for ls in s ) < n: Lmax = L
        else : Lmin = L
    L= Lmin
    p = []
    for i in xrange(len(s)):
        u = floor(s[i]/L) -1
        if u <= 0:continue
        d = s[i]/(u+1)
        for j in xrange(u):
            p.append(angles[i-1]+d*(j+1))
    return p[:n]
print distribute((0, pi/4),1)
print distribute((-pi,-pi/2,pi/2),2

你从来没有说过什么是“如何均匀分布”的精确测量。间隔大小与完全间隔间隔间隔大小的总均方根方差,还是别的?

如果你在一开始看任何一个特定的开放区间,我相信一个最优的解决方案 k 该间隔中的点总是将它们均匀地隔开。因此,问题归结为选择最小间隔大小的截止点,以获得一定数量的间隙点。完成后,如果你没有足够的分数来分配,从最大到最小的间隔中,从每个间隔中删除一个分数,然后重复,直到你得到一个合理的答案。

我建议您将问题考虑为:

• 一条折线-允许您轻松确定点间距离,然后重新映射到圆

一个想法,把角度写成列表(以度为单位):
[30, 80, 120, 260, 310]
[ 50, 40, 140, 50, 80]
注意,我们绕310+80(mod 360)=30,第一个角
对于要添加的每个点,拆分最大的差异:
n=1,分为140:
n=2,分80:
[50, 40, 70, 70, 50, 40, 40]
转换回角度:
[30, 80, 120, 190, 260, 310, 350]

Starting with array  [30, 80, 120, 260, 310] and adding n = 5 angles,
the given algorithm (see below) gives [30, 55, 80, 120, 155, 190, 225, 260, 310, 350]
with a root mean square of the differences between angles
   rms(diff) = sqrt[sum(diff * diff)] / n = 11.5974135047,
which appears to be optimal for practical purposes.

我有一个名为“condition”的函数,它接受两个参数——分子(const)和分母(pass by ref)。它要么“增大”要么“缩小”分母的值,直到整数个“分母”适合分子,即分子/分母是整数。

分母是增大还是缩小,取决于哪一个分母会使它发生较小的变化。

将分子设置为2*pi,分母设置为任何接近你想要的间距的值,你应该得到非常接近均匀分布的值。

请注意,我还有一个函数“compare”,它在一定的公差范围内比较两个double是否相等。

bool compare( const double num1, const double num2, const double epsilon = 0.0001 )
{
     return abs(num1 - num2) < epsilon;
}

那么条件函数是

void condition(const double numerator, double &denominator)
{
  double epsilon = 0.01;
  double mod = fmod( numerator, denominator );
  if( compare(mod, 0) )
    return;
  if( mod > denominator/2 ) // decide whether to grow or shrink
    epsilon *= -1;

  int count = 0;
  while( !compare( fmod( numerator, denominator ), 0, 0.1) )
  {
    denominator += epsilon;
    count++;
    if( count > 10000 ) // a safety net
      return;
  }
}