Der Algorithmus beginnt mit einem zuvor gefundenen Pfad, in diesem Fall einer Liste von Dreiecken:
Der Code am unteren Rand von Mikkos Blogbeitrag erstellt das Portals-Array, das eine Liste von Liniensegmenten darstellt, die die Liniensegmente zwischen den Polygonen des Pfades darstellen. Dies sind die "Portale", durch die der geglättete Pfad verlaufen muss (oder die Polygonkanten von "Verfolgen wir die Polygonkantenmittelpunkte"). Beachten Sie, dass die Portalliste mit degenerierten Liniensegmenten an den Start- und Zielpunkten beginnt und endet.
Diese Portalliste wird in seinen Bildern als gelb gepunktete Liniensegmente dargestellt.
Der Algorithmus beginnt mit einem breiten Trichter und fährt fort, indem die Trichterseiten iterativ entlang der Portalseitenpunkte (den Endpunkten der Liniensegmente) nach vorne bewegt werden, solange dies den Trichter festzieht (AD).
Dies bedeutet, dass bei jeder Vorwärtsbewegung die Trichterkanten nach innen verschoben werden sollten. Dies kann anhand des Kreuzprodukts der Vektoren überprüft werden, die die alte Seite und die potenzielle neue Seite darstellen ( P × Q im Bild unten; siehe auch triarea2Mikkos Code). Wenn eine Bewegung nach vorne für eine Seite den Trichter nicht straffen würde, aktualisieren wir diese Seite nicht für die aktuelle Iteration der Portale (E).
Der andere Fall, der behandelt werden muss, ist, wenn der Trichter zu einem Liniensegment ausartet. Um dies zu berücksichtigen, prüft der Algorithmus, ob sich eine der Seiten auf der "falschen" Seite befindet, indem er das Kreuzprodukt erneut verwendet, diesmal mit den Vektoren, die von der Trichterspitze und den Endpunkten der rechten und linken Seite erzeugt werden ( R × S in das Bild unten).
Ist dies der Fall, wird der Vektor von der Trichterspitze und dem korrekten seitlichen Endpunkt zum geglätteten Pfad ( R in der Abbildung oben) hinzugefügt und der Algorithmus mit seinem Endpunkt als neuer Spitze (FG) neu gestartet, sofern nicht Natürlich, wenn es der Zielpunkt ist.
