我目前正在研究一个将 2D 点集修改作为子问题的项目。点集本身将包含几个点簇，我需要以某种方式将它们彼此分开，然后在它们的簇壳内放松它们的点。或者，获取集群的外壳点并将它们用作域并在其中分布（大致）均匀间隔的点就足够了。所以可以跳过放松。作为最坏的情况，我需要处理几个点集，包括约 100k 个顶点，因此使用的算法应该很快。我知道这个主题的复杂性，这就是为什么我不想重新发明轮子，而是尽可能使用现有代码。到目前为止，我发现了以下内容：
用于点集松弛：Fortunes/Sullivans “Sweep Line”算法：据说是最快的单线程voronoi 图构造器。然而，代码似乎很难扩展，并且默认情况下可提取的信息不包含 voronoi 单元外壳数据（它们的顶点位置），至少需要计算质心并进行下一次松弛迭代。此外，矩形以外的任何域都将不可用。
CVT：一组用于创建 voronoi 图的多功能库。它支持点的松弛，也支持用户指定区域内的点集。
CGAL：具有基本 MP 支持的广泛框架，但显然没有集成的松弛方法。我需要为每个点集子集群创建一个 delaunay 三角剖分，并将其提供给一个 voronoi 适配器，然后给我提供迭代器来查询 voronoi 细胞外壳数据以进一步放松。就我通过文档而言，它应该支持域（几千页:)
还有一些，例如 Voro++，它似乎主要在 3D 中工作；三角形，它使用区域约束从给定域创建 delaunay 三角剖分，以便可以使用三角形顶点作为结果点。
好的，目前在我看来，CVT 应该满足我的需求，同时保持这一切都非常简单。但我不确定，所以问题是：有没有人有过点集松弛实施的经验，最好是使用域？哪些现有代码更可取？
谢谢毛皮建议！t