pythonalgorithmimagegeometryvoronoi

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


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. enter image description here

Here is an example of 50 iterations followed by the 75 iterations: enter image description here

enter image description here

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: enter image description here


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:

    enter image description here

    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.