*Tags:*programming numpy python mathematics

While solving problem for day-06 of **Advent of Code-2018**, I happend to compute voronoi diagram.

## Voronoi Diagram

voronoi diagram is an interesting partitioning scheme where we divide a plane into various
regions that is created by taking distance to **fixed points** lying in the same plane. Using the resulting regions, we can find to which
point (out of fixed points) an arbitarily chosen point is nearest to.

In terms of *field*, think of it as region where the fixed points have influence on to any other point on the plane.

### Approach for Constructing Voronoi Diagram

**plane generation**

Say we have a **n** 2d points, named **coords** as:

```
[(x1, y1), (x2, y2), ... (xn, yn)]
```

Now, we construct a plane that consists of integer locations (where 2d points reside). We simulate this by actually creating
a list of points starting from **(0, 0), (0, 1), …. (1, 0), (1, 1), (1, 2),..** to (a, b).

This is done by creating cross product between two lists of Xs and Ys.

Say, we have:
`xx = [0, 1, 2, 3]`

and `yy = [0, 1]`

.
So, we generate every possible points on the plane using cross-product between xx and yy. The resulting matrix is:

[

0 0

0 1

1 0

1 1

2 0

2 1

3 0

3 1

]

So, we generate every possible points on the plane of size (width, height) which should generate **width X height** number of points on
the plane.

Remember, this plane covers our initial n **fixed points** mentioned at the start.

Following code generates the points on the plane:

```
coord_matrix = np.array(coords)
X, Y = zip(*coords)
w, h = width, height
xx = list(range(w))
yy = list(range(h))
mat = np.array(list(itertools.product(xx, yy)))
```

Here, `coord_matrix`

is a matrix of size **nX2** and `mat`

is the matrix of size **(width X height, 2)**.

`itertools`

module is used to find the cross product.

**Distance Matrix**

Now, we compute the distance of every point on the plane to the **n** fixed points on the plane.
That is: for every point in **mat**, we find distance to all the points in `coord_matrix`

.

The distance can be any metric like:

For simplicity, here we use manhattan.

```
distances = manhattan_distances(mat, coord_matrix)
```

Here, `distances`

matrix is of size **( widthXheight, n)**

We make use of `sklearn`

for computing the distances:

```
from sklearn.metrics.pairwise import manhattan_distances
```

**computing nearest point**

Using `distances`

matrix, we just find the **fixed point** that is nearest. So, for each row in `distances`

we use arg min to
find the index to the nearest fixed point.

```
dist_min_idx = np.argmin(distances, axis=1)
```

**creating regions**

This is the main part where we create regions in the plane by making use of `dist_min_idx`

.

So, we create a 2d array that represent the whole plane and consists of all the points in **mat**.

```
arr = np.zeros((w, h))
```

Then, we loop through each row in **mat**. This is basically iterating over every point in the plane.

```
for i, p in enumerate(mat):
r, c = p
idx = dist_min_idx[i]
dist = distances[i]
mn = np.min(dist)
arr[r, c] = dist_min_idx[i]
```

Here, we are accessing every location in the plane and then for each location we are simply assigning the index of nearest fixed point.

Finally, we plot the 2d array using matplotlib:

```
plt.imshow(arr)
plt.show()
```

This gives us voronoi diagram like this:

**Note**

The list of 2d points used for generating this voronoi diagram can be found here