Jak narysować linię prostą między dwoma punktami na mapie bitowej?

Bawię się mapami wysokości (mapami bitowymi), staram się tworzyć własne w swojej grze i muszę zaimplementować podstawowe metody rysowania. Szybko zdałem sobie sprawę, że rysowanie linii prostych nie jest tak proste, jak myślałem.

To proste, jeśli punkty mają współrzędne X lub Y, lub jeśli są wyrównane, dzięki czemu można narysować idealnie ukośną linię. Ale we wszystkich innych przypadkach jest to trudniejsze.

Jakiego algorytmu używasz do określania, jakie piksele należy pokolorować, aby stał się „linią prostą”?

Myślę, że potrzebujesz algorytmu liniowego Bresenhama .

Z tego, co pamiętam, służy do określania, który punkt powinien być pokolorowany, a nie jak bardzo każdy punkt powinien być pokolorowany.

Algorytm liniowy Bresenhama można użyć do określenia, które punkty na siatce rastrowej mają zostać narysowane, aby uzyskać odpowiednie wizualne przybliżenie segmentu linii.

Algorytm obejmuje rasteryzację linii zdefiniowanej przez początek i punkty końcowe w przestrzeni współrzędnych, gdzie początek znajduje się w lewym górnym rogu. Zakłada się, że współrzędne całkowite odwzorowują się na centra pikseli. Warto zauważyć, że podstawowa postać algorytmu obejmuje tylko jedną oktanę koła: tę, w której linia ma rosnące współrzędne X i Y, ale ujemne nachylenie o wartości bezwzględnej mniejszej niż 1. Wszystkie inne oktany można wyprowadzić jako proste przekształcenia tego podstawowy oktant.

W psuedocode ta podstawowa forma wygląda następująco:

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
        }
    }
}

Witryna Rosetta Code zawiera zbiór konkretnych wdrożeń w różnych językach .

Może Cię również zainteresować algorytm linii Wu , który pozwala na wygładzanie krawędzi.

Oto niezwykle prosty sposób rysowania linii. Funkcję tę można łatwo zmienić w celu użycia w projektach.

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;
    }
}