Rasterung eines 2D-Polygons

Question

Ich muss eine binäre Bitmap aus einem geschlossenen 2D-Polygon erstellen, das als Liste von Punkten dargestellt wird. Könnten Sie mir bitte auf effiziente und ausreichend einfache Algorithmen hinweisen, um das zu tun, oder, noch besser, etwas C++ - Code?

Vielen Dank!

PS: Ich möchte vermeiden, eine Abhängigkeit zu meinem Projekt hinzufügen. Wenn Sie jedoch eine Open-Source-Bibliothek vorschlagen, kann ich mir den Code immer ansehen, damit er auch nützlich sein kann.

Answer 1

Die magische google Phrase, die Sie wollen, ist entweder "nicht-Null-Wicklungsregel" oder "gerade ungerade Polygonfüllung".

Siehe Wikipedia-Einträge für:

• non-zero winding rule
• even odd polygon fill

Beide sind sehr einfach für die meisten Zwecke zu implementieren und schnell genug. Mit einiger Schlauheit können sie auch antialiasiert werden.

Answer 2

• Triangulate your polygon
• Raster jedes der Dreiecke (wenn Sie eine GPU dann verwenden kann es stattdessen für Sie tun, es ist eine primitive Operation von GPUs)
  • Wenn das Dreieck nicht über ein Segment, das parallel zur x-Achse ist, dann brechen Sie es in zwei Dreiecke mit einer Linie, die parallel zur x-Achse ist und durchläuft seinen Punkt mit dem Median-y
  • Jetzt ist die verbleibende Aufgabe, ein Dreieck zu zeichnen, die ein Segment, das parallel zur x-Achse ist. Ein solches Dreieck hat ein Segment auf der linken Seite und ein Segment auf der rechten Seite
  • Iterieren Sie die Scanlinien des Dreiecks (min-y bis max-y). Berechne für jedes y die Punkte des linken und rechten Segments in diesen Scanlinien. Füllen Sie das Scanline-Segment mit diesen beiden Punkten (ein einfaches Memset).

Komplexität ist O (Bereich in Pixeln)

Answer 3

Sie können die Polygonfüllprozedur Routine in Pygame überprüfen. Schauen Sie sich die draw_fillpoly Funktion an.

Der Algorithmus ist ziemlich einfach. Es findet alle Positionen, die jedes Segment entlang der Y-Achse schneidet. Diese Schnittpunkte werden sortiert und füllen dann horizontal jedes Kreuzungspunktpaar aus.

Dies wird komplexe und sich überschneidende Formen behandeln, aber offensichtlich können Sie diesen Algorithmus mit großen Mengen von Segmenten zerquetschen.

Answer 4

Für eine robuste implimentation der "even-odd rule"

Siehe Darel Rex Finley's Efficient Polygon Fill oder Blender's version davon.

Dies ist ein ungerade/gerade Füllverfahren, die selbstschneidende Linien unterstützt, ohne komplexen Code zu benötigen, um solche Situationen zu erkennen, und hängt nicht auf kurvigen (das Polygon kann dieselben Ergebnisse ergeben und umgekehrt werden).

---

aktualisieren, hat ich eine optimierte Version von Darel Rex Methode, die alle über Looping vermeidet Koordinaten für jedes y-Pixel.

Stand-alone-Implementierungen:

• C99.
• Rust (mit Tests).

Während Speedup wahrscheinlich exponentielle sein wird, von einem schnellen Test, die um 7,5x schneller (11x, wenn round Anruf zu entfernen), unter Verwendung einer willkürliche Hand gezeichnet Scribble über eine 2540x1600 Region, YMMV.