Plotting Voronoi diagram

Showcase
1

I thought I’d post the code on how to plot voronoi diagrams using bokeh plots, since it has many use cases.

from scipy.spatial import Voronoi

    def get_voronoi(coord_x, coord_y):
        points = list(zip(coord_x, coord_y))
        #Get Voronoi points
        vor = Voronoi(points) 

        x_patch, y_patch = [], []
        x1_patch, y1_patch = [], []
# The Voronoi has 2 parts. The actual patches and the unbounded lines (that run  #indefinitely) 
        for region in vor.regions:
            if not -1 in region:
                x1_patch, y1_patch = [], []
                for i in region:
                    x1_patch.append(vor.vertices[i][0])
                    y1_patch.append(vor.vertices[i][1])

            x_patch.append(np.array(x1_patch))
            y_patch.append(np.array(y1_patch))

#This code that gets the multi lines that run indefinitely
        center = vor.points.mean(axis=0)
        ptp_bound = vor.points.ptp(axis=0)

        line_segments = []
        for pointidx, simplex in zip(vor.ridge_points, vor.ridge_vertices):
            simplex = np.asarray(simplex)
            if np.any(simplex < 0):
                i = simplex[simplex >= 0][0]  # finite end Voronoi vertex

                t = vor.points[pointidx[1]] - vor.points[pointidx[0]]  # tangent
                t /= np.linalg.norm(t)
                n = np.array([-t[1], t[0]])  # normal

                midpoint = vor.points[pointidx].mean(axis=0)
                direction = np.sign(np.dot(midpoint - center, n)) * n
                far_point = vor.vertices[i] + direction * ptp_bound.max()

                line_segments.append([(vor.vertices[i, 0], vor.vertices[i, 1]),
                                      (far_point[0], far_point[1])])

        x_vor_ls, y_vor_ls = [], []
        for region in line_segments:

            x1, y1 = [], []
            for i in region:
                x1.append(i[0])
                y1.append(i[1])

            x_vor_ls.append(np.array(x1))
            y_vor_ls.append(np.array(y1))

#Removing patches that were added multiple times. 
        x_patch = list(OrderedDict((tuple(x), x) for x in x_patch).values())
        y_patch = list(OrderedDict((tuple(x), x) for x in y_patch).values())
        x_vor_ls = list(OrderedDict((tuple(x), x) for x in x_vor_ls).values())
        y_vor_ls = list(OrderedDict((tuple(x), x) for x in y_vor_ls).values())

        return x_patch, y_patch, x_vor_ls, y_vor_ls

x_patch, y_patch, x_vor_ls, y_vor_ls = get_voronoi(coord_x, coord_y)

source_vor = ColumnDataSource(dict(xs=x_patch, ys=y_patch))
source_vor_ls = ColumnDataSource(dict(xs=x_vor_ls, ys=y_vor_ls))

#plot patches for the Voronoi
glyph_vor = plot.patches('xs', 'ys', source=source_vor, alpha=0.3, line_width=1, fill_color='dodgerblue', line_color='black')

#plot the boundary lines
glyph_ls = plot.multi_line('xs', 'ys', source=source_vor_ls, alpha=1, line_width=1, line_color='black')

image
image1514×808 157 KB

(blue color are the patches and the lines that surround white areas are the multi lines.)

Hope it helps :slight_smile:

4 Likes
2

This is great! Two things might be nice, if you are interested:

  • Adding a patches_from_voronoi helper function to the library somehwere. (It could accept the output of Voronoi to avoid a dependency on Scipy)

  • Adding an voronoi.py example shows off the above

1 Like
3

Shall I add them to examples/reference/models/ ?

Would a ipynb be better than an .py for the complete example?

1 Like
4

Almost all the example in the main repo are small focused scripts, it’s just easier to manage. Something could also be added to the bokeh-notebooks repo potentially. But the main thing would be to define and add the convenience function, so that the example script itself could short, be only 10-20 lines long.

I.e., would like to avoid repeating the situation with vector.py where 90% of the example is supporting code to generate streamlines, unrelated to Bokeh. (In fact maybe that code would be moved to a convenience function too)

1 Like
5

I’ve added the function here patches_from_voronoi.py and the example code here voronoi.py

Thanks.

1 Like