在 Delaunay 三角剖分中重新定位点
Relocate points in Delaunay triangulation
我刚刚完成了 Delaunay 增量翻转算法的实现。该算法的时间复杂度为O(N log N).
算法的应用是以每个点作为电话公司的天线。使用 Delaunay 算法，我必须用这些点对 space 进行三角剖分，然后使用三角剖分生成 Voronoi 图，其中每个 Voronoi 多边形代表每个天线的覆盖范围
现在，我必须解决以下问题：
For each given point, and a constant d, relocate all the points in the plane, without exceeding the distance d from the original coordinates of each point, so that the Voronoi regions are maximized.
我无法想象如何用高效的算法来解决这个问题。 Delaunay 和 Voronoi 的算法已经实现。
谢谢！
你可以试试劳埃德算法。为每个站点计算重心并将其与您的旧站点进行比较。如果距离不超过常量 d，则重新定位站点，否则什么都不做。重新对站点进行三角测量以使网格平滑。
我刚刚完成了 Delaunay 增量翻转算法的实现。该算法的时间复杂度为O(N log N).
算法的应用是以每个点作为电话公司的天线。使用 Delaunay 算法，我必须用这些点对 space 进行三角剖分，然后使用三角剖分生成 Voronoi 图，其中每个 Voronoi 多边形代表每个天线的覆盖范围
现在，我必须解决以下问题：
For each given point, and a constant
d, relocate all the points in the plane, without exceeding the distance d from the original coordinates of each point, so that the Voronoi regions are maximized.
我无法想象如何用高效的算法来解决这个问题。 Delaunay 和 Voronoi 的算法已经实现。
谢谢！
你可以试试劳埃德算法。为每个站点计算重心并将其与您的旧站点进行比较。如果距离不超过常量 d，则重新定位站点，否则什么都不做。重新对站点进行三角测量以使网格平滑。