Ciemny_Cygan

random_voronoi_graph

Nov 26th, 2020
645
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import numpy as np
  2. import matplotlib.pyplot as plt
  3. from scipy.spatial import Voronoi
  4. import random
  5.  
  6. def voronoi_finite_polygons_2d(vor, radius=None):
  7.     """
  8.    Reconstruct infinite voronoi regions in a 2D diagram to finite
  9.    regions.
  10.  
  11.    Parameters
  12.    ----------
  13.    vor : Voronoi
  14.        Input diagram
  15.    radius : float, optional
  16.        Distance to 'points at infinity'.
  17.  
  18.    Returns
  19.    -------
  20.    regions : list of tuples
  21.        Indices of vertices in each revised Voronoi regions.
  22.    vertices : list of tuples
  23.        Coordinates for revised Voronoi vertices. Same as coordinates
  24.        of input vertices, with 'points at infinity' appended to the
  25.        end.
  26.  
  27.    """
  28.  
  29.     if vor.points.shape[1] != 2:
  30.         raise ValueError("Requires 2D input")
  31.  
  32.     new_regions = []
  33.     new_vertices = vor.vertices.tolist()
  34.  
  35.     center = vor.points.mean(axis=0)
  36.     if radius is None:
  37.         radius = vor.points.ptp().max()
  38.  
  39.     # Construct a map containing all ridges for a given point
  40.     all_ridges = {}
  41.     for (p1, p2), (v1, v2) in zip(vor.ridge_points, vor.ridge_vertices):
  42.         all_ridges.setdefault(p1, []).append((p2, v1, v2))
  43.         all_ridges.setdefault(p2, []).append((p1, v1, v2))
  44.  
  45.     # Reconstruct infinite regions
  46.     for p1, region in enumerate(vor.point_region):
  47.         vertices = vor.regions[region]
  48.  
  49.         if all(v >= 0 for v in vertices):
  50.             # finite region
  51.             new_regions.append(vertices)
  52.             continue
  53.  
  54.         # reconstruct a non-finite region
  55.         ridges = all_ridges[p1]
  56.         new_region = [v for v in vertices if v >= 0]
  57.  
  58.         for p2, v1, v2 in ridges:
  59.             if v2 < 0:
  60.                 v1, v2 = v2, v1
  61.             if v1 >= 0:
  62.                 # finite ridge: already in the region
  63.                 continue
  64.  
  65.             # Compute the missing endpoint of an infinite ridge
  66.  
  67.             t = vor.points[p2] - vor.points[p1] # tangent
  68.             t /= np.linalg.norm(t)
  69.             n = np.array([-t[1], t[0]])  # normal
  70.  
  71.             midpoint = vor.points[[p1, p2]].mean(axis=0)
  72.             direction = np.sign(np.dot(midpoint - center, n)) * n
  73.             far_point = vor.vertices[v2] + direction * radius
  74.  
  75.             new_region.append(len(new_vertices))
  76.             new_vertices.append(far_point.tolist())
  77.  
  78.         # sort region counterclockwise
  79.         vs = np.asarray([new_vertices[v] for v in new_region])
  80.         c = vs.mean(axis=0)
  81.         angles = np.arctan2(vs[:,1] - c[1], vs[:,0] - c[0])
  82.         new_region = np.array(new_region)[np.argsort(angles)]
  83.  
  84.         # finish
  85.         new_regions.append(new_region.tolist())
  86.  
  87.     return new_regions, np.asarray(new_vertices)
  88.  
  89. # make up data points
  90. seed = random.randint(1000, 9999)
  91. print(seed)
  92. np.random.seed(seed)
  93. points = np.random.rand(15, 2)
  94.  
  95. # compute Voronoi tesselation
  96. vor = Voronoi(points)
  97.  
  98. # plot
  99. regions, vertices = voronoi_finite_polygons_2d(vor)
  100.  
  101. # colorize
  102. for region in regions:
  103.     polygon = vertices[region]
  104.     plt.fill(*zip(*polygon), alpha=0.4)
  105.  
  106. # plt.plot(points[:,0], points[:,1], 'ko')
  107. plt.xlim(vor.min_bound[0] - 0.1, vor.max_bound[0] + 0.1)
  108. plt.ylim(vor.min_bound[1] - 0.1, vor.max_bound[1] + 0.1)
  109.  
  110. plt.axis('off')
  111. plt.savefig('mygraph.png', bbox_inches='tight', pad_inches=0.0)
RAW Paste Data