查找给定形状中的4个点的分布，以便Voronoi图的区域具有相同且最大的大小

作者: 只怕再见是故人
发布时间: 2025-02-05 12:07:36 (4天前)

2 条回复

1#
回复此人
春风助手 | 2020-08-23 14-42

一种自然的方法是选择一些任意的起点，然后应用劳埃德（Lloyd）算法将站点重复移动到其Voronoi中心。不能保证获得最佳配置，但是通常只需几个步骤就可以提供非常好的（几乎是局部最佳的）配置。实际上，代码中最丑陋的部分是将Voronoi细胞限制在多边形区域内。在此问题的其他重复项中，请参见此处https://stackoverflow.com/questions/59754658/voronoi-regions 和此处https://stackoverflow.com/questions/57471445/how-to-find-intersection-points-of-overhanging-lines-of-voronoi-diagram-intersec 的讨论。这是一个可能更容易快速实施的替代方法。栅格化多边形域，计算多边形内的有限点集。现在运行k-means聚类，这只是劳埃德方法的离散变体（也是scipy）来找到您的位置。这样，您就无需修剪修剪无限的Voronoi像元，而只需要对输入面进行几何内外测试即可进行栅格化。结果具有明显的准确性-性能折衷：离散化域越精细，花费的时间就越长。但是在实践中，绝大多数好处（获得合理平衡的分区）都带有一个粗略的近似值和一些聚类迭代。最后，如果您需要使用测地距离（不允许站点直接在域的非角附近看到），则实施起来要复杂得多。（例如，请参见此处的图2a 。）https://groups.csail.mit.edu/drl/wiki/images/a/ac/NonConvexVoronoiCoverage_ICRA10.pdf

编辑

登录后才能参与评论