Berechnen und zeichnen Sie begrenzte (geschlossene) Boronoi-Diagramme in Python

Einführung

Zu den Bibliotheken, die Boronoi-Diagramme in Python berechnen und zeichnen, gehören scipy.spatial.Voronoi und scipy.spatial.voronoi_plot_2d. Einzelheiten hierzu finden Sie auf den folgenden Websites.

• Offizielle Dokumentation von scipy.spatial.Voronoi
• Offizielle Dokumentation von scipy.spatial.voronoi_plot_2d
• scipy Voronoi

Da die von diesen Bibliotheken erstellten Boronoi-Diagramme jedoch in einem unbegrenzten (nicht geschlossenen) Raum berechnet werden, ist es nicht möglich, Informationen über die äußere Boronoi-Seite oder die Boronoi-Region (Polygon) zu erhalten. Daher werde ich dieses Mal eine Methode einführen, um einen geschlossenen Bereich in Boronoi zu unterteilen.

Implementierung

Für den Teil, der das Boronoi-Gebiet gebunden macht, habe ich auf [diesen Artikel] verwiesen (http://satemochi.blog.fc2.com/blog-entry-58.html). Der allgemeine Fluss ist wie folgt.

1. Fügen Sie drei Dummy-Mutterpunkte hinzu, um alle Boronoi-Regionen zu binden.
2. Berechnen Sie das Boronoi-Diagramm mit scipy.spatial.Voronoi.
3. Berechnen Sie den gemeinsamen Teil der zu teilenden Fläche und jede Boronoi-Fläche mit "formschön".
4. Zeichnen Sie das in 3 erhaltene Polygon.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.collections import PolyCollection
from scipy.spatial import Voronoi, voronoi_plot_2d
from shapely.geometry import Polygon

def bounded_voronoi(bnd, pnts):
    """
Eine Funktion, die ein begrenztes Boronoi-Diagramm berechnet und zeichnet.
    """
    
    #Es wurden 3 Dummy-Mutterpunkte hinzugefügt, um die Boronoi-Region aller Mutterpunkte zu begrenzen
    gn_pnts = np.concatenate([pnts, np.array([[100, 100], [100, -100], [-100, 0]])])
    
    #Berechnung des Boronoi-Diagramms
    vor = Voronoi(gn_pnts)
    
    #Polygon für den zu teilenden Bereich
    bnd_poly = Polygon(bnd)
    
    #Liste zum Speichern jedes Boronoi-Bereichs
    vor_polys = []
    
    #Wiederholen Sie diesen Vorgang für nicht-Dummy-Mutterpunkte
    for i in range(len(gn_pnts) - 3):
        
        #Boronoi-Gebiet, das keinen geschlossenen Raum berücksichtigt
        vor_poly = [vor.vertices[v] for v in vor.regions[vor.point_region[i]]]
        #Berechnen Sie den gemeinsamen Teil des Boronoi-Gebiets für das zu teilende Gebiet
        i_cell = bnd_poly.intersection(Polygon(vor_poly))
        
        #Speichert die Scheitelpunktkoordinaten der Boronoi-Region unter Berücksichtigung des geschlossenen Raums
        vor_polys.append(list(i_cell.exterior.coords[:-1]))
    
    
    #Zeichnen eines Boronoi-Diagramms
    fig = plt.figure(figsize=(7, 6))
    ax = fig.add_subplot(111)
    
    #Mutterpunkt
    ax.scatter(pnts[:,0], pnts[:,1])
    
    #Boronoi Bereich
    poly_vor = PolyCollection(vor_polys, edgecolor="black",
                              facecolors="None", linewidth = 1.0)
    ax.add_collection(poly_vor)
    
    xmin = np.min(bnd[:,0])
    xmax = np.max(bnd[:,0])
    ymin = np.min(bnd[:,1])
    ymax = np.max(bnd[:,1])
    
    ax.set_xlim(xmin-0.1, xmax+0.1)
    ax.set_ylim(ymin-0.1, ymax+0.1)
    ax.set_aspect('equal')
    
    plt.show()
    
    return vor_polys

Teilen Sie das Einheitsquadrat

Das Teilen des Einheitsquadrats mit der obigen Funktion ergibt Folgendes.

#Boronoi Bereich zu teilen
bnd = np.array([[0, 0], [1, 0], [1, 1], [0, 1]])

#Anzahl der Mutterpunkte
n = 30
#Mutterpunktkoordinaten
pnts = np.random.rand(n, 2)

#Berechnung und Zeichnung des Boronoi-Diagramms
vor_polys = bounded_voronoi(bnd, pnts)

Teilen Sie ein allgemeines konvexes Polygon

Allgemeine konvexe Polygone, die keine Quadrate sind, können auf dieselbe Weise unterteilt werden.

from scipy.spatial import ConvexHull

def points_in_convex_polygon(bnd, n):
    """
Eine Funktion, die zufällig n Punkte innerhalb eines konvexen Polygons generiert.
    """
    
    #Erstellen einer Matrix, die die Grenzen einer Region darstellt
    bndhull = ConvexHull(bnd)
    bndTmp = bndhull.equations
    bndMat = np.matrix(bndTmp)
    Abnd = np.array(bndMat[:,0:2])
    bbnd = np.array(bndMat[:,2])
    
    #Rechteck um die Gegend
    xmin = np.min(bnd[:,0])
    xmax = np.max(bnd[:,0])
    ymin = np.min(bnd[:,1])
    ymax = np.max(bnd[:,1])
    
    #Zur Wiederholung
    i = 0
    pnts = []
    
    while i < n:
        
        #Punkte generieren
        pnt = np.random.rand(2)
        pnt[0] = xmin + (xmax - xmin) * pnt[0]
        pnt[1] = ymin + (ymax - ymin) * pnt[1]
        
        #Wenn sich der Punkt innerhalb eines konvexen Polygons befindet
        if (np.round(np.dot(Abnd,pnt.transpose()),7) <= np.round(-bbnd.transpose(),7)).all():

            pnts.append(pnt.tolist())
            i += 1

    return np.array(pnts)


#Boronoi Bereich zu teilen
bnd = np.array([[0.1,0.4],[0.3,0.2],[0.8,0.3],[0.9,0.6],[0.7,0.7],[0.4,0.7],[0.2,0.6]])

#Anzahl der Mutterpunkte
n = 10
#Mutterpunktkoordinaten
pnts = points_in_convex_polygon(bnd, n)

#Berechnung und Zeichnung des Boronoi-Diagramms
vor_polys = bounded_voronoi(bnd, pnts)