I've been trying to implement the Lloyd relaxation algorithm into my Voronoi diagram code. I've spent several days researching, and I am unable calculate the centroid of each voronoi polygon. This is due to me either not understanding the various formulas being used or my code lacking the required inputs needed for the calculation.

If someone could help me implement Lloyd's algorithm or explain in VERY simple terms how to calculate the centroid, I would appreciate the help.

NOTE: The voronoi diagram created below wraps around the x-axis.

My code:

from PIL import Image
import random
import math
import numpy as np
import noise
wid = 500
hei = 250
image = Image.new("RGB",(wid,hei))

def generate_voronoi_diagram(width, height, num_cells):
    image = Image.new("RGB", (width, height))
    putpixel = image.putpixel
    imgx, imgy = image.size
    nx = []
    ny = []
    nr = []
    ng = []
    nb = []
    #Go through number of cells
    for i in range(num_cells):
        #creat a point (x,y) and give it a specific color value
        nx.append(random.randrange(imgx))
        ny.append(random.randrange(imgy))
        nr.append(random.randrange(256))
        ng.append(random.randrange(256))
        nb.append(random.randrange(256))
    #go through each pixel in the image
    for y in range(int(imgy)):
        for x in range(int(imgx)):
            dmin = math.hypot(imgx-1, imgy-1)
            j = -1
            #go through each cell
            for i in range(num_cells):
                # d is distance from each voronoi starting point
                # each point gets its coordinates distorted so d also gets distorted
                d = math.hypot(nx[i]-x, ny[i]-y)
                #if distance is less than the current min distance,
                #set that point as the owner of this pixel and the new dmin
                if d < dmin:
                    dmin = d
                    j = i
                d = math.hypot(nx[i]+imgx-x, ny[i]-y)
                #if distance is less than the current min distance,
                #set that point as the owner of this pixel and the new dmin
                if d < dmin:
                    dmin = d
                    j = i
                d = math.hypot(nx[i]-imgx-x, ny[i]-y)
                #if distance is less than the current min distance,
                #set that point as the owner of this pixel and the new dmin
                if d < dmin:
                    dmin = d
                    j = i
            putpixel((x, y), (nr[j], ng[j], nb[j]))
    image.save("Voronoi_example.png", "PNG")
    image.show()
generate_voronoi_diagram(wid, hei, 20)