Search code examples
algorithmgeometrypolygoncomputational-geometryvoronoi

using Lloyd's algorithm for anchored partitioning

I can use Lloyd's algorithm to partition a polygon into n polygons. Suppose I divided the polygon below into 5 polygons using the above algorithm and I get this:-

enter image description here

But I wanted to do anchored partitioning meaning I wanted each sub-polygon to include at least one boundary point like this:

enter image description here

Are there modifications to the algorithm already available that can help me achieve that? How to ensure anchoring?

It would be very helpful if you could cite some existing Matlab/python codes rather than pseudocode? The code I used for above is from here which does the plain vanilla implementation.

Solution

  • Just a suggestion: A simple attempt. Define a potential function U(x, y) on the square. Something like this. You can choose the parameters so that its minimum is a circle that is almost the circle inscribed in the square. Or feel free to choose a different potential. Given the points p1 = [x1; y1], p1 = [x1; y1], ... pn = [xn; yn], forming the 2 x n matrix

    P = [p1 p2 ... pn];

    let the function for one step of Lloyd's algorithm be 

    P_out = LA(P_in)

    i.e. given the points P_in = [p1_in p2_in ... pn_in] it generates their Voronoi diagram, then calculates the centroids of each Voronoi cell p1_out, p2_out, ..., pn_out and moves the input points to the new output, centroid points P_out = [p1_out p2_out ... pn_out].
    Then you can apply a repositioning along the minus gradient of the potential, i.e. 

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

    where GRAD = gradU(P_in) is the function that calculates the gradient vectors for each column-vector P_in(:,j) and produces the 2 x n matrix GRAD of gradients.

    So your algorithm will actually be the composition

    P_out = LA(GR(P_in));

    Maybe then the points will favor the periphery of the square, avoiding the middle part and thus will eventually have Voronoi cells touching the boundary? I chose a potential with the assumption that in this case the vector gradient field is irrotational, so there will not be some kind of circulating dynamics emerging, but the algorithm will converge to some cetntroidal equilibrium configuration (it sound believable but I am not sure about that).