रंगीन वोरोनोई आरेख

Question

मैं scipy.spatial.Voronoi का उपयोग करके बनाए गए वोरोनोई आरेख को रंगीन करने की कोशिश कर रहा हूं। यहाँ मेरी कोड है:

import numpy as np 
import matplotlib.pyplot as plt 
from scipy.spatial import Voronoi, voronoi_plot_2d 

# make up data points 
points = np.random.rand(15,2) 

# compute Voronoi tesselation 
vor = Voronoi(points) 

# plot 
voronoi_plot_2d(vor) 

# colorize 
for region in vor.regions: 
    if not -1 in region: 
     polygon = [vor.vertices[i] for i in region] 
     plt.fill(*zip(*polygon)) 

plt.show() 

जिसके परिणामस्वरूप छवि:

आप छवि की सीमा पर Voronoi क्षेत्रों के कुछ देख सकते हैं रंग नहीं कर रहे हैं। ऐसा इसलिए है क्योंकि इन क्षेत्रों के लिए वोरोनोई के कुछ सूचकांक -1 पर सेट किए गए हैं, यानी वोरोनोई आरेख के बाहर उन शीर्षकों के लिए। डॉक्स के अनुसार:

क्षेत्रों: प्रत्येक Voronoi क्षेत्र बनाने Voronoi कोने का सूचकांक (ints, आकृति (nregions, *) की सूची की सूची)। -1 वोरोनोई आरेख के बाहर वर्टेक्स इंगित करता है।

आदेश के साथ-साथ इन क्षेत्रों colorize करने के लिए, मैं सिर्फ बहुभुज से इन "बाहर" कोने को दूर करने की कोशिश की है, लेकिन यह काम नहीं किया। मुझे लगता है, मुझे छवि क्षेत्र की सीमा पर कुछ बिंदुओं को भरने की जरूरत है, लेकिन मुझे लगता है कि यह उचित तरीके से कैसे प्राप्त किया जाए।

क्या कोई मदद कर सकता है?

Answer 1

वोरोनोई डेटा संरचना में "अनंतता के बिंदु" के लिए पदों का निर्माण करने के लिए सभी आवश्यक जानकारी शामिल हैं। Qhull भी उन्हें -1 सूचकांक के रूप में रिपोर्ट करता है, इसलिए Scipy उन्हें आपके लिए गणना नहीं करता है।

https://gist.github.com/pv/8036995

import numpy as np 
import matplotlib.pyplot as plt 
from scipy.spatial import Voronoi 

def voronoi_finite_polygons_2d(vor, radius=None): 
    """ 
    Reconstruct infinite voronoi regions in a 2D diagram to finite 
    regions. 

    Parameters 
    ---------- 
    vor : Voronoi 
     Input diagram 
    radius : float, optional 
     Distance to 'points at infinity'. 

    Returns 
    ------- 
    regions : list of tuples 
     Indices of vertices in each revised Voronoi regions. 
    vertices : list of tuples 
     Coordinates for revised Voronoi vertices. Same as coordinates 
     of input vertices, with 'points at infinity' appended to the 
     end. 

    """ 

    if vor.points.shape[1] != 2: 
     raise ValueError("Requires 2D input") 

    new_regions = [] 
    new_vertices = vor.vertices.tolist() 

    center = vor.points.mean(axis=0) 
    if radius is None: 
     radius = vor.points.ptp().max() 

    # Construct a map containing all ridges for a given point 
    all_ridges = {} 
    for (p1, p2), (v1, v2) in zip(vor.ridge_points, vor.ridge_vertices): 
     all_ridges.setdefault(p1, []).append((p2, v1, v2)) 
     all_ridges.setdefault(p2, []).append((p1, v1, v2)) 

    # Reconstruct infinite regions 
    for p1, region in enumerate(vor.point_region): 
     vertices = vor.regions[region] 

     if all(v >= 0 for v in vertices): 
      # finite region 
      new_regions.append(vertices) 
      continue 

     # reconstruct a non-finite region 
     ridges = all_ridges[p1] 
     new_region = [v for v in vertices if v >= 0] 

     for p2, v1, v2 in ridges: 
      if v2 < 0: 
       v1, v2 = v2, v1 
      if v1 >= 0: 
       # finite ridge: already in the region 
       continue 

      # Compute the missing endpoint of an infinite ridge 

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

      midpoint = vor.points[[p1, p2]].mean(axis=0) 
      direction = np.sign(np.dot(midpoint - center, n)) * n 
      far_point = vor.vertices[v2] + direction * radius 

      new_region.append(len(new_vertices)) 
      new_vertices.append(far_point.tolist()) 

     # sort region counterclockwise 
     vs = np.asarray([new_vertices[v] for v in new_region]) 
     c = vs.mean(axis=0) 
     angles = np.arctan2(vs[:,1] - c[1], vs[:,0] - c[0]) 
     new_region = np.array(new_region)[np.argsort(angles)] 

     # finish 
     new_regions.append(new_region.tolist()) 

    return new_regions, np.asarray(new_vertices) 

# make up data points 
np.random.seed(1234) 
points = np.random.rand(15, 2) 

# compute Voronoi tesselation 
vor = Voronoi(points) 

# plot 
regions, vertices = voronoi_finite_polygons_2d(vor) 
print "--" 
print regions 
print "--" 
print vertices 

# colorize 
for region in regions: 
    polygon = vertices[region] 
    plt.fill(*zip(*polygon), alpha=0.4) 

plt.plot(points[:,0], points[:,1], 'ko') 
plt.xlim(vor.min_bound[0] - 0.1, vor.max_bound[0] + 0.1) 
plt.ylim(vor.min_bound[1] - 0.1, vor.max_bound[1] + 0.1) 

plt.show() 

Answer 2

मुझे नहीं लगता कि कम से कम कुछ वोरोनोई गणना के बिना इसे बाहर निकालने के लिए vor संरचना में उपलब्ध डेटा से पर्याप्त जानकारी है। चूंकि यह मामला है, यहां मूल voronoi_plot_2d फ़ंक्शन के प्रासंगिक भाग हैं जिन्हें आप vor.max_bound या vor.min_bound के साथ छेड़छाड़ करने वाले बिंदुओं को निकालने के लिए उपयोग करने में सक्षम होना चाहिए जो आरेख के नीचे बाएं और शीर्ष दाएं कोने हैं आदेश अपने बहुभुज के लिए अन्य निर्देशांक को समझें।

for simplex in vor.ridge_vertices: 
    simplex = np.asarray(simplex) 
    if np.all(simplex >= 0): 
     ax.plot(vor.vertices[simplex,0], vor.vertices[simplex,1], 'k-') 

ptp_bound = vor.points.ptp(axis=0) 
center = vor.points.mean(axis=0) 
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() 

     ax.plot([vor.vertices[i,0], far_point[0]], 
       [vor.vertices[i,1], far_point[1]], 'k--')