Rasterisierung eines Kreisbogens

[asdfman]

Mahlzeit. Mal sehen, ob ich formuliert bekomme, was ich möchte.

Ich habe ein quadratisches Raster und möchte ein Ding (z.B. Pixel) einen (unvollständigen) Kreisbogen um ein gegebenes zentrales Ding beschreiben lassen.
Mir ist als erstes der Midpoint Circle Algorithm eingefallen. Dabei wird nur ein Oktant rasterisiert und durch Spiegelung auf den Rest des Kreises abgebildet.
Die berechneten Teilbögen sind dadurch nicht zusammenhängend und die Reihenfolge der Pixel läuft teilweise mit und teilweise gegen den Uhrzeigersinn.
Daraus kann ich nicht trivial einen Pfad von einem Punkt auf dem Bogen zu einem beliebigen anderen herausfriemeln.

Spoiler: Mspaint Kunstwerk

Gibt es (schnelle) Verfahren, die dazu besser geeignet sind?
Kann ich die Ausgabe des oben genannten Verfahrens zuverlässig umsortieren, so dass ich eine Liste von benachbarten pixeln mit einem bestimmten Umlaufsinn bekomme?
Kann man das Verfahren so anpassen, dass es einen zusammenhängenden Pfad ausspuckt?

Sagt mal, was euch so einfällt.

LG, asdfmann

 

[Cool Master]

Welche Informationen liegen dir vor?

 

[asdfman]

Der Mittelpunkt und der Startpunkt (und damit auch der Radius), eine Richtung und die Anzahl gewünschter Schritte (von einem Punkt zum Nachbarn).

 

[Cool Master]

In dem Fall kannst du mit Grad rechnen. Du musst die "Schritte" nur in Grad umrechnen, damit sollte es möglich sein das ganze zu berechnen wenn ich aktuell nicht einen Denkfehler habe.

 

[asdfman]

Mit Schritt meine ich den Weg von einem Punkt zum nächsten und der hat kein konstantes Bogenmaß. Ein horizontaler bzw. vertikaler Schritt ist kürzer als ein diagonaler Schritt und der abgewanderte Anteil des Kreisbogens hängt auch davon ab, an welcher Stelle des Bogens der Schritt gemacht wird, weil die Punkte ja die Kreisbahn nur annähern und nicht exakt abbilden können.

 

[Doktor Kumpel]

Berechne den Kreis mithilfe des von dir geposteten Algorithmus. Danach hast du eine Liste mit Koordinaten. Diese gilt es zu sortieren.

Jeder Punkt hat eine x- und eine y-Koordinate. Berechne arcustangens(y/x) für jeden Punkt und nenne die nun entstandene Variable z. Sortiere deine Punkte in der Liste aufsteigend nach z. Da die Arcustangensfunktion monoton steigend ist, sind deine Punkte automatisch in der richtigen Reihenfolge.

Edit: Zumindest für eine Hälfte des Kreises sollte es so funktionieren.

Edit2: Der Mittelpunkt sollte die Koordinaten (0,0) haben.

 

[fhtagn]

Kann ich die Ausgabe des oben genannten Verfahrens zuverlässig umsortieren, so dass ich eine Liste von benachbarten pixeln mit einem bestimmten Umlaufsinn bekomme?

Der Algorithmus zeichnet Punkte parallel in acht Oktanten 0 bis 7. Die Punkte in den ungeraden Oktanten 1, 3, 5 und 7 sind gespiegelt. Wenn man also die Reihenfolge der Punkte in den ungeraden Oktanten umkehrt und dann die 8 Oktanten zusammenfügt, erhält man eine Liste von benachtbarten Punkten auf dem Kreisbogen entgegen dem Uhrzeigersinn, beginnend bei x=radius, y=0.

 

[asdfman]

Der Algorithmus zeichnet Punkte parallel in acht Oktanten 0 bis 7. Die Punkte in den ungeraden Oktanten 1, 3, 5 und 7 sind gespiegelt. Wenn man also die Reihenfolge der Punkte in den ungeraden Oktanten umkehrt und dann die 8 Oktanten zusammenfügt, erhält man eine Liste von benachtbarten Punkten auf dem Kreisbogen entgegen dem Uhrzeigersinn, beginnend bei x=radius, y=0.

Manchmal kommt mir eine einfache Lösung nicht in den Sinn, weil mir das Problem viel komplizierter vorkommt, als es in Wirklichkeit ist.
Die Lösung sollte genau das tun, was ich möchte. Vielen lieben Dank!