Wie zeichnet man eine gerade Linie zwischen zwei Punkten in einer Bitmap?

Ich spiele mit Höhenkarten (Bitmaps) herum und versuche, einige meiner eigenen in meinem Spiel zu erstellen. Dazu muss ich einige grundlegende Zeichenmethoden implementieren. Ich habe schnell gemerkt, dass das Zeichnen von geraden Linien nicht so einfach ist, wie ich dachte.

Es ist ganz einfach, wenn Ihre Punkte eine X- oder Y-Koordinate haben oder wenn sie so ausgerichtet sind, dass Sie eine perfekt diagonale Linie zeichnen können. Aber in allen anderen Fällen ist es schwieriger.

Mit welchem ​​Algorithmus bestimmen Sie, welche Pixel gefärbt werden müssen, damit eine "gerade" Linie entsteht?

Ich denke, was Sie brauchen, ist Bresenhams Linienalgorithmus .

Soweit ich mich erinnere, wird es verwendet, um zu bestimmen, welcher Punkt gefärbt werden soll, und nicht, wie viel jeder Punkt gefärbt werden soll.

Mit dem Linienalgorithmus von Bresenham können Sie bestimmen, welche Punkte in einem Rastergitter geplottet werden sollen, um eine angemessene visuelle Approximation eines Liniensegments zu erzielen.

Der Algorithmus deckt die Rasterung einer Linie ab, die durch den Ursprung und die Endpunkte in einem Koordinatenraum definiert ist, in dem sich der Ursprung oben links befindet. Es wird angenommen, dass Ganzzahlkoordinaten auf Pixelmitten abgebildet werden. Insbesondere deckt die Grundform des Algorithmus nur einen Oktanten des Kreises ab: denjenigen, bei dem die Linie zunehmende X- und Y-Koordinaten aufweist, aber eine negative Steigung mit einem Absolutwert von weniger als 1. Alle anderen Oktanten können als einfache Transformationen davon abgeleitet werden Grundoktant.

Im Pseudocode sieht diese Grundform so aus:

void DrawLine(Point origin, Point endpoint, Bitmap surface) {
    deltaX = endpoint.X - origin.X
    deltaY = endpoint.Y - origin.Y
    error = 0

    // Note the below fails for completely vertical lines.
    deltaError = absoluteValue(deltaY / deltaX)

    Y = origin.Y
    for (X from origin.X to endpoint.X) {
        surface.PlotPixel(X, Y)
        error = error + deltaError 
        if (error >= 0.5) {
            ++Y;
            error -= 1.0
        }
    }
}

Die Rosetta Code-Website enthält eine Sammlung konkreter Implementierungen in verschiedenen Sprachen .

Sie könnten auch an Wus Linienalgorithmus interessiert sein , der Anti-Aliasing ermöglicht.

Hier finden Sie eine äußerst einfache Methode zum Zeichnen von Linien. Die Funktion kann leicht geändert werden, um in Projekten verwendet zu werden.

void draw_line(float x0, float y0, const float& x1, const float& y1)
{
    float x{x1 - x0}, y{y1 - y0};
    const float max{std::max(std::fabs(x), std::fabs(y))};
    x /= max; y /= max;
    for (float n{0}; n < max; ++n)
    {
        // draw pixel at ( x0, y0 )
        x0 += x; y0 += y;
    }
}