在最小距离约束下最大化多边形内点数的算法

Question

问题：

给定一个充当边界或约束的不规则多边形，我的目标是在该多边形内添加尽可能多的点，但这些点必须彼此保持最小距离。所以有一些具体的要求：

1. 这些点需要位于多边形内部，
2. 每个点之间必须有最小间距，
3. 理想情况下，点应排列在有序网格中，以最大化点数。

在寻找问题的解决方案时，我已经遇到了一些聚类算法，例如 K-Means，用作解决问题的启发式算法。然而，这些方法似乎并没有完全解决我的场景的独特限制。

问题：

1. 是否存在现有算法可以更恰当地满足这些特定要求？
2. 如果没有，是否有替代方法可以帮助在这样一个受限且不规则的空间内实现近乎最佳的点排列？

任何建议、经验或相关资源或案例研究的指示将不胜感激。谢谢！

Answer 1

可以围绕关键字“快速泊松盘采样”进行搜索。

下一步是将其推广到多边形域（不仅仅是矩形）。经过一番谷歌搜索后，我找到了：“Efficient Maximal Poisson-Disk Sampling”，Ebeida 等人。 （https://escholarship.org/content/qt8xv0237z/qt8xv0237z.pdf?t=ptt40r）。参见图 1，他们能够在相当复杂的域（非凸）上执行算法。