均衡各种多边形随机镶嵌面积的算法

计算科学 优化 计算几何 图论 约束优化
2021-12-06 01:02:20

我正在寻找一种算法,我可以申请随机镶嵌具有不同区域的多边形。该算法可以将多边形的几何形状放松到所有多边形都具有相同面积的条件!

应该有人遇到过这个问题。最简单的情况是所有多边形都具有相同数量的边。在这种情况下,可以找到外围和区域之间的关系。但是,该算法应该适用于具有不同边数的多边形的一般情况。

如果你们能给我一些提示或将我链接到在此处输入图像描述图、计算几何和数学领域可能存在的一些相关研究,我将不胜感激。

1个回答

可以使用相当简单的劳埃德算法来实现这一点。

该算法的本质是从一组点和距离度量定义的给定镶嵌开始。

然后将这些点移动到质心,从而重新计算曲面细分和区域。然后重复这个迭代过程,直到移动足够小。如果您熟悉统计/分类中的 k-means 聚类,则本质上是相同的过程。