Präziser Subpixel-Linienzeichnungsalgorithmus (Rasterisierungsalgorithmus)

Ich brauche einen Algorithmus, der (ein bisschen) langsamer sein kann als der Bresenham-Linienzeichnungsalgorithmus , muss aber ein viel genauer. Mit 'genau' meine ich: Jeder berührte Pixel sollte gedruckt werden. Nicht mehr, aber auch nicht weniger! Das bedeutet, dass die Verwendung einer dickeren Linie oder ähnlichem keine Option ist, da zu viele Pixel beteiligt sind. Ich brauche auch kein grafisches Framework oder ähnliches, wie es gefragt vorher , ich brauche die Algorithmus! Die Anwendung ist nicht wirklich in 'Grafiken' ist es in der Geografiebereich , wobei Pixel" Kacheln "sind.

Das Hauptproblem für mich ist, dass ich Subpixel-Präzision brauche, was bedeutet, dass eine Linie bei 0,75 / 0,33 und nicht nur bei 0/0 beginnen könnte, wie es bei Integer-Werten der Fall ist. Ich habe versucht, eine funktionierende Lösung für die letzten Stunden zu erstellen, kann aber nicht funktionieren - es gibt zu viele Randfälle.

Zuerst dachte ich eine Anti-Alias-Version wie der Algorithmus von Wu sollte es machen, aber es druckt zu viele Pixel (insbesondere für Start- und Endpunkte) und in bestimmten Fällen fehlen noch einige Pixel z für sehr kurze Zeilen.

Dann habe ich versucht, Bresenham zum Laufen zu bringen, wo ich das zweite "if" durch "else if" ersetzt habe, wie hier , und es ist näher, aber immer noch nicht da. Dann habe ich versucht, den Bresenham von Integer- in Float-Präzision zu bewegen, was zu einer Endlosschleife führte (da die x, y-Werte über die Endbedingung if (y1 == y2 && x1 == x2) gesprungen sind).

Ich könnte die naive Linienzeichnung verwenden, aber welche delta sollte ich verwenden? Z.B. Wenn ich 0.1 benutze, werde ich immer noch einige Pixel vermissen und kleinere Werte werden wahrscheinlich zu lange dauern (und immer noch Pixel vermissen).

Eine funktionierende Lösung in C / Java / ... wäre willkommen. Zumindest sollte es für Octant 1 funktionieren, aber eine vollständige Lösung wäre noch schöner.

Update : Ich habe folgende Idee: Mit der naiven Linienrasterisierung können Sie für jeden Punkt 4 Pixel-Kandidaten berechnen. Überprüfen Sie dann diese 4 Pixel, wenn die Linie sie wirklich kreuzt. Aber ich bin mir nicht sicher, ob die Linie / Kasten-Kreuzung schnell genug sein kann.