﻿

# 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.
7.     """
8.    Reconstruct infinite voronoi regions in a 2D diagram to finite
9.    regions.
10.
11.    Parameters
12.    ----------
13.    vor : Voronoi
14.        Input diagram
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)
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')