Координаты по которым идет линия. Куда копать?

Не могу даже вопрос загуглить. Но вкратце смогу изложить здесь, прошу сказать куда копать вообще.

 

Задача - провести линию из точки A в точку B.

 

Допустим, имеем матрицу 8х8.

С тем, чтобы нарисовать нечто, идущее исключительно по одной из координат (например, из точки (0, 2) в точку (15, 2)) проблем нет - просто идем по памяти и меняем значение.

Когда нужно провести линию из (3, 1) в (7, 4) нужно провести расчеты. Я не понимаю какие, и прошу вас сказать - куда копать?

 

Но, допустим, результаты расчетов такие:

(3,1) -> (4,2) -> (5,3) -> (6,4) -> (7,4)

Могли бы быть и немного иными, но все равно суть не особо меняется.

 

Нужно как-то высчитать шаги по Y и X, какие именно пиксели должны быть закрашены. Просто скажите куда копать.

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

Ну там первый случай, когда можно дойти тупо по диагонали, а второй, когда надо будет ещё делать шажок по горизонтали. Обе координаты увеличиваешь или уменьшаешь на 1 одновременно, до тех пор пока одна из них не поравняется с нужной тебе координатой, тогда меняешь уже только одну другую. 

 

NoMercyPWNZ сказал(а):↑

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

Нажмите, чтобы раскрыть...

Я тупой, но вебмакакинг мне не нравится

denton сказал(а):↑

Ну там первый случай, когда можно дойти тупо по диагонали, а второй, когда надо будет ещё делать шажок по горизонтали. Обе координаты увеличиваешь или уменьшаешь на 1 одновременно, до тех пор пока одна из них не поравняется с нужной тебе координатой, тогда меняешь уже только одну другую. 

Нажмите, чтобы раскрыть...

Черт, придется пол часа думать над тем, что ты сказал

denton сказал(а):↑

Ну там первый случай, когда можно дойти тупо по диагонали, а второй, когда надо будет ещё делать шажок по горизонтали.

Нажмите, чтобы раскрыть...

Ну эт как я и сказал

Kagon сказал(а):↑

С тем, чтобы нарисовать нечто, идущее исключительно по одной из координат (например, из точки (0, 2) в точку (15, 2)) проблем нет - просто идем по памяти и меняем значение.

Нажмите, чтобы раскрыть...

С описанной в ОП-посте проблемой я столкнулся еще год назад, когда писал API для графики. Квадраты всякие простые я сделал, и линии меняющие только одну из координат, а вот с другими вещами у меня сложности возникли.

denton сказал(а):↑

Обе координаты увеличиваешь или уменьшаешь на 1 одновременно, до тех пор пока одна из них не поравняется с нужной тебе координатой, тогда меняешь уже только одну другую. 

Нажмите, чтобы раскрыть...

Допустим, нужно мне из точки 0;0 в 3;8

1. 0;0 + 1;1 = 1;1

...

denton сказал(а):↑

до тех пор пока одна из них не поравняется с нужной тебе координатой, тогда меняешь уже только одну другую. 

Нажмите, чтобы раскрыть...

Это один из основных вопросов поста - как понять, какая же мне нужна

 

Вон мужик что-то про линейную функцию сказал, я загуглил и ничего не понял, думаю разобраться, может, ответ найду. Там про векторы всякие пишут, это вроде к линейной алгебре имеет отношение. А я ничего труднее квадратных уравнений не считал в своей жизни, понимаешь.

в целом согласен с оратором на 1 месте

чуток дополню:

 

уравнение прямой можно задать формулой Ax + By + C = 0 или (y - y1) / (y2 - y1) = (x - x1) / (x2 - x1)

в общем виде: (y1 - y2) * x + (x2 - x1) * y + (x1y1 - x1x2 - x2y1) = 0

 

если получить y = f(x), то выйдет: y = - ( (x1y2 - x1x2 - x2y1) + (y1 - y2) * x ) / (x2 - x1) )

 

далее берешь переменную (int k  = x1 ; k <= x2; k++) и смотришь соотв. y(k), сохраняешь значения в 2массиве, что-то типа такого вообщем если я нигде не ошибся

 

вот на Си:

 

#include <stdio.h>

double function(double x, double x1, double x2, double y1, double y2)

{

return (-(y1 - y2) * x -(x1 * y2 - x2 * y1)) / (x2 - x1);

}

int main(void)

{

double x1 = 3;

double x2 = 7;

double y1 = 1;

double y2 = 4;

for (int k = x1; k <= x2; k++)

{

double y = function(k, x1, x2, y1, y2);

printf("x = %d \n", k);

printf("y = %f \n", y);

}

return 0;

}

 

 

или подожди, я походу не правильно понял

Какие-то шахматные координаты

 

стоп чел, тебе нужна линия или отрезки? Просто то что ты написал

Kagon сказал(а):↑

(3,1) -> (4,2) -> (5,3) -> (6,4) -> (7,4)

Нажмите, чтобы раскрыть...

это не линия, уравнение из (3 1) и (7 4) это y = (3x - 5) / 4, там нет никаких 4 2 и 5 3

Одни программисты на форуме, может напишем свою доку 3?

x3000 сказал(а):↑

Одни программисты на форуме, может напишем свою доку 3?

Нажмите, чтобы раскрыть...

лучше бы были одни хакеры, я бы например удалил для начала 2ую из этого мира) чтобы высерки потеряли миллиарды

Kagon сказал(а):↑

Когда нужно провести линию из (3, 1) в (7, 4) нужно провести расчеты. Я не понимаю какие, и прошу вас сказать - куда копать?

Нажмите, чтобы раскрыть...

Я не понял, что тебе выше советовали, но предлагаю следующее:

Спойлер:

 

(x1;y1) и (x2;y2) - начальное и конечное положения соответственно. Сверху видно уравнение, задающее прямую, но, поскольку работаешь ты с пикселями, то равно нулю это будет редко (а именно когда линия, задаваемая таким уравнением, проходит от одной вершины пикселя до противоположной)

 

Значит, проверяя пиксели в "парах" (показано фиолетовыми прямоугольничками), высчитывая значение функции в каждом пикселе пары и выбирая тот, значение в котором по модулю ближе к нулю, ты сделаешь линию без дабл пикселей (показана жёлтыми квадратиками)...

 

Не думаю, что это самое эффективное решение, но в матрице 8 на 8 точно будет работать. Можешь сам подумать, как это ещё улучшить

 

P.S. результат проверен в программе для пиксель арта, так что верить можно

Спойлер:

использован инструмент "Линия"

Kagon сказал(а):↑

Не могу даже вопрос загуглить. Но вкратце смогу изложить здесь, прошу сказать куда копать вообще.

 

Задача - провести линию из точки A в точку B.

 

Допустим, имеем матрицу 8х8.

С тем, чтобы нарисовать нечто, идущее исключительно по одной из координат (например, из точки (0, 2) в точку (15, 2)) проблем нет - просто идем по памяти и меняем значение.

Когда нужно провести линию из (3, 1) в (7, 4) нужно провести расчеты. Я не понимаю какие, и прошу вас сказать - куда копать?

 

Но, допустим, результаты расчетов такие:

(3,1) -> (4,2) -> (5,3) -> (6,4) -> (7,4)

Могли бы быть и немного иными, но все равно суть не особо меняется.

 

Нужно как-то высчитать шаги по Y и X, какие именно пиксели должны быть закрашены. Просто скажите куда копать.

Нажмите, чтобы раскрыть...

Когда-то я делал это так: 

procedure ln;

begin

    x := round(x0);

    y := round(y0);

    field[round(y0), round(x0)] := 'A';

    

    

    if ((x < 1000) and (x > 1)) then

    begin

        if x1 >= x0 then

        begin

            if (abs(x1 - x0) >= abs(y1 - y0)) then

                repeat

                    begin

                        x := x + 1;

                        y := round(y0 + (((y1 - y0) / (x1 - x0)) * (round(x - x0))));

                        field[y, x] := '#';

                    end;

                until (x = x1) and (y = y1);

            repeat

                if (abs(x1 - x0) < abs(y1 - y0)) then

                begin

                    if y1 > y0 then

                    

                    begin

                        y := y + 1;

                        x := round(x0 + (((x1 - x0) / (y1 - y0)) * (y - y0)));

                        field[y, x] := '#';

                    end

                        else 

                    begin

                        begin

                            y := y - 1;

                            x := round(x0 + (((x1 - x0) / (y1 - y0)) * (y - y0)));

                            field[y, x] := '#';

                        end;

                        

                    end;

                end;

            until (x = x1) and (y = y1);

        end;

        

        if x1 < x0 then  

        begin

            if (abs(x1 - x0) >= abs(y1 - y0)) then

                repeat

                    begin

                        x := x - 1;

                        y := round(y0 + (((y1 - y0) / (x1 - x0)) * (round(x - x0))));

                        field[y, x] := '#';

                    end;

                until (x = x1) and (y = y1);

            repeat

                if (abs(x1 - x0) < abs(y1 - y0)) then

                begin

                    if y1 > y0 then

                    

                    begin

                        y := y + 1;

                        x := round(x0 + (((x1 - x0) / (y1 - y0)) * (y - y0)));

                        field[y, x] := '#';

                    end

                        else 

                    begin

                        begin

                            y := y - 1;

                            x := round(x0 + (((x1 - x0) / (y1 - y0)) * (y - y0)));

                            field[y, x] := '#';

                        end;

                        

                    end;

                end;

            until (x = x1) and (y = y1);

        end;

    end;

    

    field[round(y1), round(x1)] := 'B';

end;

Алгормтм брезенхема, хотя можно все куда проще. Берешь нормализованый вектор (б - а) и прибавляешь и в цикле итерации которого равны длине вектора, прибавляешь его к изначальной точке умножив i / len. В конечном счете получится линия из а в б без пропусков