Как нарисовать «линию» в двумерном массиве (симулякр для экрана)

Question

Я работаю над проектом, который будет распечатываться в растровое изображение (точнее, в формате RAW, но это не важно для вопроса), но я работаю в двумерном массиве в программе.

Я хочу иметь возможность нарисовать линию от точки (a, b) к точке (x, y) для любых произвольных значений a, b, x и y. Мне не нужно ничего такого, как сглаживание; в этом пункте ближайший сосед в порядке. для примера, давайте предположим, что у меня есть 5x5 2d массив, например:

00,10,20,30,40
01,11,21,31,41
02,12,22,32,42
03,13,23,33,43
04,14,24,34,44

Теперь давайте предположим, что я хочу нарисовать линию между 04 и 42. Я хочу, чтобы был способ надежно придумать что-то вроде этого:

0,0,0,0,0
0,0,0,0,0
0,0,0,1,1
0,1,1,1,0
1,1,0,0,0

Я уверен, что кто-то думает: "А, этот парень отсталый? Он потерпел неудачу здесь?", Но, пожалуйста, пошутите!

Я работаю в C ++, но это должно быть вторично по отношению к реальному вопросу.

Answer 1

Алгоритм линии Брезенхама - это то, что вам нужно:

Иллюстрация результата алгоритма линии Брезенхэма.

Answer 2

Как сказал Симукал, Брезенхем - это путь. Вот наивная реализация.

Не идеальный C-код, и вы должны сделать немного магии, если вы хотите толщину на отрезках. Кроме того, вы должны пройти вдоль х, а не у, как я здесь. Это более кеш-дружественный. Если вы хотите сглаживать, ищите «Wu-линии». Это умный прием - использовать дробь с позиций в качестве градиента.

Советы по толщине линии: Вычислите нормализованный вектор V (-y, x) из v1 - v0, если ваши вершины расположены против часовой стрелки, или V (y, -x), если ваши вершины расположены по часовой стрелке. Тогда у вас есть четыре точки, определенные как: v0, v0 + V * ширина линии, v1 и v1 + V * ширина линии. Растеризация этого четырехугольника путем интерполяции по краям. Но если вы уже хотите зайти так далеко, вы, вероятно, вместо этого кодируете растеризатор треугольника.

typedef struct Point 
{
    int x, y;
} Point;

typedef struct Color {
    unsigned char r,g,b;
} Color;

#define RGB(x) (x->r << 16) | (x->g << 8) | (x->b)

int DrawLinestrip(int width, int height, unsigned int* buffer,
    Color* color, Point* verts, int count)
{
    int i, x,y,xbegin, xdelta, ydelta, xdiff, ydiff, accum, sign;
    Point *p1, *p2;
    if(!verts || count < 2)
        return -1;

    for(i=1; i<count; ++i){
        if(verts[i].y > verts[i-1].y){ /* sort by y */
            p1 = &verts[i-1];
            p2 = &verts[i];
        } else {
            p1 = &verts[i];
            p2 = &verts[i-1];
        }

        xdelta = p2->x - p1->x;
        ydelta = p2->y - p1->y;
        accum = 0;
        sign = 0;

        if(!xdelta && !ydelta)
            continue;
        else if(!xdelta && ydelta){ /* Special case: straight vertical line */
            x = p1->x;
            for(y=p1->y; y<(p1->y + ydelta); ++y){
                buffer[x + y*width] = RGB(color);
            }
        }
        else if(xdelta && !ydelta){ /* Special case: straight horisontal line */
            y = p1->y;
            xbegin = (p1->x < p2->x ? p1->x : p2->x);
            for(x=xbegin; x<=xbegin+abs(xdelta); ++x){
                buffer[x + y*width] = RGB(color);
            }
        }
        else {
            xdiff = (xdelta << 16) / ydelta;
            ydiff = (ydelta << 16) / xdelta;

            if( abs(xdiff) > abs(ydiff) ){ /* horizontal-major */
                y = p1->y;
                if(xdelta < 0){ /* traversing negative x */
                    for(x=p1->x; x >= p2->x; --x){
                        buffer[x + y*width] = RGB(color);
                        accum += abs(ydiff);
                        while(accum >= (1<<16)){
                            ++y;
                            accum -= (1<<16);
                        }
                    }
                } else { /* traversing positive x */
                    for(x=p1->x; x <= p2->x; ++x){
                        buffer[x + y*width] = RGB(color);
                        accum += abs(ydiff);
                        while(accum >= (1<<16)){
                            ++y;
                            accum -= (1<<16);
                        }
                    }
                }
            } else if( abs(ydiff) > abs(xdiff) ){ /* vertical major */
                sign = (xdelta > 0 ? 1 : -1);
                x = p1->x;
                for(y=p1->y; y <= p2->y; ++y){
                    buffer[x + y*width] = RGB(color);
                    accum += abs(xdiff);
                    while(accum >= (1<<16)){
                        x += sign;
                        accum -= (1<<16);
                    }
                }            
            } else if( abs(ydiff) == abs(xdiff) ){ /* 45 degrees */
                sign = (xdelta > 0 ? 1 : -1);
                x = p1->x;
                for(y=p1->y; y <= p2->y; ++y){
                    buffer[x + y*width] = RGB(color);
                    x+= sign;
                }
            }
        }
    }
    return 0;
}