computational-geometry - 如何定期用点填充多边形？

Question

填充矩形很简单：只需制作一些网格。但是，如果多边形是无条件的，那么任务就变得不那么简单了。
可能“定期”可以表述为彼此点之间的距离为：R ± alpha。但我不确定这一点。
也许有一些已知的算法可以实现这一点。
补充：
我需要生成网，没有大洞，也没有大的点聚集。

Answer 1

您是否考虑过使用点的力导向布局？

在多边形的边界框上随机散布一些点，然后重复应用两个简单的规则来调整它们的位置：

1. 如果一个点在多边形之外，将它移动到最小可能的距离，使其位于其中，即：到多边形边缘上最近的点。
2. 点以与它们之间的距离成反比的力相互排斥，即：对于每个点，考虑每隔一个点并计算将两个点直接分开的排斥向量。向量对于近点应该大，对于远点应该小。对向量求和并添加到点的位置。

经过多次迭代后，点应稳定在多边形区域上均匀分布的稳定状态。达到这种状态的速度取决于多边形的几何形状以及您如何缩放点之间的排斥力。

Answer 2

您可以计算多边形的约束 Delaunay 三角剖分并使用 Delaunay 细化算法（使用此关键字搜索）。

我最近在 Fade2D 库http://www.geom.at/fade2d/html/中实现了细化。它采用没有自相交的任意多边形以及每个所得三角形的外接圆半径的上限。当前版本 1.02 中尚未包含此功能，但如果您想尝试，我可以为 Linux 或 Win64 编译当前开发版本。