Building a circle pixel by pixel in a iteration style for a voronoi diagram using the incremental neighborhood method

Question

As mentioned above, I'm trying to create a Voronoi diagram in an image using the incremental neighborhood method, which consists of given n random points (which will be a pixel), I paint its neighbors for each point. Then these new neighborhood neighbors until the image is filled. The problem that I am currently facing is that the regions are completely messed up. What I can guess is if I check all the neighbors of a given point, it will end up building a square, and not a circle, so the distance for any point will not be the euclidian distance. I would like to know how I could check and create the neighbors so I draw the distance in a euclidian distance properly given that I don't want to calculate the distance between every pixel to the random points since that would be slow.

I tried using a method that I only check for the diagonals of a pixel each odd iteration, which gives me a bit more of a circular shape, but not quite right.

This is what the current code is doing.

Here is an example of 50 iterations followed by the 75 iterations:

The code I'm using is the following, only the part that is used to create the regions is present, I later use this map to generate the image correctly

def createVoronoiIncremental(im, numPoints, param):
y, x, z = im.shape
points = []

count = 0
while count < numPoints:
    px = np.random.randint(0,x)
    py = np.random.randint(0,y)
    if not inPoints(np.array([px,py]), points):
        points.append(np.array([px,py]))
        count += 1

points = np.array(points)

mapPoint = {}
mapDist = {}

for i, col in enumerate(im):
        for j, row in enumerate(col):
            mapPoint[(j, i)] = -1 # white pixels
            mapDist[(j, i)] = y*x # white pixels


groups = {}
groups[-1] = (0,0,0)
outer = {}
count = 0
for point in points:
    i = point[1]
    j = point[0]
    mapPoint[(j, i)] = count # colored by group pixels
    mapDist[(j, i)] = 0
    outer[(j, i)] = [np.array([j, i])]
    groups[count] = (np.random.randint(0,255),np.random.randint(0,255),np.random.randint(0,255))
    count += 1

isNeighbour = True
count = 0
while isNeighbour:
    isNeighbour = False
    for point in points:
        outerPoints = outer[(point[0], point[1])].copy()
        newOuterPoints = []
        for p in outerPoints:
            n, mapPoint = neightbours(p, mapPoint, mapDist, (x,y), count)
            for neighbour in n:
                newOuterPoints.append(neighbour)
        outer[(point[0], point[1])] = newOuterPoints
        if len(newOuterPoints) != 0:
            isNeighbour = True
    count += 1
    if count > param:
        break


        

return mapPoint

And this is how I define the neighborhood:

def neightbours(points, mapPoint, size, count):
neightbours = []

potentialNeighbours = []

if type(points) != 'numpy.ndarray':
    x = points[0]
    y = points[1]

    #vizinhos superiores
    if x-1 >= 0 and y+1 < size[1]:# and count%2 != 0:
        potentialNeighbours.append(np.array([x-1,y+1]))
    if y+1 < size[1]:
        potentialNeighbours.append(np.array([x  ,y+1]))
    if x+1 < size[0] and y+1 < size[1]:#  and count%2 != 0:
        potentialNeighbours.append(np.array([x+1,y+1]))

    #visinhos laterais
    if x-1 >= 0:
        potentialNeighbours.append(np.array([x-1,y]))
    if x+1 < size[0]:
        potentialNeighbours.append(np.array([x+1,y]))

    #vizinhos inferiores
    if x-1 >= 0 and y-1 >= 0:#  and count%2 != 0:
        potentialNeighbours.append(np.array([x-1,y-1]))
    if y-1 >= 0:
        potentialNeighbours.append(np.array([x  ,y-1]))
    if x+1 < size[0] and y-1 >= 0:#  and count%2 != 0:
        potentialNeighbours.append(np.array([x+1,y-1]))

    for potentialNeighbour in potentialNeighbours:
        if mapPoint[(potentialNeighbour[0], potentialNeighbour[1])] == -1: #white pixel
            mapPoint[(potentialNeighbour[0], potentialNeighbour[1])] = mapPoint[(x,y)]
            neightbours.append(potentialNeighbour)
else:
    for point in points:
        x = point[0]
        y = point[1]

        #vizinhos superiores
        if x-1 >= 0 and y+1 < size[1]:# and count%2 != 0:
            potentialNeighbours.append(np.array([x-1,y+1]))
        if y+1 < size[1]:
            potentialNeighbours.append(np.array([x  ,y+1]))
        if x+1 < size[0] and y+1 < size[1]:#  and count%2 != 0:
            potentialNeighbours.append(np.array([x+1,y+1]))

        #visinhos laterais
        if x-1 >= 0:
            potentialNeighbours.append(np.array([x-1,y]))
        if x+1 < size[0]:
            potentialNeighbours.append(np.array([x+1,y]))

        #vizinhos inferiores
        if x-1 >= 0 and y-1 >= 0:#  and count%2 != 0:
            potentialNeighbours.append(np.array([x-1,y-1]))
        if y-1 >= 0:
            potentialNeighbours.append(np.array([x  ,y-1]))
        if x+1 < size[0] and y-1 >= 0:#  and count%2 != 0:
            potentialNeighbours.append(np.array([x+1,y-1]))

        for potentialNeighbour in potentialNeighbours:
            if mapPoint[(potentialNeighbour[0], potentialNeighbour[1])] == -1: #white pixel
                mapPoint[(potentialNeighbour[0], potentialNeighbour[1])] = mapPoint[(x,y)]
                neightbours.append(potentialNeighbour)
                

return neightbours, mapPoint

SOLUTION:

Using the Bresenham’s circle drawing algorithm and the answer given in this other question: Given a image, a pixel point and a radious in pixels. How do I find the pixel coordenate of the circle border it creates

Incrementing the circle radious and checking if the points are drawn or not you can create the voronoi diagramam effect:

Answer 1

Using the Bresenham’s circle drawing algorithm and the answer given in this other question: Given a image, a pixel point and a radious in pixels. How do I find the pixel coordenate of the circle border it creates

Incrementing the circle radious and checking if the points are drawn or not you can create the voronoi diagramam effect:

This solved for what I wanted, but in the end this method still lacks a lot, since the edges between areas are not clean as they should be.

Answer 2

I would do this a completely different way, using a priority queue:

1. Let pq be priority queue of tuples (dist, center, x, y), where (x,y) is a point that might be drawn in the neighborhood of center center, and dist is the squared distance from the point to the center, i.e., (x-center.x)² + (y-center.y)². The priority queue must sort in order of increasing dist.
2. For each center c, add (0, c, c.x, c.y) to pq
3. Take the tuple (dist, center, x, y) with the smallest dist from the queue. If (x,y) isn't already colored, then color it for center and add its uncolored neighbors to the queue with the correct dist.
4. Repeat step (3) until pq is empty.

This way you don't have to worry about how to draw circles or how to find the pixels at a given distance, or any of that.

If you want to see partial results, with all pixels up to radius r filled, then you just stop when dist > r*r.