等同于仅使用 Delaunay 三角剖分的 Lloyd 算法
Equivalent to Lloyd's algorithm using solelly the Delaunay triangulation
我正在尝试开发一个程序，其中在 2D space 中，一组随机点使用 Delaunay 三角剖分生成图形。
对于这部分，有大量的算法可以做到这一点。
我要实现的第二部分包括对点进行松弛，即允许它们在 2D 中移动 space 以便彼此之间的距离相等。
我知道对于 Voronoi 图（Delaunay 三角剖分的对偶图），Lloyd 算法可以执行该任务，但我似乎找不到任何类型的独立于此图结构的算法（我不会除了这个松弛步骤之外，确实需要计算。
关于我需要的算法类型的任何提示？
提前致谢！
您可以尝试加权 delaunay 三角剖分。首先计算法线 delaunay 三角剖分和每个三角形的重心。然后使用第一个三角剖分的权重计算加权 delaunay 三角剖分。它有助于平滑网格。
如果您已经可以访问 Delaunay 三角剖分，那么您也可以隐含地获得 Voronoi 图的表示。
例如，三角剖分中给定顶点 xi 周围的 Voronoi 单元是连接与 xi 相邻的三角形的外心的（凸）多边形。
要实施 Lloyd 算法，需要将每个顶点移动到其关联的 Voronoi 多边形的质心，重新计算 Delaunay 三角剖分，并继续直到达到收敛。
我正在尝试开发一个程序，其中在 2D space 中，一组随机点使用 Delaunay 三角剖分生成图形。
对于这部分，有大量的算法可以做到这一点。
我要实现的第二部分包括对点进行松弛，即允许它们在 2D 中移动 space 以便彼此之间的距离相等。
我知道对于 Voronoi 图（Delaunay 三角剖分的对偶图），Lloyd 算法可以执行该任务，但我似乎找不到任何类型的独立于此图结构的算法（我不会除了这个松弛步骤之外，确实需要计算。
关于我需要的算法类型的任何提示？
提前致谢！
您可以尝试加权 delaunay 三角剖分。首先计算法线 delaunay 三角剖分和每个三角形的重心。然后使用第一个三角剖分的权重计算加权 delaunay 三角剖分。它有助于平滑网格。
如果您已经可以访问 Delaunay 三角剖分，那么您也可以隐含地获得 Voronoi 图的表示。
例如，三角剖分中给定顶点 xi 周围的 Voronoi 单元是连接与 xi 相邻的三角形的外心的（凸）多边形。
要实施 Lloyd 算法，需要将每个顶点移动到其关联的 Voronoi 多边形的质心，重新计算 Delaunay 三角剖分，并继续直到达到收敛。