我给了一个随机的形状，其中我想放置4个（或任何其他数字）点。这些点应该是分布的，所以它们的Voronoi-Diagram的所有区域都有相同的面积大小，并有可能的最大面积大小。我想找到一个可以在Python中实现的算法，有什么想法可以开始吗？
该算法应该找到发现一个房间的无人机群的最佳分布。
一个很自然的方法是选择一些任意的起点，并应用 "随机点"。劳埃德算法 反复移动站点到它们的Voronoi中心。它并不能保证得到最佳配置，但一般来说，在几步内就能得到一个很好的（近乎局部最优的）配置。
实际上，代码中最丑陋的部分是将Voronoi单元限制在多边形域内。参见讨论 此处 和 此处 在这个问题的其他重复中。
这里有一个替代方案，也许更容易快速实现。栅格化 您的多边形域，计算多边形内部的有限点集。现在运行 k-means聚类 这只是Lloyd法的离散变体（也是 在scipy)来寻找你的位置。这样一来，你就避免了修剪无限Voronoi单元的努力，而只需要依靠对输入多边形的几何内外测试来进行光栅化。这样做的结果有一个明显的精度与性能的权衡：你把域离散得越细，需要的时间就越长。但在实践中，绝大多数的好处（得到一个合理平衡的分割）都来自于粗略的近似和仅仅几个聚类迭代。
最后，如果你需要使用测地距离，不允许站点直接看到域的非角周围，那么实现起来就复杂多了。(例如，见图2a 此处.)