We will now draw a Voronoi diagram. Voronoi diagrams are a simple yet very powerful tool used in modeling lots of physical systems. Wikipedia (https://en.wikipedia.org/wiki/Voronoi_diagram#Applications)  lists more than 20 disciplines of science and technology where Voronoi diagrams are used to model and solve real-world problems. 

There are many little variations to the rules for drawing Voronoi diagrams,  but the most common type of Voronoi diagram is made by choosing a finite number of points on a 2D plane. We call these points the seeds or the attractors. The tiny blue dots shown in the following image are attractor points.  We then map or attach all the points on the plane to their nearest attractor point. All points closer to a particular attractor point is drawn in one color, which partitions the plane into what are called Voronoi cells, as shown in the following diagram:

Voronoi diagrams can be drawn in spaces of arbitrary dimensions, but we stick to studying them in a two-dimensional plane. 

There are many efficient but complicated algorithms for drawing Voronoi diagrams. However, we will use the simplest algorithm to understand. However, being simple comes at a cost. The algorithm requires more time to compute when compared to other faster but more complex algorithms.

We will begin by creating a fixed number of random attractor points on a canvas of given width and height. Accordingly, we define three variables in the program (8.09_vornoi_diagram.py):

width = 800
height = 500
number_of_attractor_points = 125

Next, we create a canvas on a Tkinter root window with the preceding width and height and pass the canvas to a method named generate_vornoi_diagram, which does all the processing and drawing for us. Its code is as follows:

def create_voronoi_diagram(canvas, w, h, number_of_attractor_points):
  attractor_points = []
  colors = []
  for i in range(number_of_attractor_points):
    attractor_points.append((random.randrange(w), random.randrange(h)))
    colors.append('#%02x%02x%02x' % (random.randrange(256),
                                     random.randrange(256),
                                     random.randrange(256)))
  for y in range(h):
    for x in range(w):
      minimum_distance = math.hypot(w , h )
      index_of_nearest_attractor = -1
      for i in range(number_of_attractor_points):
        distance = math.hypot(attractor_points[i][0] - x, 
          attractor_points[i][1] - y)
        if distance < minimum_distance:
          minimum_distance = distance
          index_of_nearest_attractor = i
      canvas.create_rectangle([x, y, x, y], 
        fill=colors[index_of_neasrest_attractor], width=0)
  for point in attractor_points:
    x, y = point
    dot = [x - 1, y - 1, x + 1, y + 1]
    canvas.create_rectangle(dot, fill='blue', width=1)

Here's a brief description of the preceding code:

• We begin by creating two lists. The first for loop is used to populate the attractor_points list with tuples (x, y) for each of the attractor points. We also create another list, colors, which holds the random color hexadecimal string for the cell of each attractor point.
• The second triple nested for loops goes through each pixel on the canvas and finds the index of the nearest attractor. Once that has been established, it colors the individual pixel using the color assigned to that attractor point.
• The last for loop then draws an overlapping blue colored square for each of the attractor points. This loop is deliberately run last to ensure that the attractor point draws over the colored cell region.

Since the preceding code has to go through three nested loops for checking each x,y location on the plane against each attractor point, it has a computational complexity of O(n³) as per Big-O notation. This means that the algorithm is not at all scalable to drawing images of larger sizes and explains why this code takes some time to generate the Voronoi diagram, even for this modest-sized image. More efficient algorithms are available and if you do not want to reinvent the wheel, you can even use the Voronoi class from the scipy.spatial module to implement this much faster. That is left as an exercise for you to explore.

This concludes the section. If you now run the 8.09_vornoi_diagram.py program, it should generate a Voronoi diagram.