使用Lloyd算法进行锚定分区

Question

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

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

是否已经对算法进行了修改，可以帮助我实现这一点？如何确保锚定？

如果您可以引用一些现有的Matlab/python代码而不是伪代码，这将非常有用？我在上面使用的代码就是从这里开始的，它执行普通的实现。

Answer 1

只是一个建议：一个简单的尝试。在正方形上定义一个势函数U（x，y）。像这样的。您可以选择参数，使其最小值为一个圆，该圆几乎是内接在正方形中的圆。或者可以自由选择不同的潜力。给定点p1=[x1；y1]，p1=[x1；y1]。。。pn=[xn；yn]，形成2 x n矩阵

P = [p1 p2 ... pn]; 

让Lloyd算法的一步函数是

P_out = LA(P_in)

i、 e.给定点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）是计算每个列向量的梯度向量P_in（：，j）并生成2 x n矩阵梯度的函数。

所以你的算法实际上就是

P_out = LA(GR(P_in));

也许这些点会倾向于广场的外围，避开中间部分，从而最终让沃罗诺伊细胞接触边界？我选择了一个势，假设在这种情况下矢量梯度场是不旋转的，所以不会有某种循环动力学出现，但是算法会收敛到某种十六向平衡构型（听起来可信，但我不确定）。