在数学，科学和计算机系统中，球上点的最均匀分布是一项非常重要的任务，并且使用相同的投影将Fibonacci网格应用于球的表面是解决该问题的极其快速而有效的近似方法。我将展示如何通过较小的更改使它变得更好。

不久前，该帖子出现在Hacker News主页上。它的讨论可以在这里阅读。

引言

球上点的均匀分布问题历史悠久。这是关于球形几何的数学文献中研究最深入的问题之一。它在数学，物理，化学的许多领域都至关重要，包括计算方法，逼近理论，编码理论，晶体学，静电学，计算机图形学，病毒形态学以及许多其他领域。

不幸的是，除了一些特殊情况（即柏拉图固体）之外，不可能在球体上完美地分布点。另外，问题的解决很大程度上取决于用于评估均匀性的标准。实际上，使用了许多标准，包括：

包装和涂层
凸包，Voronoi细胞和Delaunay三角形
核仁 $s$ 大米能源
古巴和预选赛

阐明这一方面非常重要：通常没有针对此问题的最佳解决方案，因为基于一个准则的最佳解决方案通常不是针对其他准则的最佳点分布。例如，我们还将发现包装优化不一定会创建最佳的凸包，反之亦然。

为了简洁起见，在本文中，我们将仅考虑两个条件：最小包装距离和凸包/ Delaunay网格（体积和面积）。

在第1部分中，我们展示了如何更改规范的斐波那契网格以构建更好的包装分布 。在第2节中，我们展示了如何更改规范的斐波那契网格以建立凸包的改进参数（体积和表面积）。

第1节。优化包装距离

通常，这个问题被称为塔姆（Tamm）的任务 ，以纪念植物学家特姆斯（Tems），后者寻求解释花粉粒的表面结构。打包标准要求我们最大化邻居之间的最小距离

$N$ 点。那是

$d_N = \ min_ {i \ neq j} | x_i-x_j |$

该值随速度降低。

〜

$〜1 / \ sqrt {N}$ 因此，确定归一化距离以及归一化距离的渐近极限将非常有用，

，

$d ^ * _ N = \ sqrt {N} d_N，\ quad \ quad d ^ * = \ lim_ {N \ rightarrow \ infty} d ^ * _ N$

斐波那契网格

一种非常优雅的解决方案对自然界中发现的节点进行建模，例如，将种子分布在向日葵或松果中。这种现象称为螺旋叶序。 Coxeter表明，这种结构与斐波那契数列有根本的联系，

F_k = \ {1，1，2，3，5，8，13，... \}

$F_k = \ {1，1，2，3，5，8，13，... \}$ 和黄金比例

（ ）

$\ phi =（1+ \ sqrt {5}）/ 2$ 。

在文献中，发现了球形斐波那契网格点集的两个相似定义。来源严格为

$N$ 等于斐波那契数列的成员之一，

$F_m$ ，并对数论进行了深入研究。

$t_i = \左（\ frac {i} {F_m}，\ frac {i F_ {m-1}} {F_m} \右）\ quad \ textrm {for} \; 0 \ leq i \ leq N-1$

第二个定义将公式推广到任意数量

$N$ 并经常用于计算中：

$t_i = \左（\ frac {i} {N}，\ frac {i} {\ phi} \ right）\ quad \ textrm {for} \; 0 \ leq i \ leq N \ tag {1}$

在哪里

$\ phi = \ frac {1+ \ sqrt {5}} {2} = \ lim_ {n \ rightarrow \ infty} \ left（\ frac {F_ {n + 1}} {F_n} \ right）$

以下是相同的斐波那契网格的示例。通过转换，您可以将这些点集转换为我们众所周知的斐波那契螺旋线。

$（r，\ theta）=（\ sqrt {x_1}，2 \ pi x_2）$

同样，这些点集可以从单位平方转移

$[0，1] ^ 2$ 在球体上使用圆柱等距投影：

$（x，y）\ rightarrow（\ theta，\ phi）：\ quad \ left（\ cos ^ {-1}（2x-1）-\ pi / 2，2 \ pi y \ right）$

$（\\ theta，\ phi）\ rightarrow（x，y，z）：\ quad \ left（\ cos \ theta \ cos \ phi，\ cos \ theta \ sin \ phi，\ sin \ theta \ right）$

在stackoverflow上可以找到许多不同版本的Python代码：在球体上均匀分布点。

即使球形Fibonacci集在全球范围内并不是最佳的样本分布（因为它们的解与柏拉图固体的解并不吻合）。

$n = $ 4,6,8,12,2$ ），它们具有出色的采样属性，并且与其他更复杂的球形采样方案相比，非常易于构建。

由于从单位正方形到球体表面的转移是通过保留面积的投影进行的，因此可以预期，如果起点均匀分布，则它们也将在球体表面上相当均匀地分布。但是，这并不意味着分布将证明是最优的。

这种转移遭受两个不同但相互关联的问题。

首先，在保持面积而不是距离的同时执行此覆盖。假设在我们的情况下，条件是使点之间的最小成对最小距离最大化，则投影后不一定要满足这些条件和关系。

从实用的角度来看，第二个问题最难解决：叠加在每个极点上都有两个退化点。考虑两个非常接近极点但经度相差180度的点。在单个正方形上（以及在圆柱投影上），它们将对应于彼此相距很远的两个点，但是，当叠加在球体表面上时，它们可以通过穿过北极的很小的弧形连接。由于这个特殊的问题，许多螺旋覆盖物不够理想。

从等式1获得的斐波那契球面螺旋给出值

$d_N ^ *$ 对于所有

$N$ 那就是

$d ^ * = 2$ 。

网格1

一个更通用的版本（尤其是在计算机系统上），可以带来更高的价值

$d ^ * = 3.09$ 具有以下形式：

$t_i = \左（\ frac {i + 1/2} {N}，\ frac {i} {\ phi} \ right）\ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \标签{2}$

它将点放置在区间的中点（根据高斯二次公式中的中点规则），因此，对于

$n = 100$ ，第一个坐标的值如下：

$\ {\ frac {0.5} {100}，\ frac {1.5} {100}，\ frac {2.5} {100}，\ ldots，\ frac {97.5} {100}，\ frac {98.5} {100} ，\ frac {99.5} {100} \}$

网格2。

进一步改进公式2的关键是要意识到

$d ^ * _ N$ 总是对应于点之间的距离

$t_0$ 和

$t_3$ 在两极。即改善

$d_N$ 极点附近的点应该更远。

如果我们定义以下分布：

$t_i（\ varepsilon）= \左（\ frac {i + 1/2 + \ varepsilon} {N + 2 \ varepsilon}，\ frac {i} {\ phi} \ right）\ quad \ textrm {for} \ ; 0 \ leq i \ leq N-1$

$d ^ * _ N$ -各种值的曲线。

$\ varepsilon = 0$ （蓝色）;

$\ varepsilon = \ frac {1} {2}$ （橙色）;

$\ varepsilon = \ frac {3} {2}$ （绿色）；和

$\ varepsilon = \ frac {5} {2}$ （红色）。你可以看到

$\ varepsilon = \ frac {5} {2}$ 使结果更接近渐近结果。也就是说，

$N> 20$ 以下简单表达式可产生明显更好的结果。

$d ^ * = 3.29$ 与标准球形Fibonacci网格相比：

$t_i = \左（\ frac {i + 3} {N + 5}，\ frac {i} {\ phi} \ right）\ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \标签{3}$

也就是说，

$N = 100$ 第一个坐标的值将等于：

$\ {\ frac {3} {105}，\ frac {4} {105}，\ frac {5} {105}，\ ldots，\ frac {100} {105}，\ frac {101} {105} ，\ frac {102} {105} \}$

图1.不同的值

$d_N ^ *$ 在不同的值

$\ epsilon$ 。 值越高，配置越优化。 我们看到

$\ epsilon \ simeq 2.5$ 提供接近最佳的解决方案。

网格3。

如上所述，球上点的均匀分布的最严重问题之一是分布的最佳程度严格取决于所使用的目标函数。原来如此。本地数量就像

$d_N ^ *$ 有时他们几乎“不会原谅错误”-最佳位置中的单个点可能会灾难性地减少对点的整体分布的评估。

就我们而言，无论大小

$N$ 价值

$D_N ^ *$ 通常由最接近每个极点的四个点定义，特别是

$t_0$ 和

$t_3$ 。但是，关于该网格也已知最大的 Voronoi多边形位于极点。所以试图最大化

$d_N$ 通过连续分割原始极点，我们实际上增加了极点上的空隙！因此，我们提出了网格2的替代方案，它通常是可取的，因为它在极点附近没有显示出如此大的空隙。

它几乎与网格2相同，但是有两个区别。首先，她使用

$\ varepsilon = 11/2$ 在

$1 \ leq i \ leq N-2$ 。其次，除了这些

$N-2$ 第一个和最后一个点位于每个极点。

那就是：

$t_0 =（0,0）; \; t_n =（1,0）; \ quad t_i = \左（\ frac {i + 6} {N + 11}，\ frac {i} {\ phi} \ right）\ quad \ textrm {for} \; 1 \ leq i \ leq N-2 \标签{4}$

这种构造方法的一个令人惊奇的特性是，尽管其创建的动机是希望将两极空隙最小化，但实际上，它是所有方法中的最佳价值

$d_N$ 和

$d ^ *$ 与

$d ^ * = 3.31$ ！

也就是说，

$N = 100$ 第一个坐标的值如下：

$\ {0; \; \ frac {7} {111}，\ frac {8} {111}，\ frac {9} {1111}，\ ldots，\ frac {102} {111}，\ frac {103} {111}，\ frac {104} {111}; \; 1 \}$

图2.各种网格配置。 左侧的标准斐波那契网格。 请注意，即使中间网格

$d_N ^ *$ 好了，在杆子上她有一个明显的空白。 网格3在极点处没有空隙并且具有最佳价值

$d_N ^ *$ 。

比较方式

对于大价值

$N$ 这个值

$d ^ *$ 与其他方法（例如，测地穹顶）具有非常好的可比性，该方法基于柏拉图固体表面到球体表面的三角投影。毫不奇怪，最高质量的测地线圆顶是基于二十面体或十二面体构建的。

基于二十面体的测地线穹顶

$N$ 。

$\ begin {array} {| c | cccccccccc |} \ hline N＆12＆42＆92＆162＆252＆362＆492＆642＆812＆1002 \\ \ hline d ^ *＆3.64＆3.54＆3.34＆3.22 ＆3.15＆3.09＆3.06＆3.03＆3.00＆2.99 \\ \ hline \ end {array}$

基于十二面体的测地线穹顶

$N$ 。

$\ begin {array} {| c | ccccccc |} \ hline N＆20＆32＆122＆272＆482＆752＆1082 \\ \ hline d ^ *＆3.19＆3.63＆3.16＆2.99＆2.90＆2.84＆ 2.81 \\ \ hline \ end {array}$

此外，对应于富勒烯形状的截短二十面体

$C_ {60}$ 只有

$d ^ * = 3.125$ 。

也就是说，

$N> 100$ 基于方程式3的网格比任何测地多面体更好。

根据下面参考列表中第一个来源的数据，一些现代方法通常很复杂，需要递归和/或动态编程，它们具有以下指标。

$\ begin {array} {| lr |} \ hline \ text {Lattice 1}＆3.09 \\ \ hline \ text {Max Determinant}＆3.19 \\ \ hline \ text {Lattice 2}＆3.28 \\ \ hline \文字{Lattice 3}和3.31 \\ \ hline \文字{Zoneal Equal Area}＆3.32 \\ \ hline \文字{Coulomb}＆3.37 \\ \ hline \文字{Log Energy}＆3.37 \\ \ hline \ end {数组}$

第一部分的结论

由等式3创建的网格3是标准斐波那契网格的修改，该网格为点的分布提供了更好的封装。那是

$t_0 =（0,0）; \; \; t_i = \左（\ frac {i + 6} {N + 11}，\ frac {i} {\ phi} \ right）; \; \; t_ {N-1} =（0,1）; \ quad \ textrm {for} \; 1 \ leq i \ leq N-2$

第2节。优化凸包（Delaunay网格）

在上一节中，我们通过

$d ^ * _ N$ 但是，这些修改会使其他指标恶化，例如凸包（Delaunay网格）的体积。本节介绍如何以优化（最大化）诸如凸包的体积之类的更全局指标的方式在球体上均匀分布点。

我们表示

$C_N$ 像凸包

$N$ 点数

$\ epsilon_N = N \左（\ frac {4 \ pi} {3} \;-\ textrm {Vol}（C_N）\右）$

包括归一化因子

$N$ ，因为绝对差异会随着速度降低

$〜1 / N$ 。

举止

$\ epsilon_N$ 在各种

$N$ 可以在图3中看到（蓝线）。

为减少音量不匹配，应注意，尽管使用了

$\ phi$ ，从黄金分割处的逻辑开始

$N \ rightarrow \ infty$ 它并不一定意味着它是最终产品的最佳价值

$N$ 。用科学的话来说，可以说我们需要考虑肢体矫正的影响。

让我们将等式1总结如下：

$t_i = \左（\ frac {i + 1/2} {N}，\ frac {i} {g（N）} \ right）\ quad \ textrm {for} \; 0 \ leq i \ leq N-1 \标签{4}$

我们在哪里定义

$g（n）$ 怎么

$g（n）= \开始{cases} 3- \ phi，＆\文本{如果$ k $是偶数} \\ \ phi，＆\ text {如果$ k $是奇数} \ end {cases} \ tag {5}美$

在哪里

$k = \左\ lfloor \ textrm {log} _ {\ phi}（\ frac {n} {1.5}）\ right \ rfloor = \ left \ lfloor \ frac {\ ln（n / 1.5）} {\ ln \ phi} \对\ rfloor$

在哪里

$\ lfloor x \ rfloor$ -向下舍入到最接近的整数的功能。

图3显示了针对一半的值优化了多少音量失配。

$N$ 。

原因是鲜为人知的事实：所有数字

$x$ 从无理性开始，满足特殊的Mobius变换是等效的

$\ phi$ 。

$x = \ frac {a \ phi + b} {c \ phi + d}，\ quad \ textrm {对于所有整数} \; \; a，b，c，d \; \ textrm {such that} | ad-bc | = 1$

因此，

$\ phi$ 和

$3- \ phi$ 非常适合

$\ frac {1} {\ phi} = \ frac {\ phi + 1} {2 \ phi + 1}，\ quad \ quad \ frac {1} {3- \ phi} = \ frac {2 \ phi + 1} {1 \ phi + 1}$

图3.点的凸包的体积与单位球体的体积之间的不匹配。 请记住，它越小越好。 该图显示了基于

$\ phi$ 和

$3- \ phi$ ，与标准的斐波那契网格（蓝线）相比，点的分布更好。

对于剩下的一半，我们首先定义一个辅助序列

$A_N$ 是斐波那契数列的一种变体

$A_1 = 1，\; A_2 = 4； \; A_ {n + 2} = A_ {n + 1} + A_n \; \ textrm {for} n = 1,2,3，...$

那是

$A_N = 1,4,5,9,14,23,37,60,97,157,254,411，...$

该系列的所有分数均具有优雅的连续分数，在极限范围内收敛到

$\ phi$ 。举个例子

$t _5 / t_4 = 1+ \ cfrac {1} {1+ \ cfrac {1} {1+ \ cfrac {1} {1+ \ cfrac {1} {4}}}}$

现在我们可以完全概括

$g（n）$ 如下：

$g（N）= \开始{cases} 3- \ phi，＆\文本{如果$ k $是偶数} \\ A_ {j + 1} / A_j，＆\文本{如果$ k $是奇数，则$ j =（k + 7）/ 2 $} \结束{cases} \标记{6}$

下表显示了这些值

$g（N）$ 对于各种

$N$ 。

$\ begin {array} {| c | c | c | c | c | c | c | c | c |} \ hline N＆4-6＆7-10＆11-16＆17-26＆27-43＆44- 70＆71-114＆115-184＆185-300 \\ \ hline g（n）＆3- \ phi＆\ frac {23} {14}＆3- \ phi＆\ frac {37} {23}＆3- \ phi＆\ frac {60} {37}＆3- \ phi＆\ frac {97} {60}＆3- \ phi \\ \ hline \ end {array}$

图4显示，相对于凸包的体积，对于所有值，此新分布均优于规范网格

$n$

图4.凸包的体积与单位球体的体积之间的不匹配。 值越低越好。 这告诉我们，所提出的新方法（绿线）始终比标准斐波那契网格（蓝线）提供更好的分布。

图5.规范网格（左）与新的修改网格（右）的视觉比较（n = 35和n = 150）。 在视觉上，差异几乎是无法察觉的。 但是，在要求最大效率的条件下，改进版（右侧）在凸包的体积和表面积方面都提供了很小但可量化的改进。

奇怪的是，这种分布也微不足道，但是稳定地减少了凸包的表面积和单个球体的表面积之间的不匹配。如图6所示。

图5.凸包（Delaunay网格）的表面积与单个球体的表面积之间的面积归一化不匹配。 值越低越好。 这表明，与经典的斐波那契网格（蓝点）相比，拟议的新修改（绿点）显示出表面积差异的微小但持续减小

第2节的结论

对应于等式6的网格是标准Fibonacci网格的修改形式，基于凸包的体积和表面积（Delaunay网格）创建了明显更好的点分布。

资料来源

球上点的均匀分布

引言

第1节。优化包装距离

第2节。优化凸包（Delaunay网格）

More articles: