使用 Lloyd 算法进行锚定分区

Question

我可以使用 Lloyd 算法将多边形划分为 n 个多边形。假设我使用上述算法将下面的多边形分成 5 个多边形，我得到：-

但我想进行锚定分区，这意味着我希望每个子多边形至少包含一个边界点，如下所示：

是否对现有算法进行了修改以帮助我实现该目标？如何保证锚定？

如果您能引用一些现有的 Matlab/python 代码而不是伪代码，那将会很有帮助吗？我在上面使用的代码来自 here，它执行普通的香草实现。

Answer 1

只是一个建议：一个简单的尝试。在正方形上定义一个势函数U(x, y)。 Something like this. 您可以选择参数，使其最小值是一个与正方形内切圆几乎相同的圆。或者随意选择不同的潜力。给定点 p1 = [x1; y1], p1 = [x1; y1], ... pn = [xn; yn]，形成 2 x n 矩阵

P = [p1 p2 ... pn];

设 Lloyd 算法一步的函数为

P_out = LA(P_in)

即给定点 P_in = [p1_in p2_in ... pn_in] 它生成它们的 Voronoi 图，然后计算每个 Voronoi 单元的质心 p1_out, p2_out, ..., pn_out 并将输入点移动到新的输出，质心点 P_out = [p1_out p2_out ... pn_out].
然后你可以沿着电位的负梯度应用重新定位，即

function  P_out = GR(P_in)
   P_out = P_in - gradU(P_in); 
end

其中 GRAD = gradU(P_in) 是为每个 column-vector P_in(:,j) 计算梯度向量并生成梯度的 2 x n 矩阵 GRAD 的函数。

所以你的算法实际上就是合成

P_out = LA(GR(P_in));

也许这些点会偏向正方形的外围，避开中间部分，从而最终让 Voronoi 单元接触到边界？我选择了一个潜在的假设，在这种情况下矢量梯度场是无旋的，所以不会出现某种循环动力学，但该算法将收敛到一些 centroidal 平衡配置（这听起来可信但我不确定那）。

使用 Lloyd 算法进行锚定分区

using Lloyd's algorithm for anchored partitioning

algorithm

geometry

voronoi

polygon

computational-geometry