生成均匀间隔网格的算法

Question

我正在寻找用于创建均匀间隔网格的通用算法，我很惊讶找到它的难度!这是一个很好解决的问题，我不知道它的名字吗？或者这是一个 Unresolved 问题，最好由自组织映射来解决？

更具体地说，我试图在二维笛卡尔平面上制作一个网格，其中每个点和 4 条边界线(或“墙”以构成边界框)之间的欧几里德距离相等或几乎相等。对于正方形数字，这就像在边界框的中心制作一个具有 sqrt(n) 行和 sqrt(n) 列且间距相等的网格一样简单。对于 5 个点，图案可能是圆形或中间有一个点的 4 个点。

我没有找到一个很好的解决方案，所以我很遗憾地把这个问题搁置一旁，并使用一个生成以下网格的快速函数来解决:

Answer 1

这个问题没有简单的通用解决方案。自组织映射可能是最佳选择之一。

解决此问题的另一种方法是将这些点想象成相互排斥并且也被墙壁排斥的粒子。作为初始安排，您已经可以将点平均分配到下一个较小的平方数 - 为此您已经有了解决方案。然后随机添加剩余的点数。

迭代修改位置以根据粒子和壁之间的总力最小化能量函数。结果当然取决于力定律，即力如何取决于距离。

要解决这个问题，您可以使用 FEM 等数值方法。

基于相同原理的一种简化且效率较低的方法是首先根据您可以计算的平方数情况设置估计的最小距离。然后多次遍历所有点，并为每个点计算与其最近邻居的距离。如果这小于估计距离，则将您的点向相反方向移动一定比例的差异。

此方法通常不会导致稳定的最小值，但应该在多次迭代后找到可接受的解决方案。您将不得不试验步长和迭代次数。

总而言之，您有三个选择:

• FEM 方法:高效但难以实现

• 自组织映射:效率稍低，实现复杂度中等。

• 上一节中描述的迭代:效率较低但易于实现。