在2024年，一组九位数学家发布了一份近1000页的证明，证明了几何朗兰兹猜想。这是纯数学的一项伟大成就，而我已经接受自己将永远无法理解他们所证明的甚至是声明，更不用说证明本身。在光谱的另一端，2007年，罗伯特·布里德森发表了一篇一页的论文，引用近1000次，并且在10分钟内可以完全理解。它给出了一个简单的解决方案，解决了计算机图形和模拟中常见的问题：随机放置事物，但不能太靠近。假设你正在尝试程序性生成一片森林，并需要一种放置树木的方法。普通随机采样的问题是不言而喻的：一些树木会重叠！我们需要能够在任何两棵树之间设置最小距离。遵循这一规则的树木分布称为泊松圆盘分布。我们可以尝试一个简单的拒绝采样方法，通过投掷随机的飞镖并拒绝任何在任何其他点的最小距离内的点，但没有一个更聪明的数据结构，对于每个样本检查碰撞需要线性时间，并且拒绝率很快接近1。布里德森的算法为我们提供了一种高效的方法来做到这一点。布里德森算法假设所需的点之间的最小距离为rr，我们在dd维空间中工作。布里德森算法如下：将空间划分为边长为rd√dr的网格。这确保每个网格单元最多只能有一个点。初始化一个列表active，随机均匀选取一个点。只要active不为空：从active中均匀随机选择一个元素pp。在以pp为中心、内半径为rr和外半径为2r的环形区域中，均匀采样最多kk次。如果找到有效的泊松圆盘样本，利用网格进行有效的碰撞检测，将其添加到active中，并选择一个新点pp。如果在kk次尝试中未找到有效点，则从active中移除pp。布里德森建议设置k=30。均匀采样环形区域的最简单方法是生成一个随机单位向量v∈Rd和一个均匀选择的数字x，区间为[12d,1)，然后最终样本为2rx1/d⋅v。几年前，我制作了一段解释为什么这有效的视频。在二维中，选择单位向量等价于选择一个角度θ∈[0,2π)。在更高的维度中，你可以对每个分量进行从正态分布中采样的归一化向量。改进我发现有两个简单的改进，可以大大减少生成相同数量点所需的迭代次数。第一个适用于二维，但第二个也适用于更高维度。我们先从二维改进开始。考虑算法放置一个点pp，然后采样它的环形区域以获取一个新点qq。我们将pp称为qq的父点。这些点之间的关系存储了有价值的信息。当我们不可避免地采样以qq为中心的环形区域时，有一个范围的角度我们不需要考虑，因为这些角度内的点将离pp太近。该范围由以下图形中的虚线表示。pq | p - q | = 1.50 r虽然视觉直观易于理解，但将其转化为公式是一个繁琐的三角学练习。我将省略细节，并在没有证明的情况下声称，被虚线所包围的锥体是以角度α为中心，宽度为2β，其中α=atan2(py−qy,px−qx)，β=min(arccos(|p−q|^2+3r^24r⋅|p−q|),arccos(|p−q|/2r))。实施这个只需要存储每个点的父点。然后，您可以计算锥体的角度并生成下一个样本的角度θ在锥体外的范围内。以下图显示了布里德森算法在优化前后生成的点数。每个数据点是100个三...