Computergeometrie in Python: Von der Theorie zur Anwendung

Wenn Menschen an Computergeometrie denken, denken sie meiner Erfahrung nach normalerweise an eines von zwei Dingen:

1. Wow, das klingt kompliziert.
2. Oh ja, konvexe Hülle.

In diesem Beitrag möchte ich etwas Licht in die Computergeometrie bringen, beginnend mit einem kurzen Überblick über das Thema, bevor ich zu einigen praktischen Ratschlägen übergehe, die auf meinen eigenen Erfahrungen basieren (springen Sie weiter, wenn Sie mit dem Thema vertraut sind).

Was soll die ganze Aufregung?

Während Computergeometriealgorithmen für konvexe Hüllen normalerweise in einem Einführungskurs für Algorithmen enthalten sind, ist Computergeometrie ein weitaus reichhaltigeres Thema, das vom durchschnittlichen Entwickler / Informatiker selten genügend Aufmerksamkeit erhält (es sei denn, Sie entwickeln Spiele oder ähnliches).

Theoretisch spannend…

Aus theoretischer Sicht sind die Fragen der Computergeometrie oft überaus interessant; die Antworten, überzeugend; und die Wege, auf denen sie erreicht werden, vielfältig. Allein diese Qualitäten machen es meiner Meinung nach zu einem Studienfach.

Betrachten Sie zum Beispiel das Kunstgalerie-Problem: Wir besitzen eine Kunstgalerie und möchten Sicherheitskameras installieren, um unsere Kunstwerke zu bewachen. Aber wir haben ein knappes Budget, also wollen wir so wenig Kameras wie möglich verwenden. Wie viele Kameras brauchen wir?

Wenn wir dies in eine computergeometrische Notation übersetzen, ist der „Grundriss“ der Galerie nur ein einfaches Polygon. Und mit etwas Ellbogenfett können wir beweisen, dass n/3 Kameras immer für ein Polygon auf n Eckpunkten ausreichen, egal wie chaotisch es ist. Der Beweis selbst verwendet duale Graphen, etwas Graphentheorie, Triangulationen und mehr.

Hier sehen wir eine clevere Beweistechnik und ein Ergebnis, das neugierig genug ist, um es für sich allein zu schätzen. Aber wenn Ihnen die theoretische Relevanz nicht ausreicht …

Und wichtige Praxis

Wie ich bereits erwähnt habe, stützt sich die Spieleentwicklung stark auf die Anwendung von Computergeometrie (zum Beispiel stützt sich die Kollisionserkennung oft auf die Berechnung der konvexen Hülle einer Menge von Objekten); ebenso geografische Informationssysteme (GIS), die zum Speichern und Durchführen von Berechnungen mit geografischen Daten verwendet werden; und Robotik (z. B. für Sichtbarkeits- und Planungsprobleme).

Warum ist es so hart?

Nehmen wir ein ziemlich einfaches Rechengeometrieproblem: Liegt ein gegebener Punkt und ein Polygon innerhalb des Polygons? (Dies wird als Point-in-Polygon- oder PIP-Problem bezeichnet.)

PIP demonstriert hervorragend, warum Computergeometrie (täuschend) schwierig sein kann. Für das menschliche Auge ist das keine schwierige Frage. Wir sehen das folgende Diagramm und es ist uns sofort klar, dass der Punkt im Polygon liegt:

Selbst bei relativ komplizierten Polygonen entgeht uns die Antwort nicht länger als ein oder zwei Sekunden. Aber wenn wir dieses Problem einem Computer zuführen, sieht er möglicherweise Folgendes:

 poly = Polygon([Point(0, 5), Point(1, 1), Point(3, 0), Point(7, 2), Point(7, 6), Point(2, 7)]) point = Point(5.5, 2.5) poly.contains(point)

Was für das menschliche Gehirn intuitiv ist, lässt sich nicht so einfach in Computersprache übersetzen.

Abstrakter (und abgesehen von der Notwendigkeit, diese Dinge in Code darzustellen) sind die Probleme, die wir in dieser Disziplin sehen, in einem Algorithmus für Computergeometrie sehr schwer zu rigorisieren („rigoros machen“). Wie würden wir das Punkt-in-Polygon-Szenario beschreiben, ohne eine tautologische Sprache wie „Ein Punkt befindet sich innerhalb eines Polygons, wenn er sich innerhalb des Polygons befindet“ zu verwenden? Viele dieser Eigenschaften sind so fundamental und so grundlegend, dass es schwierig ist, sie konkret zu definieren.

Schwierig, aber nicht unmöglich. Beispielsweise könnten Sie Point-in-Polygon mit den folgenden Definitionen rigorisieren:

• Ein Punkt befindet sich innerhalb eines Polygons, wenn ein unendlicher Strahl, der an dem Punkt beginnt, eine ungerade Anzahl von Polygonkanten schneidet (bekannt als Gerade-Ungerade-Regel).
• Ein Punkt befindet sich innerhalb eines Polygons, wenn er eine Windungszahl ungleich Null hat (definiert als die Anzahl von Malen, die die Kurve, die das Polygon definiert, um den Punkt wandert).

Wenn Sie keine Erfahrung mit Computergeometrie haben, werden diese Definitionen wahrscheinlich nicht Teil Ihres vorhandenen Vokabulars sein. Und vielleicht ist das ein Sinnbild dafür, wie Computergeometrie Sie dazu bringen kann , anders zu denken .

Wir stellen CCW vor

Jetzt, da wir ein Gefühl für die Bedeutung und Schwierigkeit von Problemen der Computergeometrie haben, ist es an der Zeit, unsere Hände nass zu machen.

Das Rückgrat des Themas ist eine täuschend mächtige primitive Operation: gegen den Uhrzeigersinn oder kurz „CCW“. (Ich warne Sie jetzt: CCW wird immer wieder auftauchen.)

CCW nimmt drei Punkte A, B und C als Argumente und fragt: Bilden diese drei Punkte eine Drehung gegen den Uhrzeigersinn (im Gegensatz zu einer Drehung im Uhrzeigersinn)? Mit anderen Worten, ist A -> B -> C ein Winkel gegen den Uhrzeigersinn?

Zum Beispiel sind die grünen Punkte CCW, während die roten Punkte nicht sind:

Warum CCW wichtig ist

CCW gibt uns eine primitive Operation, auf der wir aufbauen können. Es gibt uns einen Ort, an dem wir mit der Rigorisierung und Lösung von Problemen der Computergeometrie beginnen können.

Um Ihnen ein Gefühl für seine Macht zu vermitteln, betrachten wir zwei Beispiele.

Bestimmung der Konvexität

Die erste: Können Sie bei einem Polygon feststellen, ob es konvex ist? Konvexität ist eine Eigenschaft von unschätzbarem Wert: Wenn Sie wissen, dass Ihre Polygone konvex sind, können Sie die Leistung oft um Größenordnungen verbessern. Als konkretes Beispiel: Es gibt einen ziemlich einfachen PIP-Algorithmus, der für konvexe Polygone in Log(n)-Zeit läuft, aber für viele konkave Polygone fehlschlägt.

Intuitiv ergibt diese Lücke Sinn: konvexe Formen sind „schön“, während konkave Formen scharfe Kanten haben können, die nach innen und außen ragen – sie folgen einfach nicht denselben Regeln.

Ein einfacher (aber nicht offensichtlicher) Berechnungsgeometriealgorithmus zum Bestimmen der Konvexität besteht darin, zu überprüfen, ob jedes Triplett aufeinanderfolgender Eckpunkte gegen den Uhrzeigersinn gerichtet ist. Dies erfordert nur ein paar Zeilen Python-Geometriecode (vorausgesetzt, dass die points gegen den Uhrzeigersinn bereitgestellt werden – wenn die points im Uhrzeigersinn angeordnet sind, möchten Sie, dass alle Tripletts im Uhrzeigersinn angeordnet sind):

 class Polygon(object): ... def isConvex(self): for i in range(self.n): # Check every triplet of points A = self.points[i % self.n] B = self.points[(i + 1) % self.n] C = self.points[(i + 2) % self.n] if not ccw(A, B, C): return False return True

Versuchen Sie dies auf Papier mit ein paar Beispielen. Sie können dieses Ergebnis sogar verwenden, um Konvexität zu definieren . (Um die Dinge intuitiver zu gestalten, beachten Sie, dass eine CCW-Kurve von A -> B -> C einem Winkel von weniger als 180 entspricht, was eine weit verbreitete Methode zur Definition von Konvexität ist.)

Linienkreuzung

Betrachten Sie als zweites Beispiel den Schnittpunkt von Liniensegmenten, der auch nur mit CCW gelöst werden kann:

 def intersect(a1, b1, a2, b2): """Returns True if line segments a1b1 and a2b2 intersect.""" return ccw(a1, b1, a2) != ccw(a1, b1, b2) and ccw(a2, b2, a1) != ccw(a2, b2, b1)

Warum ist das so? Der Schnittpunkt von Liniensegmenten kann auch so formuliert werden: Liegen bei einem gegebenen Segment mit den Endpunkten A und B die Endpunkte C und D eines anderen Segments auf derselben Seite von AB? Mit anderen Worten, wenn die Abbiegungen von A -> B -> C und A -> B -> D in dieselbe Richtung verlaufen, können sich die Segmente nicht schneiden. Wenn wir diese Art von Sprache verwenden, wird klar, dass ein solches Problem das Brot und die Butter von CCW ist.

Eine strenge Definition

Nun, da wir einen Eindruck von der Bedeutung von CCW bekommen haben, sehen wir uns an, wie es berechnet wird. Gegebene Punkte A, B und C:

 def ccw(A, B, C): """Tests whether the turn formed by A, B, and C is ccw""" return (Bx - Ax) * (Cy - Ay) > (By - Ay) * (Cx - Ax)

Um zu verstehen, woher diese Definition kommt, betrachten Sie die Vektoren AB und BC. Wenn wir ihr Kreuzprodukt AB x BC nehmen, ist dies ein Vektor entlang der z-Achse. Aber in welche Richtung (dh +z oder -z)? Wie sich herausstellt, ist die Drehung gegen den Uhrzeigersinn, wenn das Kreuzprodukt positiv ist; andernfalls ist es im Uhrzeigersinn.

Diese Definition erscheint unintuitiv, es sei denn, Sie haben ein wirklich gutes Verständnis der linearen Algebra, der Rechte-Hand-Regel usw. Aber deshalb haben wir Abstraktion – wenn Sie an CCW denken, denken Sie nur an seine intuitive Definition und nicht an seine Berechnung. Der Wert wird sofort klar.

My Dive In Computational Geometry and Programming Using Python

Im letzten Monat habe ich an der Implementierung mehrerer Algorithmen für Computergeometrie in Python gearbeitet. Da ich in den nächsten Abschnitten darauf zurückgreifen werde, nehme ich mir einen Moment Zeit, um meine Anwendungen für Computergeometrie zu beschreiben, die auf GitHub zu finden sind.

Hinweis: Meine Erfahrung ist zugegebenermaßen begrenzt. Da ich an diesem Zeug eher Monate als Jahre gearbeitet habe, nehmen Sie meinen Rat mit einem Körnchen Salz. Trotzdem habe ich in diesen paar Monaten viel gelernt, also hoffe ich, dass sich diese Tipps als nützlich erweisen.

Kirkpatricks Algorithmus

Im Mittelpunkt meiner Arbeit stand eine Implementierung von Kirkpatricks Algorithmus zur Punktortung. Die Problemstellung wäre in etwa so: Welches Polygon enthält P bei einer gegebenen planaren Unterteilung (ein Bündel nicht überlappender Polygone in der Ebene) und einem Punkt P? Stellen Sie sich Point-in-Polygon bei Steroiden vor – statt eines einzelnen Polygons haben Sie ein ganzes Flugzeug voll davon.

Betrachten Sie als Anwendungsfall eine Webseite. Wenn ein Benutzer mit der Maus klickt, muss die Webseite so schnell wie möglich herausfinden, worauf der Benutzer geklickt hat. War es Taste A? War es Link B? Die Webseite besteht aus nicht überlappenden Polygonen, daher wäre Kirkpatricks Algorithmus gut positioniert, um zu helfen.

Obwohl ich den Algorithmus nicht im Detail besprechen werde, können Sie hier mehr erfahren.

Minimales Begrenzungsdreieck

Als Teilaufgabe habe ich auch den Algorithmus von O'Rourke zur Berechnung eines minimalen umschließenden/begrenzenden Dreiecks (d. h. das Finden des kleinsten Dreiecks, das eine Menge von Punkten konvex umschließt) in linearer Zeit implementiert.

Hinweis: Die Berechnung des minimalen Begrenzungsdreiecks hilft oder schadet der asymptotischen Leistung von Kirkpatricks Algorithmus nicht, da die Berechnung selbst eine lineare Zeit ist – aber sie ist für ästhetische Zwecke nützlich.

Praktische Ratschläge, Anwendungen und Bedenken

Die vorherigen Abschnitte konzentrierten sich darauf, warum es schwierig sein kann, rigoros über Computergeometrie nachzudenken.

In der Praxis müssen wir uns mit einer ganzen Reihe neuer Bedenken auseinandersetzen.

Erinnerst du dich an CCW? Sehen wir uns als netten Übergang noch eine seiner großartigen Qualitäten an: Es schützt uns vor den Gefahren von Fließkommafehlern.

Fließkommafehler: Warum CCW König ist

In meinem Kurs über Computergeometrie hat Bernard Chazelle, ein angesehener Professor, der mehr Artikel veröffentlicht hat, als ich zählen kann, zur Regel gemacht, dass wir keine Winkel erwähnen dürfen, wenn wir versuchen, einen Algorithmus oder eine Lösung zu beschreiben.

Warum? Winkel sind chaotisch. Winkel sind „schmutzig“. Wenn Sie einen Winkel berechnen müssen, müssen Sie dividieren oder eine Annäherung (alles, was zum Beispiel Pi betrifft) oder eine trigonometrische Funktion verwenden.

Wenn Sie einen Winkel in code berechnen müssen, werden Sie fast immer eine Annäherung vornehmen. Sie werden um einen winzigen Grad an Gleitkommagenauigkeit abweichen - was wichtig ist, wenn Sie auf Gleichheit testen. Sie können nach einem Punkt in der Ebene durch zwei verschiedene Methoden lösen und natürlich erwarten, dass p1.x == p2.x and p1.y == p2.y . Aber in Wirklichkeit wird diese Prüfung oft fehlschlagen. Außerdem (und ganz offensichtlich) haben diese Punkte dann unterschiedliche Hashes.

Um die Sache noch schlimmer zu machen, wird Ihr Fehlergrad zunehmen, wenn sich Ihre winzigen Unterschiede durch Ihre Berechnungen ausbreiten. (Für einige weitere wissenschaftliche Beispiele geht dieser Artikel darauf ein, was bei der Berechnung der konvexen Hülle oder der Delaunay-Triangulation schief gehen kann.)

Also, was können wir dagegen tun?

fast gleich

Ein Teil des Problems der Python-Computergeometrie besteht darin, dass wir in einer Welt, in der die Dinge selten genau sind, Genauigkeit verlangen. Dies wird häufiger zu einem Problem als beim Umgang mit Winkeln. Folgendes berücksichtigen:

 # Define two random points p1 = RandomPoint() p2 = RandomPoint() # Take the line through them l1 = Line(p1, p2) # Shift both points up by sqrt(2) p1.y += sqrt(2) p2.y += sqrt(2) l2 = Line(p1, p2) # Slope 'should' be the same? if abs(l1.slope - l2.slope) > 0: print "Error!" # Error!

Tatsächlich gibt dieser Code „Error!“ aus. ungefähr 70% der Zeit (empirisch). Wir können dieser Sorge begegnen, indem wir etwas nachsichtiger mit unserer Definition von Gleichheit umgehen; das heißt, indem ein gewisses Maß an Genauigkeit geopfert wird.

Ein Ansatz, den ich verwendet habe (und zB in einigen OpenCV-Modulen gesehen habe), besteht darin, zwei Zahlen als gleich zu definieren, wenn sie sich nur durch einen kleinen Wert Epsilon unterscheiden. In Python haben Sie möglicherweise:

 def almostEqual(x, y, EPSILON=1e-5): return abs(x - y) < EPSILON class Point(object): ... def __eq__(self, that): return (almostEqual(self.x, that.x) and almostEqual(self.y, that.y))

In der Praxis ist dies sehr hilfreich. Selten, wenn überhaupt, würden Sie zwei Punkte berechnen, die sich um weniger als 1e-5 unterscheiden, die eigentlich unterschiedliche Punkte sein sollen. Ich empfehle dringend, diese Art der Überschreibung zu implementieren. Ähnliche Methoden können zum Beispiel für Linien verwendet werden:

 class Line(object): ... def __eq__(self, that): return (almostEqual(self.slope, that.slope) and almostEqual(self.intercept, that.intercept))

Fortgeschrittenere Lösungen wurden natürlich vorgeschlagen. Zum Beispiel zielt die Denkschule der „exakten geometrischen Berechnung“ (in diesem Artikel beschrieben) darauf ab, dass alle Entscheidungspfade in einem Programm ausschließlich vom Vorzeichen einer Berechnung abhängen und nicht von ihrem genauen numerischen Wert, wodurch viele der damit verbundenen Bedenken beseitigt werden zu Gleitkommaberechnungen. Unser nahezu gleichberechtigter Ansatz kratzt nur an der Oberfläche, wird aber in der Praxis oft ausreichen.

CCW ist König

Auf einer höheren Ebene ist es (wohl) problematisch, dass wir unsere Lösungen sogar in Bezug auf so exakte Rechengrößen wie Winkel oder Punktkoordinaten definieren. Anstatt nur die Symptome anzugehen (dh Fließkommafehler mit almostEqual zu überschreiben), warum nicht die Ursache angehen? Die Lösung: Anstatt in Winkeln zu denken, denken Sie in CCW , was dazu beitragen wird, die mit Gleitkommaberechnungen verbundenen Bedenken zu abstrahieren.

Hier ist ein konkretes Beispiel: Angenommen, Sie haben ein konvexes Polygon P , einen Scheitelpunkt v und einen Punkt u außerhalb des Polygons. Wie können Sie herausfinden, ob die Linie uv P in konstanter Zeit über oder unter v schneidet oder überhaupt nicht?

Die Brute-Force-Lösung (abgesehen davon, dass sie linear und nicht konstant ist) wäre problematisch, da Sie einige genaue Linienschnittpunkte berechnen müssten.

Ein Ansatz mit konstanter Zeit, den ich gesehen habe, beinhaltet:

• Berechnen einiger Winkel mit arctan2 .
• Umrechnung dieser Winkel in Grad durch Multiplikation mit 180/Pi.
• Untersuchung der Beziehungen zwischen diesen verschiedenen Blickwinkeln.

Glücklicherweise hat der Autor die almostEqual -Technik verwendet, um die Fließkommafehler zu glätten.

Meiner Meinung nach wäre es besser, das Problem der Gleitkommafehler vollständig zu vermeiden. Wenn Sie sich ein paar Minuten Zeit nehmen, um das Problem auf Papier zu betrachten, können Sie eine Lösung erhalten, die vollständig auf CCW basiert. Die Intuition: Wenn die an v angrenzenden Eckpunkte auf derselben Seite von uv liegen, dann schneidet sich die Linie nicht; Andernfalls prüfen Sie, ob u und v auf derselben Seite der Linie zwischen den benachbarten Scheitelpunkten liegen, und vergleichen Sie je nach Ergebnis ihre Höhen.

Hier ist der Python-Code zum Testen der Schnittmenge über v (die Schnittmenge darunter kehrt nur die Richtung der Vergleiche um):

 def intersectsAbove(verts, v, u): """ Returns True if uv intersects the polygon defined by 'verts' above v. Assumes v is the index of a vertex in 'verts', and u is outside of the polygon. """ n = len(verts) # Test if two adjacent vertices are on same side of line (implies # tangency) if ccw(u, verts[v], verts[(v - 1) % n]) == ccw(u, verts[v], verts[(v + 1) % n]): return False # Test if u and v are on same side of line from adjacent # vertices if ccw(verts[(v - 1) % n], verts[(v + 1) % n], u) == ccw(verts[(v - 1) % n], verts[(v + 1) % n], verts[v]): return uy > verts[v].y else: return uy < verts[v].y

Die Lösung ist mit bloßem Auge nicht sofort ersichtlich, aber in der Sprache eines Algorithmus für Computergeometrie: „Gleiche Seite der Linie“ ist ein klassisches Element dieses bewährten Algorithmus.

Fertig ist besser als perfekt

In der rechnergeometrischen Literatur steckt oft ziemlich viel Zauberei in scheinbar einfachen Operationen. Dies gibt Ihnen die Wahl: Sie können die Dinge auf die harte Tour machen, indem Sie einem Papier folgen, das eine unglaublich fortschrittliche Lösung für ein nicht so fortgeschrittenes Problem definiert – oder Sie können die Dinge auf die einfache Art und Weise mit ein bisschen roher Gewalt tun.

Auch hier verwende ich ein Beispiel: das Abtasten eines zufälligen inneren Punkts aus einem beliebigen Polygon. Mit anderen Worten, ich gebe Ihnen ein einfaches Polygon und Sie geben mir einen zufälligen Punkt darin (gleichmäßig über das Polygon verteilt).

Oft werden zum Testen Innenpunkte benötigt. In diesem Fall haben Sie keine spezifischen Laufzeitanforderungen an den Berechnungsgeometriealgorithmus, der sie erzeugt (im Rahmen des Zumutbaren). Die schnelle und schmutzige Lösung, deren Implementierung ~ 2 Minuten dauert, besteht darin, einen zufälligen Punkt in einem Feld auszuwählen, das das Polygon enthält, und zu prüfen, ob sich der Punkt selbst innerhalb des Polygons befindet.

Beispielsweise können wir zweimal verfehlen und nur beim dritten Punkt ein gültiges Beispiel finden:

Hier ist der Code:

 class Polygon(object): ... def interiorPoint(self): """Returns a random point interior point""" min_x = min([px for p in self.points]) max_x = max([px for p in self.points]) min_y = min([py for p in self.points]) max_y = max([py for p in self.points]) def x(): return min_x + random() * (max_x - min_x) def y(): return min_y + random() * (max_y - min_y) p = Point(x(), y()) while not self.contains(p): p = Point(x(), y()) return p def contains(self, p): for i in range(self.n): p1 = self.points[i] p2 = self.points[(i + 1) % self.n] p3 = self.points[(i + 2) % self.n] if not ccw(p1, p2, p3): return False return True

Dies wird als Ablehnungsstichprobe bezeichnet: Nehmen Sie zufällige Punkte, bis einer Ihre Kriterien erfüllt. Auch wenn möglicherweise mehrere Stichproben erforderlich sind, um einen Punkt zu finden, der Ihren Kriterien entspricht, ist der Unterschied in der Praxis für Ihre Testsuite vernachlässigbar . Warum also noch härter arbeiten? Zusammenfassend: Scheuen Sie sich nicht, den schmutzigen Weg zu gehen, wenn es der Anlass erfordert.

Übrigens: Wenn Sie einen exakten Algorithmus für die Zufallsstichprobe wollen, gibt es hier einen cleveren, den ich unten implementiert habe. Das Wesentliche davon:

1. Triangulieren Sie Ihr Polygon (dh zerlegen Sie es in Dreiecke).
2. Wählen Sie ein Dreieck mit einer Wahrscheinlichkeit proportional zu seiner Fläche.
3. Nehmen Sie einen zufälligen Punkt innerhalb des gewählten Dreiecks (eine Operation mit konstanter Zeit).

Beachten Sie, dass dieser Algorithmus erfordert, dass Sie Ihr Polygon triangulieren, was dem Algorithmus sofort eine andere Laufzeitgrenze auferlegt, sowie die Notwendigkeit, dass Sie eine Bibliothek zum Triangulieren beliebiger Polygone haben (ich habe poly2tri mit Python-Bindungen verwendet).

 from p2t import CDT class Triangle(object): ... def area(self): return abs((Bx * Ay - Ax * By) + (Cx * By - Bx * Cy) + (Ax * Cy - Cx * Ay)) / 2 def interiorPoint(self): r1 = random() r2 = random() # From http://www.cs.princeton.edu/~funk/tog02.pdf return (1 - sqrt(r1)) * A + sqrt(r1) * (1 - r2) * B + r2 * sqrt(r1) * C class Polygon(object): ... def triangulate(self): # Triangulate poly with hole cdt = CDT(poly.points) triangles = cdt.triangulate() def convert(t): A = Point(tax, tay) B = Point(tbx, tby) C = Point(tcx, tcy) return Triangle(A, B, C) return map(convert, triangles) def interiorPoint(self): # Triangulate polygon triangles = self.triangulate() areas = [t.area() for t in triangles] total = sum(areas) # Calculate normalized areas probabilities = [area / total for area in areas] weighted_triangles = zip(triangles, probabilities) # Sample triangles according to area r = random() count = 0 for (triangle, prob) in weighted_triangles: count += prob # Take random point from chosen triangle if count > r: return triangle.interiorPoint()

Hoffentlich ist der zusätzliche Aufwand aus dem Code ersichtlich. Denken Sie daran: Wie sie bei Facebook sagen, „fertig ist besser als perfekt“. Dasselbe gilt für Probleme der Computergeometrie.

Visuelles und automatisiertes Testen

Da viele der Probleme, an denen Sie in der Computergeometrie arbeiten, in Bezug auf leicht sichtbare Qualitäten oder Quantitäten definiert sind, ist visuelles Testen besonders wichtig – obwohl es allein nicht ausreicht. Die ideale Testsuite verfügt über eine Kombination aus visuellen und randomisierten automatisierten Tests.

Auch hier gehen wir exemplarisch vor. Erwägen Sie, unsere Implementierung des Kirkpatrick-Algorithmus zu testen. In einem Schritt muss der Algorithmus das gegebene Polygon durch ein Dreieck begrenzen und den Bereich zwischen dem Polygon und dem äußeren Dreieck triangulieren. Hier ist ein visuelles Beispiel, bei dem die durchgezogene grüne Linie das anfängliche Polygon und die gestrichelten Linien den triangulierten Bereich definieren:

Die Bestätigung, dass diese Triangulation korrekt ausgeführt wurde, ist sehr schwer durch Code zu überprüfen, aber für das menschliche Auge sofort erkennbar. Hinweis: Ich empfehle dringend, Matplotlib zu verwenden, um Ihre visuellen Tests zu unterstützen – hier gibt es eine nette Anleitung.

Später wollen wir überprüfen, ob der Algorithmus Punkte korrekt lokalisiert. Ein randomisierter, automatisierter Ansatz wäre, für jedes Polygon eine Reihe von Innenpunkten zu generieren und sicherzustellen, dass wir das gewünschte Polygon zurückgeben. In Code:

 class TestLocator(unittest.TestCase): ... def runLocator(self, polygons): # Pre-process regions l = Locator(polygons) # Ensure correctness for polygon in polygons: # Test 100 random interior points per region for k in range(100): target = polygon.interiorPoint() target_polygon = l.locate(target) self.assertEqual(polygon, target_polygon) self.assertTrue(target_polygon.contains(target))

Wir könnten dann die runLocator Methode auf verschiedene Sätze von Polygonen anwenden, wodurch wir eine gut diversifizierte Testsuite erhalten.

Open-Source-Lösungen

Computational Geometry verfügt über eine schöne Suite von Open-Source-Bibliotheken und -Lösungen, die unabhängig von der Programmiersprache Ihrer Wahl verfügbar sind (obwohl C++-Bibliotheken unverhältnismäßig häufig aufzutauchen scheinen).

Die Vorteile der Verwendung vorhandener Open-Source-Lösungen (wie beim wissenschaftlichen Rechnen in Python) sind bekannt und wurden ausführlich diskutiert, sodass ich hier nicht weiter darauf eingehen werde. Aber ich dachte, ich würde ein paar Python-zentrierte Ressourcen erwähnen, die ich nützlich fand:

• poly2tri: Eine großartige Bibliothek für schnelle Triangulationen von Polygonen. Unterstützt auch (und das ist oft entscheidend) Polygone mit Löchern darin. Poly2tri wurde in C++ geschrieben, hat auch Python-Anbindungen und war recht einfach zum Laufen zu bringen. Sehen Sie sich meine triangulate Methode oben an, um einen Vorgeschmack auf die Funktionsaufrufe zu erhalten.
• scipy.spatial: Enthält Funktionen zum Berechnen konvexer Hüllen, Delaunay-Triangulationen und mehr. Schnell (wie immer), zuverlässig usw. Hinweis: Ich fand es nützlich, meinen eigenen Point -Datentyp mit einer toNumpy Methode zu verwenden: def np(self): return [self.x, self.y] . Dann könnte ich einfach scipy.spatial Methoden aufrufen, zB: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV: Die Open-Source-Computer-Vision-Bibliothek hat einige nette eigenständige Computational Geometry-Module. Insbesondere habe ich eine Zeit lang seine minimale umschließende Dreiecksfunktion verwendet, bevor ich sie selbst implementiert habe.

Fazit

Ich hoffe, dieser Beitrag hat Ihnen als Python-Entwickler einen Vorgeschmack auf die Schönheit der Computergeometrie gegeben, ein Thema, das reich an faszinierenden Problemen und ebenso faszinierenden Anwendungen ist.

In der Praxis stellen computergeometrische Implementierungen einzigartige Herausforderungen dar, die Sie dazu bringen werden, neue und aufregende Fähigkeiten zur Problemlösung zu üben.

Wenn Sie mehr erfahren möchten oder Fragen an mich haben, bin ich unter [email protected] erreichbar.