पायथन: 3 डी

Question

में सिसिसी के डेल्यूने त्रिभुज से वोरोनोई टेस्सेलेशन की गणना करें मेरे पास 3 डी में लगभग 50,000 डेटा पॉइंट हैं जिन पर मैंने scipy.spatial.Delaunay को नए scipy से चलाया है (मैं 0.10 का उपयोग कर रहा हूं) जो मुझे एक बहुत उपयोगी त्रिकोण देता है ।

के आधार पर:

... मैं अगर वहाँ एक आसान तरीका यह ट्राईऐन्ग्युलेशंस की "दोहरे ग्राफ" है, जो Voronoi है करने के लिए है सोच रहा था http://en.wikipedia.org/wiki/Delaunay_triangulation (अनुभाग "Voronoi आरेख के साथ रिश्ता") tesselation।

कोई सुराग? ऐसा लगता है कि इस पर चारों ओर खोज करने से मुझे लगता है कि मैं लगभग अजीब काम नहीं करता हूं!

धन्यवाद, एडवर्ड

Answer 1

आसन्नता जानकारी Delaunay ऑब्जेक्ट की neighbors विशेषता में पाई जा सकती है। दुर्भाग्यवश, कोड इस समय उपयोगकर्ता को circumcenters का पर्दाफाश नहीं करता है, तो आपको स्वयं को फिर से बदलना होगा।

इसके अलावा, वोरोनोई किनारों जो अनंत तक बढ़ते हैं, सीधे इस तरह से प्राप्त नहीं होते हैं। यह अभी भी संभव है, लेकिन कुछ और सोच की जरूरत है।

import numpy as np 
from scipy.spatial import Delaunay 

points = np.random.rand(30, 2) 
tri = Delaunay(points) 

p = tri.points[tri.vertices] 

# Triangle vertices 
A = p[:,0,:].T 
B = p[:,1,:].T 
C = p[:,2,:].T 

# See http://en.wikipedia.org/wiki/Circumscribed_circle#Circumscribed_circles_of_triangles 
# The following is just a direct transcription of the formula there 
a = A - C 
b = B - C 

def dot2(u, v): 
    return u[0]*v[0] + u[1]*v[1] 

def cross2(u, v, w): 
    """u x (v x w)""" 
    return dot2(u, w)*v - dot2(u, v)*w 

def ncross2(u, v): 
    """|| u x v ||^2""" 
    return sq2(u)*sq2(v) - dot2(u, v)**2 

def sq2(u): 
    return dot2(u, u) 

cc = cross2(sq2(a) * b - sq2(b) * a, a, b)/(2*ncross2(a, b)) + C 

# Grab the Voronoi edges 
vc = cc[:,tri.neighbors] 
vc[:,tri.neighbors == -1] = np.nan # edges at infinity, plotting those would need more work... 

lines = [] 
lines.extend(zip(cc.T, vc[:,:,0].T)) 
lines.extend(zip(cc.T, vc[:,:,1].T)) 
lines.extend(zip(cc.T, vc[:,:,2].T)) 

# Plot it 
import matplotlib.pyplot as plt 
from matplotlib.collections import LineCollection 

lines = LineCollection(lines, edgecolor='k') 

plt.hold(1) 
plt.plot(points[:,0], points[:,1], '.') 
plt.plot(cc[0], cc[1], '*') 
plt.gca().add_collection(lines) 
plt.axis('equal') 
plt.xlim(-0.1, 1.1) 
plt.ylim(-0.1, 1.1) 
plt.show() 

Answer 2

मैं यह करने के लिए एक समारोह का पता नहीं है, लेकिन यह एक बेहद जटिल काम की तरह प्रतीत नहीं होता।

वोरोनोई ग्राफ विकिपीडिया लेख में वर्णित circumcircles का जंक्शन है।

तो आप एक ऐसे कार्य के साथ शुरू कर सकते हैं जो त्रिकोण के circumcircles का केंद्र पाता है, जो मूल गणित (http://en.wikipedia.org/wiki/Circumscribed_circle) है।

फिर, बस आसन्न त्रिभुजों के केंद्रों में शामिल हों।

Answer 3

मैं एक ही समस्या में आया और मुझे वेब पर मिले पीवी के उत्तर और अन्य कोड स्निपेट से समाधान मिला। समाधान एक पूर्ण वोरोनोई आरेख देता है, जिसमें बाहरी रेखाएं शामिल हैं जहां कोई त्रिकोण पड़ोसी मौजूद नहीं है।

#!/usr/bin/env python 
import numpy as np 
import matplotlib 
import matplotlib.pyplot as plt 
from scipy.spatial import Delaunay 

def voronoi(P): 
    delauny = Delaunay(P) 
    triangles = delauny.points[delauny.vertices] 

    lines = [] 

    # Triangle vertices 
    A = triangles[:, 0] 
    B = triangles[:, 1] 
    C = triangles[:, 2] 
    lines.extend(zip(A, B)) 
    lines.extend(zip(B, C)) 
    lines.extend(zip(C, A)) 
    lines = matplotlib.collections.LineCollection(lines, color='r') 
    plt.gca().add_collection(lines) 

    circum_centers = np.array([triangle_csc(tri) for tri in triangles]) 

    segments = [] 
    for i, triangle in enumerate(triangles): 
     circum_center = circum_centers[i] 
     for j, neighbor in enumerate(delauny.neighbors[i]): 
      if neighbor != -1: 
       segments.append((circum_center, circum_centers[neighbor])) 
      else: 
       ps = triangle[(j+1)%3] - triangle[(j-1)%3] 
       ps = np.array((ps[1], -ps[0])) 

       middle = (triangle[(j+1)%3] + triangle[(j-1)%3]) * 0.5 
       di = middle - triangle[j] 

       ps /= np.linalg.norm(ps) 
       di /= np.linalg.norm(di) 

       if np.dot(di, ps) < 0.0: 
        ps *= -1000.0 
       else: 
        ps *= 1000.0 
       segments.append((circum_center, circum_center + ps)) 
    return segments 

def triangle_csc(pts): 
    rows, cols = pts.shape 

    A = np.bmat([[2 * np.dot(pts, pts.T), np.ones((rows, 1))], 
       [np.ones((1, rows)), np.zeros((1, 1))]]) 

    b = np.hstack((np.sum(pts * pts, axis=1), np.ones((1)))) 
    x = np.linalg.solve(A,b) 
    bary_coords = x[:-1] 
    return np.sum(pts * np.tile(bary_coords.reshape((pts.shape[0], 1)), (1, pts.shape[1])), axis=0) 

if __name__ == '__main__': 
    P = np.random.random((300,2)) 

    X,Y = P[:,0],P[:,1] 

    fig = plt.figure(figsize=(4.5,4.5)) 
    axes = plt.subplot(1,1,1) 

    plt.scatter(X, Y, marker='.') 
    plt.axis([-0.05,1.05,-0.05,1.05]) 

    segments = voronoi(P) 
    lines = matplotlib.collections.LineCollection(segments, color='k') 
    axes.add_collection(lines) 
    plt.axis([-0.05,1.05,-0.05,1.05]) 
    plt.show() 

काले लाइनों = Voronoi आरेख, लाल लाइनों = Delauny

Answer 4

त्रिकोण मैं इस पर समय के एक काफी राशि खर्च की है, मैं कैसे Voronoi पाने के लिए पर मेरे समाधान साझा करना चाहते हैं केवल किनारों के बजाय बहुभुज।

कोड https://gist.github.com/letmaik/8803860 पर है और tauran के समाधान पर विस्तारित है।

सबसे पहले, मैंने कोड को प्रतिबिंबित करने और सूचकांक (= किनारों) को अलग-अलग देने के लिए कोड बदल दिया, क्योंकि बिंदु निर्देशांक के बजाय सूचकांक पर काम करते समय कई गणनाओं को सरल बनाया जा सकता है।

फिर, voronoi_cell_lines विधि में मैं निर्धारित करता हूं कि किन किनारों से संबंधित कोशिकाएं हैं। इसके लिए मैं संबंधित प्रश्न से Alink के प्रस्तावित समाधान का उपयोग करता हूं। यही है, प्रत्येक किनारे के लिए दो निकटतम इनपुट पॉइंट (= कक्ष) ढूंढते हैं और उस से मैपिंग बनाते हैं।

अंतिम चरण वास्तविक बहुभुज बनाने के लिए है (voronoi_polygons विधि देखें)।सबसे पहले, किनारों को लटकने वाले बाहरी कोशिकाओं को बंद करने की आवश्यकता है। यह सभी किनारों को देखकर और यह जांचना जितना आसान है कि किसके पास केवल एक पड़ोसी किनारा है। या तो शून्य या दो ऐसे किनार हो सकते हैं। दो के मामले में, मैं फिर अतिरिक्त किनारे पेश करके इन्हें जोड़ता हूं।

अंत में, प्रत्येक सेल में अनियंत्रित किनारों को उनके द्वारा बहुभुज प्राप्त करने के लिए सही क्रम में रखा जाना चाहिए।

उपयोग है:

P = np.random.random((100,2)) 

fig = plt.figure(figsize=(4.5,4.5)) 
axes = plt.subplot(1,1,1) 

plt.axis([-0.05,1.05,-0.05,1.05]) 

vertices, lineIndices = voronoi(P)   
cells = voronoi_cell_lines(P, vertices, lineIndices) 
polys = voronoi_polygons(cells) 

for pIdx, polyIndices in polys.items(): 
    poly = vertices[np.asarray(polyIndices)] 
    p = matplotlib.patches.Polygon(poly, facecolor=np.random.rand(3,1)) 
    axes.add_patch(p) 

X,Y = P[:,0],P[:,1] 
plt.scatter(X, Y, marker='.', zorder=2) 

plt.axis([-0.05,1.05,-0.05,1.05]) 
plt.show() 

जो आउटपुट:

कोड शायद इनपुट अंक की बड़ी संख्या के लिए उपयुक्त नहीं है और कुछ क्षेत्रों में सुधार किया जा सकता। फिर भी, यह उन लोगों के लिए उपयोगी हो सकता है जिनके पास समान समस्याएं हैं।