Elegant/Reinigen (spezieller Fall) Straight-line Grid-Traversal Algorithmus?

Was Sie wollen, ist ein bestimmter Fall von einem supercover, die alle Pixel durchschnitten von einem geometrischen Objekt. Das Objekt kann eine Linie oder ein Dreieck, - und es gibt Verallgemeinerungen auf höhere Dimensionen.

Sowieso, hier ist eine Umsetzung für Liniensegmente. Die Seite vergleicht auch die supercover mit dem Ergebnis des Bresenham-Algorithmus - Sie sind anders.


_{(Quelle: free.fr)}

Ich weiß nicht, ob Sie sich der Algorithmus, der dort als eleganter/sauberer, aber es scheint einfach genug, um zu passen Sie den code und gehen auf andere Teile Ihres Projekts.

Durch die Art und Weise, Ihre Frage impliziert, dass der Bresenham-Algorithmus ist nicht effizient für große Netze. Das ist nicht wahr - es erzeugt nur die Pixel auf der Linie. Sie müssen nicht zu einer wahr/falsch-test für jedes pixel auf dem Gitter.

Update 1: ich bemerkt, dass in dem Bild gibt es zwei "extra" - Blaue Quadrate, glaube ich, dass die Linie nicht passieren. Einer von Ihnen ist neben dem 'h' in 'Dieser Algorithmus'. Ich weiß nicht, ob das spiegelt ein Fehler im Algorithmus oder die Grafik (aber siehe @kikito ' s Kommentar unten).

Im Allgemeinen, die "harten" Fälle wahrscheinlich, wenn die Linie geht genau durch einen Gitterpunkt. Ich spekulieren, dass, wenn du floating-point -, der float-point-Fehler können Sie Durcheinander zu bringen in diesen Fällen. In anderen Worten, algorithmen sollte wahrscheinlich stick auf integer-Arithmetik.

Update 2: Eine andere Implementierung.

Gibt es einen sehr einfachen Algorithmus für Dein problem, die läuft in linearer Zeit:

1. Gegeben seien zwei Punkte A und B, bestimmen Sie die Schnittpunkte der geraden (A, B) mit jede vertikale Linie des Rasters, das liegt innerhalb dieses Intervalls.
2. Legen Sie zwei Besondere Schnittpunkte im inneren der Zellen mit A und B am Anfang/Ende der Liste aus Punkt 1.
3. Interpretieren jede zwei aufeinander folgenden Schnittpunkten als die min-und max-Vektoren einer Achse ausgerichtet Rechteck und markiere alle Rasterzellen, die sich innerhalb dieses Rechtecks (dieses ist sehr einfach (Schnittpunkt der beiden Achsen ausgerichtet rects), vor allem wenn man bedenkt, dass das Rechteck hat eine Breite von 1 und nimmt daher nur 1 Spalte des Rasters)

Beispiel:

+------+------+------+------+
|      |      |      |      |
|      |      | B    *      |
|      |      |/    |      |
+------+------*------+------+
|      |     /|      |      |
|      |    /|      |      |
|      |   / |      |      |
+------+--/---+------+------+
|      | /   |      |      |
|      |/    |      |      |
|      *      |      |      |
+-----/+------+------+------+
|    /|      |      |      |
*   A  |      |      |      |
|      |      |      |      |
+------+------+------+------+ 

"A" und "B" sind die Punkte, die Kündigung der Linie dargestellt durch "/". "*" markiert Schnittpunkte der Linie mit dem Netz. Die beiden speziellen Schnittpunkte benötigt werden, um markieren Sie die Zellen, die enthalten A & B und zu handhaben besonderen Fällen, wie A. x == B. x

Eine optimierte Implementierung benötigt Θ(|B. x - A. x| + |B. y - A. y|) Zeit für eine Zeile (A, B). Weiter kann man schreiben Sie diesen Algorithmus, um zu bestimmen Schnittpunkte mit der horizontalen grid-Linien, wenn das einfacher ist für die Umsetzer.

Update: Border-Fällen

Als brainjam richtig betont in seiner Antwort, die harten Fälle sind die, wenn eine Linie geht genau durch einen Gitterpunkt. Nehmen wir an ein solcher Fall tritt auf, und die Gleitkomma-arithmetische Operationen ordnungsgemäß zurückgeben, die einen Schnittpunkt mit integriertem Koordinaten. In diesem Fall wird der vorgeschlagene Algorithmus markiert nur die richtigen Zellen (wie durch das Bild von der OP).

Jedoch, floating-point-Fehler auftreten werden, früher oder später und falsche Ergebnisse liefern. Aus meiner Meinung nach, auch die Verwendung von Doppel-nicht ausreichen und man sollte wechseln zu einer Decimal Nummer geben. Eine optimierte Umsetzung führen Θ(|max.x - min.x|) Ergänzungen auf, die Daten geben Sie nacheinander die Einnahme von Θ(log max.y) Zeit. Das bedeutet, dass im schlimmsten Fall (die Zeile ((0, 0), (N, N)) mit riesigen N (> 10⁶) der Algorithmus degradiert zu einem O(N log N) worst case Laufzeit. Auch die Umschaltung zwischen der vertikalen und/oder horizontalen Rasterlinie Kreuzung-Erkennung abhängig von der Steigung der geraden (A, B) nicht helfen, im schlimmsten Fall, aber es ist sicher nicht in der durchschnittlichen Fall - ich würde nur in Erwägung ziehen, umzusetzen, wie ein switch, wenn Sie ein profiler-Erträge der Decimal - Operationen, die den Flaschenhals.

Schließlich kann ich mir vorstellen, dass einige kluge Leute möglicherweise in der Lage zu kommen mit einem O(N) Lösung, die es richtig sich mit dieser Grenze Fällen. Alle Ihre Vorschläge sind willkommen!

Korrektur

brainjam darauf hingewiesen, dass ein decimal-Datentyp ist nicht befriedigend, auch wenn es bedeuten kann beliebiger Genauigkeit Gleitkomma-zahlen, da z.B. ¹/₃ können nicht korrekt wiedergegeben werden. Deshalb sollte man einen Teil der Daten geben, die sollten in der Lage sein zu handhaben Grenze Fällen richtig. Thx brainjam! 🙂