Berechnen und Anzeigen einer konvexen Hülle in Python

Eine konvexe Hülle ist das kleinste konvexe Polygon, das eine Punktmenge enthält. In Python berechnet SciPys ConvexHull die Hülle, und Matplotlib kann ihren Rand zeichnen. Eine kleine eigene Quickhull-Implementierung eignet sich, wenn Sie den Algorithmus nachvollziehen möchten.

Das Python Tutorial von DelftStack deckt neben Geometrie auch Strings, Dateien und Fehlerbehandlung ab und ordnet alle Anleitungen in einer klaren Lernreihenfolge.

Was ist eine konvexe Hülle?

Für Punkte in einer Ebene ist die konvexe Hülle das kleinste konvexe Polygon, das alle Punkte enthält. Stellen Sie sich ein gespanntes Gummiband um die Punktmenge vor: Die Punkte, die es berührt, sind die Eckpunkte der Hülle; Punkte innerhalb des Bandes gehören nicht zum Rand. Die Polygonkanten verbinden diese äußeren Punkte der Reihe nach.

Die Definition bezieht sich auf eine Punktmenge und nicht auf den Rand eines bereits konvexen Objekts. Konvexe Hüllen sind in der Geometrie, bei Kollisionsgrenzen und in der räumlichen Analyse nützlich. Dabei lassen sie die Anordnung der Punkte im Inneren bewusst außer Acht.

Eine konvexe Hülle mit SciPy berechnen und plotten

Installieren Sie NumPy, SciPy und Matplotlib in der Python-Umgebung, in der Sie das Skript ausführen möchten, zum Beispiel mit python -m pip install numpy scipy matplotlib. ConvexHull verarbeitet ein Array, dessen Zeilen jeweils einen Punkt und dessen zwei Spalten die x- und y-Koordinaten enthalten. Das Attribut vertices liefert die Indizes der Randpunkte in ihrer Reihenfolge. Wenn Sie diese Punkte verbinden und den ersten Punkt am Ende wiederholen, schließen Sie das Polygon.

Führen Sie dieses Beispiel aus:

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

points = np.array([
    [0.0, 0.0], [1.0, 0.0], [2.0, 0.0],
    [2.0, 1.0], [2.0, 2.0], [1.0, 2.0],
    [0.0, 2.0], [0.0, 1.0], [1.0, 1.0],
])
hull = ConvexHull(points)
boundary = points[hull.vertices]
closed_boundary = np.vstack((boundary, boundary[0]))

plt.scatter(points[:, 0], points[:, 1], label="Points")
plt.plot(closed_boundary[:, 0], closed_boundary[:, 1], "r-", label="Hull")
plt.gca().set_aspect("equal", adjustable="box")
plt.xlabel("x")
plt.ylabel("y")
plt.legend()
plt.show()

Der innere Punkt gehört zwar zu den Eingabedaten, aber nicht zur Hülle. Hier eignet sich hull.vertices besser als das Plotten von hull.simplices Kante für Kante: Die geordneten Eckpunkte ergeben eine einzige geschlossene Umrandung. Das Beispiel öffnet ein Matplotlib-Fenster; in einem Notebook wird die Abbildung stattdessen im Ausgabebereich angezeigt. Die Beschriftungen „Points“ und „Hull“ bleiben im unveränderten Beispielcode Englisch.

Quickhull in Python implementieren

Quickhull ist ein rekursives Verfahren, um eine 2D-Hülle zu finden. Es beginnt mit den Punkten mit der kleinsten und der größten x-Koordinate. Diese Endpunkte teilen den möglichen Rand in zwei Seiten. Für jede gerichtete Seite wählt der Algorithmus den Punkt mit dem größten positiven Kreuzprodukt aus (der dazugehörige senkrechte Abstand ist proportional zu diesem Wert) und durchsucht anschließend die beiden kleineren Punktmengen auf beiden Seiten dieses Punkts. Liegt kein Kandidat links von einer Strecke, gehört diese Strecke zum Rand. Durch die strenge Seitenprüfung wird jeder ausgewählte Punkt aus den folgenden rekursiven Aufrufen entfernt. Daher endet die Rekursion bei einer endlichen Menge verschiedener Punkte.

Die folgende Implementierung akzeptiert ein iterierbares Objekt mit 2D-Koordinatenpaaren und gibt die Eckpunkte des Polygons in Umlaufrichtung zurück, ohne den ersten Punkt zu wiederholen. Vor der rekursiven Suche entfernt sie doppelte Koordinaten. Bei weniger als drei verschiedenen Punkten oder wenn alle Punkte auf einer Geraden liegen, gibt sie die vorhandenen äußersten Punkte zurück. Das Beispiel benötigt nur die Python-Standardbibliothek. Sie können es daher als einzelnes Skript ausführen und die zurückgegebene Liste später an eine Plot-Bibliothek übergeben.

Führen Sie dieses Beispiel aus:

def cross(a, b, point):
    """Return the signed 2D cross product of AB and A-to-point."""
    return (b[0] - a[0]) * (point[1] - a[1]) - (b[1] - a[1]) * (point[0] - a[0])


def quickhull(points):
    """Return the vertices of a 2D convex hull in boundary order."""
    unique = sorted(set(tuple(point) for point in points))
    if len(unique) <= 2:
        return unique

    left = min(unique, key=lambda point: (point[0], point[1]))
    right = max(unique, key=lambda point: (point[0], point[1]))

    def chain(start, end, candidates):
        candidates = [point for point in candidates if cross(start, end, point) > 0]
        if not candidates:
            return []
        farthest = max(candidates, key=lambda point: cross(start, end, point))
        first = [point for point in candidates if cross(start, farthest, point) > 0]
        second = [point for point in candidates if cross(farthest, end, point) > 0]
        return chain(start, farthest, first) + [farthest] + chain(farthest, end, second)

    upper = chain(left, right, unique)
    lower = chain(right, left, unique)
    return [left] + upper + [right] + lower


points = [
    (0, 0), (1, 0), (2, 0), (2, 1), (2, 2),
    (1, 2), (0, 2), (0, 1), (1, 1),
]
hull_points = quickhull(points)
closed_hull = hull_points + hull_points[:1]
print(hull_points)

Das Vorzeichen des Kreuzprodukts zeigt, auf welcher Seite einer gerichteten Geraden ein Punkt liegt; sein Betrag ordnet die Kandidaten auf dieser Seite. Die rekursiven Aufrufe behalten nur Punkte bei, die strikt außerhalb der beiden neuen Strecken liegen. Die zurückgegebene Liste folgt dem Polygonrand. Hängen Sie beim Zeichnen einer geschlossenen Linie daher den ersten Punkt erneut an. Diese Lernimplementierung ist auf 2D-Punkte beschränkt und ersetzt in Produktionsanwendungen keine geprüfte Geometriebibliothek. Bei bestimmten Punktverteilungen kann die einfache Rekursion außerdem erheblichen Rechenaufwand verursachen.

Vorgehensweise wählen und Sonderfälle berücksichtigen

Verwenden Sie SciPy, wenn Sie eine gepflegte Bibliotheksfunktion, die Indizes der Hülle oder Unterstützung für mehr als zwei Dimensionen benötigen. Eine eigene Quickhull-Implementierung eignet sich, wenn Sie die rekursive Aufteilung verstehen oder eine kleine 2D-Routine anpassen möchten. Gehen Sie nicht von einem vermeintlichen Geschwindigkeitsvorteil aus: Die Leistung hängt von den Daten und der Umgebung ab; dieser Artikel enthält keine Benchmark-Aussage.

Form und Geometrie der Eingabedaten sind wichtig. SciPy benötigt für ein 2D-Polygon mindestens drei nicht kollineare Punkte. Zu wenige Punkte oder eine kollineare Punktmenge können kein solches Polygon bilden; Qhull meldet in diesen Fällen einen Geometriefehler. Fangen Sie scipy.spatial.QhullError ab, wenn Ihre Anwendung diesen Fall behandeln muss, oder prüfen Sie die Eingabe vor dem Aufruf von ConvexHull. Doppelte Punkte fügen keine Eckpunkte am Rand hinzu. Die oben gezeigte eigene Funktion entfernt Duplikate und gibt bei kollinearen Eingaben die vorhandenen äußersten Punkte zurück. Sie setzt jedoch endliche numerische Koordinatenpaare voraus. Prüfen Sie nicht vertrauenswürdige Daten daher, bevor Sie sie übergeben. Für 3D-Hüllen und höhere Dimensionen verwenden Sie die SciPy-Bibliotheksimplementierung statt dieses eigenen 2D-Algorithmus.

Häufig gestellte Fragen

Wie findet Quickhull den Rand?

Das Verfahren beginnt mit äußersten Punkten, wählt auf jeder Seite den am weitesten entfernten Kandidaten aus und untersucht rekursiv die Punktmengen außerhalb der neuen Strecken. Gibt es auf einer Seite keine weiteren Kandidaten, gehört die entsprechende Kante zur Hülle.

Lässt sich eine konvexe Hülle in 3D berechnen?

Ja. SciPys ConvexHull unterstützt Punkt-Arrays mit mehr als zwei Koordinatenspalten. Die hier gezeigte eigene Implementierung verwendet 2D-Kreuzprodukte und verarbeitet keine 3D-Eingaben.

Was passiert, wenn die Punkte kollinear sind?

Sie bilden kein 2D-Polygon. SciPy meldet einen Qhull-Geometriefehler; die eigene Funktion gibt die beiden äußersten Punkte zurück oder weniger, wenn es weniger verschiedene Punkte gibt.

Welches Verfahren sollte ich verwenden?

Wählen Sie SciPy für Anwendungscode und Eingaben mit mehr als zwei Dimensionen. Verwenden Sie die eigene Variante, um den 2D-Algorithmus zu verstehen. Ergänzen Sie Eingabeprüfungen und Tests, bevor Sie sie für ein größeres System anpassen.