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:
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.