voronoi_subdivide

Example Python program voronoi_subdivide.py

Modules

• import numpy as np
• from scipy.spatial.distance import cdist,pdist,squareform
• import matplotlib
• import matplotlib.pyplot as plt
• import matplotlib.tri as tri
• from voronoi import voronoi # http://webloria.loria.fr/~rougier/coding/neural-networks/voronoi.py

Code

Python example

import numpy as np
from scipy.spatial.distance import cdist,pdist,squareform
import matplotlib
import matplotlib.pyplot as plt
import matplotlib.tri as tri

from voronoi import voronoi # http://webloria.loria.fr/~rougier/coding/neural-networks/voronoi.py


# Code to take a voronoi tesselation of a 2D space and subdivide each voronoi cell by 
# selecting the m furthest neighboring voronoi cell centers and generating n-1 new points between
# the center and the midpoint to the neighbor, that along with the original center will 
# define a new voronoi parition within the cell.


k = 10 # number of reference poses
N = 40000 # number of test points
m = 2 # number of neighbors to base subdivision off of
n = 3 # number of slices 

colors = np.arange(m*n+1)

g = np.linspace(0,1,n+1)
gdata = np.array([0,1])

# Define Random reference points
x_i = np.random.uniform(0,5,size=(k,2))

# Calculate pairwise distance between references points
d_ij = squareform(pdist(x_i))

# Define voronoi
vorbounds = voronoi(x_i[:,0],x_i[:,1])

# Create Deluanay Triangulation
triang = tri.Triangulation(x_i[:,0], x_i[:,1])
edges = triang.edges

# Create supplementary poses to subdivide voronoi cells
y_i = []
for vori,vor in enumerate(x_i):
    temppoints = []
    # Identify neighboring reference poses
    jj = np.where((edges[:,0] == vori) | (edges[:,1] == vori))
    pj = edges[jj].flatten()
    pj = pj[pj != vori]

    # Get m poses with largest distance
    d_j = d_ij[vori,:]
    neigh_target_j = pj[np.argsort(d_j[pj])[::-1]]

    # Linearly interpolate n points between reference and midpoint with neighbors
    count = 0
    for nj in neigh_target_j:
        if count > m - 1:
            break
        midpoint = 0.5*(vor - x_i[nj,:]) + x_i[nj,:]
        nearest = np.argmin(cdist(np.atleast_2d(midpoint),x_i))
        # exclude centeres connected via the Delaunay triangulation
        # that pass through an intervening voronoi cell
        if not nearest in [nj,vori]:
            continue
        endpoints = np.vstack((vor,midpoint))
        a = np.zeros((g.shape[0]-2,2))
        for dim in xrange(2):
            a[:,dim] = np.interp(g,gdata,endpoints[:,dim])[1:-1]

        temppoints.append(a)
        count += 1

    if len(temppoints):  
        y_i.append(np.vstack(temppoints))
    else:
        y_i.append([])

# Generate a large number of random configs and assign to subdivisions
x = np.random.uniform(0,5,size=(N,2))
cassign = np.zeros((N,))
for ii,p in enumerate(x):
    # Calculate the distance from point to every reference pose
    p = np.atleast_2d(p)
    d_j = cdist(p,x_i,metric='euclidean')

    # Identify voronoi membership
    pi = np.argmin(d_j)

    # Determine membership in subdivisions
    if len(y_i[pi]):
        subpoints = np.vstack((x_i[pi,:],y_i[pi]))
    else:
        subpoints = x_i[pi,:]
    subpoints = np.atleast_2d(subpoints)
    si = np.argmin(cdist(p,subpoints))
    cassign[ii] = colors[si]

#print cassign    
fig = plt.figure()
ax = fig.add_subplot(111)

# Plot reference poses
ax.plot(x_i[:,0],x_i[:,1],'.',color='yellow',markersize=20)

# Plot internal points
y_ii = [a for a in y_i if a != []]
z = np.vstack(y_ii)
ax.plot(z[:,0],z[:,1],'.',color='yellow',markersize=10)


# Plot voronoi edges
vorlines = matplotlib.collections.LineCollection(vorbounds, color='yellow',linewidths=3)
ax.add_collection(vorlines)

# Plot Deluanay triangulation
ax.triplot(triang, 'wo-')

# Plot test particles
ax.scatter(x[:,0],x[:,1],marker='o',c=cassign,s=5)

plt.axis([-1,6,-1,6])
plt.show()

Useful Links

• Articles: https://python-commandments.org/
• Python shell: https://bsdnerds.org/learn-python/
• Tutorial: https://pythonprogramminglanguage.com/