Instantly share code, notes, and snippets.

# duhaime/lloyd.py

Created September 29, 2018 19:56
Show Gist options
• Save duhaime/04bf7db1d7d8d6a0d823ef88e31376fe to your computer and use it in GitHub Desktop.
Unconstrained Lloyd Iteration
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 from scipy.spatial import Voronoi, voronoi_plot_2d import matplotlib.pyplot as plt import numpy as np import umap, os def find_centroid(verts): '''Return the centroid of a polygon described by `verts`''' area = 0 x = 0 y = 0 for i in range(len(verts)-1): step = (verts[i, 0] * verts[i+1, 1]) - (verts[i+1, 0] * verts[i, 1]) area += step x += (verts[i, 0] + verts[i+1, 0]) * step y += (verts[i, 1] + verts[i+1, 1]) * step if area == 0: area += 0.01 return np.array([ (1/(3*area))*x, (1/(3*area))*y ]) def lloyd_iterate(X): voronoi = Voronoi(X, qhull_options='Qbb Qc Qx') centroids = [] for i in voronoi.regions: region = voronoi.vertices[i + [i[0]]] centroids.append( find_centroid( region ) ) return np.array(centroids) def plot(X, name): '''Plot the Voronoi map of 2D numpy array X''' v = Voronoi(X, qhull_options='Qbb Qc Qx') plot = voronoi_plot_2d(v, show_vertices=False, line_colors='y', line_alpha=0.5, point_size=5) plot.set_figheight(14) plot.set_figwidth(20) plt.axis([-10, 10, -10, 10]) if not os.path.exists('plots'): os.makedirs('plots') plot.savefig( 'plots/' + str(name) + '.png' ) # get 1000 observations in two dimensions and plot their Voronoi map X = np.random.rand(1000, 4) X = umap.UMAP().fit_transform(X) plot(X, 0) # run 4 iterations, plotting each result for i in range(100): X = lloyd_iterate(X) plot(X, i)