Rastern Sie ein 2D-polygon

Brauche ich zum erstellen einer binären bitmap aus einer geschlossenen 2D-polygon dargestellt als eine Liste von Punkten. Könnten Sie bitte zeigen Sie mir auf eine effiziente und ausreichend einfache algorithmen zu tun, dass, oder, noch besser, einige C++ - code?

Vielen Dank!

PS: ich möchte vermeiden, das hinzufügen einer Abhängigkeit zu meinem Projekt. Allerdings, wenn Sie vorschlagen, eine open-source-Bibliothek, kann ich immer betrachten Sie den code, so kann es nützlich sein, auch.

InformationsquelleAutor static_rtti | 2009-08-27
  1. 11

    Magic google die phrase, die Sie wollen, ist entweder "non-zero-winding-Regel" oder "ungerade polygon fill".

    Finden Sie auf der wikipedia-Einträge für:

    Beide sind sehr einfach zu implementieren und ausreichend schnell für die meisten Zwecke. Mit etwas Geschick, kann man Sie geglättet als gut.

    • ist das nicht over-kill für einfache Polygone?
    • Was ist ein einfaches polygon? @static_rtti nicht angeben, wie viele Punkte oder wenn die Polygone immer konvex sein, daher ist eine Allgemeine Lösung ist die richtige Antwort. NZW-und EO sind po-einfach und eignen sich für den scanline-orientierte Lösungen, etc, etc, etc.
    • Danke, das ist genau das, was ich gesucht habe! Googeln Zeug kann tückisch sein, wenn Sie nicht haben, die Zauberformel 🙂
    • ein einfaches polygon ist, dessen Segmente nicht kreuzen. siehe en.wikipedia.org/wiki/Simple_polygon
    InformationsquelleAutor plinth
  2. 5

    Können Sie das polygon fill-routine in Pygame. Blick auf die draw_fillpoly Funktion.

    Der Algorithmus ist ziemlich einfach. Es findet alle Positionen, die jedes segment schneidet entlang der Y-Achse. Diese Schnittpunkte werden sortiert und dann horizontal füllt jedes paar von Kreuzungen.

    Dieser wird mit komplexen und sich überschneidenden Formen, aber offensichtlich konnte man crush dieser Algorithmus mit großen Mengen von Segmenten.

    • nicht zu verwandten, aber btw Pete Sie sind genial für die Herstellung von pygame 🙂
    InformationsquelleAutor Peter Shinners
  3. 3
    • Ihr polygon triangulieren
    • Raster jedes der Dreiecke (wenn Sie mit einer GPU, dann kann es für Sie stattdessen, es ist eine primitive operation der GPUs)
      • Wenn das Dreieck nicht ein segment, die parallel zur x-Achse, dann brechen Sie in zwei Dreiecke mit einer Linie, die parallel zur x-Achse und geht durch den Punkt mit der median-y
      • Nun die Verbleibende Aufgabe ist es, ein Dreieck zeichnen, die eine Passage, die parallel zur x-Achse. So ein Dreieck hat eine Links-Seite-segment und einer rechten Seite-segment
      • Durchlaufen der Dreiecks-scan-Zeilen (min-y max-y). Für jedes y berechnen Sie die linken und rechten Segmente und Punkte in, die scanlines. Füllen Sie das scanline-segment diese zwei Punkte (eine einfache memset).

    Komplexität ist O(Fläche in Pixel)

    • Wie würden Sie die Option "Rastern", die daraus resultierenden Dreiecke? Durch die quer durch das ganze Bild jedes mal? Ist das nicht wahrscheinlich zu sein sehr langsam?
    • was meinst du, die quer durch das ganze Bild jedes mal?
    • Ich fügte hinzu, eine Erklärung, wie zum Rastern eines Dreiecks
    • Der entscheidende Punkt ist hier "berechnen Sie die linken und rechten Segmente". Tun Sie es getrennt für jede Scanzeile ist zu langsam; ein besserer Weg ist die Berechnung der Schrittweite, und es auf den ersten Wert.
    • Ich denke, diese Antwort Glossen über die Komplexität mit der triangulation des Polygons. Für einfache Polygone, nicht so schlecht. Aber für selbst schneidende Polygone dies ist eher beteiligt. - Siehe angusj.com/delphi/clipper.php als ein Beispiel.
    InformationsquelleAutor yairchu
  4. 2

    Für eine robuste Umsetzung der "gerade-ungerade-Regel"

    Sehen Darel Rex Finley die Effiziente Polygon Füllen, oder Blender version es.

    Dies ist eine ungerade/sogar füllen-Methode, die unterstützt sich selbst schneidenden Linien, ohne komplexen code zu erkennen, solche Situationen, und nicht davon abhängig, Wicklung (das polygon kann Umgekehrt werden, und die gleichen Ergebnisse liefern).

    Update habe ich gemacht, eine optimierte version von Darel Rex ' s Methode, die verhindert, dass Schleifen über alle Koordinaten für jedes y-pixel.

    Stand-alone-Implementierungen:

    Während speedup wird wahrscheinlich exponentiell sein, Von einem schnellen test, rund 7,5 x schneller (11x beim entfernen round nennen), mit einem beliebigen handgezeichneten scribble über eine 2540x1600 region, YMMV.

    InformationsquelleAutor ideasman42
Schreibe einen Kommentar