На мен самият ми стана съвсем ясно как се чертае линия, - т.е. най-накрая написах работещо за всички случаи предписание - докато си играех на философ преди около година. (Разбира се, става въпрос за решение на целочислен Асемблер, защото делението на отсечката на части с плаваща запетая е твърде "близко до ума".) Този алгоритъм е много съществен в "рисуването" с по-стари сметачета, като Правчото, с който си играех едно време, затова съм си блъскал, плахо и без успех, главата върху този алгоритъм още когато минавах прав под рекламите на поникналите като гъби "Интернет-клубове" и когато на озадачените посетители, учудени от нелепото откритие, че в клуб с надпис "Интернет" няма достъп до Интернет, администраторите отвръщаха: "Прекарай ни телефон и ще има!"...

Философският "двубой", наречен Схващане за всеобщата предопределеност 2, беше между млад "субективен идеалист", "детерминист" и "неопозитивист", смятащ че истината е това, което можеш да пресъздадеш в предписание, и то да работи, и опитен метафизичен идеалист и "свободолюбец".

Не бях съгласен с "метафизичното твърдение", че "разсъдъкът ни не може да схване, изрази и опише дори най-простото движение, да речем преместването на една точка по права линия(...)" и си спомних, че се бях заел с въпросния алгоритъм, на осем-шестак, преди време, но го бях зарязал, щото това, което бях измислил, не работеше за всички случаи - едни линии излизаха както трябва, други - не. (С разни знаци май че се балтаех...)

Впрочем, не мога да се сдържа да не вмъкна какво мисли Дружество "Разум": http://eim.hit.bg/razum/ за "истината", защото тази статия, алгоритъмът от нея, би трябвало да бъде част от "любителското изследване", наречено "Основи на разпознаването на образи", което предстои да бъде издадено.

Истината според мен:

Колкото повече входният къс знание, чиято "истинност" се проверява, съвпада с къс знание от спомените на разума, толкова по-"истинен" и "действителен" е той според разума. Т.е. определянето на "истинност" е определяне на разлика между минало и настояще.

...Спомних си за старата започната, но недовършена работа, и като прегледах отново какво съм бил зарязал, същината на алгоритъма ми се изясни напълно, и разбрах къде бях грешал (но после забравих ;-).

Първо да видим как би могла да се реши задачата:

Последователността от действия се схваща по-лесно, ако си начертаем двумерен масив (решетка), през който прокарваме отсечки и квадратчетата, които те пресичат, запълваме, т.е. си правим "пикселизирано" изображение на отсечка. Изобщо, разглеждането на образите по този начин улеснява изследването на разпознаването на образи.

Какви входни данни имаме и какви изходни трябва да получим, или как бих могъл да оправдая описания под "решението-оправдание" ;-) алгоритъм

Като вход имаме:
- координати на началото и края - (x,y),(x1,y1)
Като изход:
- изображението, което сме начертаали

В него можем да забележим, че:
- отсечката е съставена от съседнии точки (т.е. все намиращи се сред "осморката" около дадена централна точка; за "осморката", съседството и свързаността в "Основи на разпознаването на образи"), следователно някъде ще се използва стъпка единица
- понякога се срещат две и повече съседни точки, които не са диагонални, следователно ще има стъпка, която в общия случай не е единица

Открихме, че едната стъпка на обхождане е единица. Числата, от които се налага да построим зависимост, са 4 - x,y,x1,y1 и зависимостта на стъпката, с която се покачва втората координата, трябва да бъде получена като уравнение от четирите променливи. Можем да забележим, обаче, че като местим отсечката по координатната система (направена, както отбелязахме, като матрица, за да изпъква по-ясно границата между точките), разликите във взаимното разположение между точките в отсечката не се променят. Следователно важно е отношението между началните и крайните координати, а не абсолютната им стойност. Отношението между координатите е разликата между началото и края по двете оси - така опростяваме търсенето, до зависимост между 2 входни стойности.

Спомняме си, че промяната на координатата нявсякъде, включително в частите на отсечката, където има поредица от съседни точки, образуващи хоризонтала, става с единица. Следователно двете променливи определят периода, през който ще се извършва промяна на стойност с единица.

Алгоритъмът трябва да е прост - да използваме само събиране и изваждане. Забелязваме, че колкото е по-голямо отношението между разликите по двете оси, толкова е по-полегата отсечката, т.е. промяната на едната от координатите с единица става по-рядко, следователно периодът е по-голям. Разбира се - трябва да разделим едната разлика на другата. Делението чрез събиране става, като натрупваме делителя в първоначално нулирана променлива и броим колко пъти са нужни да го съберем, за да получим число, равно или по-голямо от делимото. (Разбира се, за чисто изчислителни задачи и големи отношения делимо/делител могат да се използват хитрости, като запомняне на получения сбор след втората стъпка, чрез което пресмятаме резултата направо след осмата, после след шестнайстата и т.н.). Полученото частно е стъпката, през която става промяна на втората координата. След пресмятане на първото частно не трябва да нулираме променливата, защото така ще загубим остатъка. Вместо това изваждаме от натрупания сбор стойността на делимото - остатъкът остава да се помни в променливата, в която натрупваме делителя.

По този начин задачата е решена.

 
Изчертаване на отсечка

1. Взимаме началните координати x,y и крайните x1,y1 в решетката, в която ще преместваме точката.
2. Пресмятаме разликите: dx = x1 - x; dy = y1 - y.
3. Ако (dx >= dy) -> (4) иначе (10)

"По-широка, отколкото висока"

4. (dx >= dy), т.е. ъгълът, който сключват двете точки спрямо "водоравната ос" X на координатната система е между 0 и 45 градуса включително, отсечката е по-"широка", отколкото "висока".
5. Определяме броя на стъпките: (st = dx).
6. Настоящото положение на точката се записва в променливи (tx, ty). На всяка стъпка, tx се увеличава с единица - по оста Х точката се премества с една клетка.
7. В променлива, в началото със стойност нула - да я наречем "n", след всяка стъпка прибавяме dy. Когато "n" стане по-голямо от dx, преместваме точката и по оста y с една стъпка, след което изваждаме от натрупаната в n стойност dx.
8. Дали я преместваме "нагоре" или "надолу" зависи от избора на посоки: ако нарастването на y означава "надолу", то ако (y1 > y), точката ще се "спуска" надолу (++) след всяко преминаване на "n" над dx; ако (y1 < y), точката ще се "издига" нагоре (--); ако пък (y1 == y), точката ще се "плъзга" на едно и също равнище.
9. Повтаряме действията от 4 до 8, докато tx се изравни с x1.

"По-висока, отколкото широка"

10. (dx < dy), т.е. ъгълът спрямо водоравната ос е между 45 и 90 градуса. Тогава стъпките (st = dy). Използваме същата последователност, с промените:
- преместваме с една клетка на всяяка стъпка по Y (ty++), вместо X (tx)
- в n се прибавя dx (вместо dy), ккоято щом надмине dy (вместо dx) кара точката да се измести и по оста X и предизвиква изваждане на dy от n.

...

Горд от откритието си ;-), реших да потърся какво пише из Мрежата за чертаенето на отсечка. Намерих нещо само на едно място (но не помня дали мързелът се върна твърде бързо или Интернет излезе "празен" откъм такава информация), което цитирам.

  http://www.rulabinsy.com/cavd/text/chap09-2.html
"The solution to drawing lines without complex arithmetic is to use scaled-integer values for the determination of pixel increments. The most popular technique also does all initial calculations in terms of these scaled integers [Breshenham 65]. The algorithm makes use of an indicator that initially has the value D = 2dy - dx (where dy = y2 - y1 and dx = x2 - x1), and a current point (x, y), which initially is (x1, y1). After plotting this point, x is incremented by 1, and y increments by 1 only if D > 0. If y increments, then D has the value 2(dy - dx) added to it; otherwise, it has the value 2y added to it. This continues until (x, y) reaches (x2, y2).

The Breshenham algorithm is very fast because the terms can be precomputed and all of them require only addition and subtraction. The version described is, of course, for lines with a slope of less than one because x increments smoothly. For other lines, the coordinate terms are simply reversed."

program lina_lina;

var vsega:word;  {сегмент на графичната страница}
    i,j,k:word;

procedure init;assembler;
asm
  mov vsega, $A000      {адрес на графичната страница}
  mov   ax, $13
  int   10H
  mov   ah, $0F
  int   10H
end;

(*-----------------------------------------------*)
(*------------Alexei Frunze----------------------*)

Procedure PutPixel(X, Y : Word; C : Byte); Assembler;
Asm
  Mov   AX, VSegA
  Mov   ES, AX
  Mov   DI, X
  Mov   BX, Y
  ShL   BX, 6
  Add   DI, BX
  ShL   BX, 2
  Add   DI, BX
  Mov   AL, C
  mov es:[di],al {променено от Тош; в оригинала на
		     {Алексей е "STOSB"}
End;

Function Sgn (I : Integer) : Integer; Assembler; 
Asm
  Mov   AX, I
  Or    AX, AX
  JZ    @end
  ShL   AX, 1
  JC    @1
  Mov   AX, 1
  Jmp   @end
@1:
  Mov   AX, -1
@end:
End;

Function _Abs (I : Integer) : Integer; Assembler;
Asm
  Mov   AX, I
  Test  AX, 8000h
  JZ    @end
  Neg   AX
@end:
End;

Procedure Line (X1, Y1, X2, Y2 : Word; C : Byte);
{от "grafix" на Alexei Frunze, http://alex.chat.ru }
Var
  SX, SY, M, N,
  DX1, DY1, DX2, DY2 : Integer;
Begin
  SX := X2-X1;
  SY := Y2-Y1;
  DX1 := Sgn (SX);
  DY1 := Sgn (SY);
  M := _Abs (SX);
  N := _Abs (SY);
  DX2 := DX1;
  DY2 := 0;
  If M < N then
    Begin
      M := _Abs (SY);
      N := _Abs (SX);
      DX2 := 0;
      DY2 := DY1
    End;
  Asm
    Mov   AX, VSegA
    Mov   ES, AX
    Mov   DI, X1
    Mov   BX, Y1
    ShL   BX, 6
    Add   DI, BX
    ShL   BX, 2
    Add   DI, BX                              

    Mov   AX, DY1
    Test  AX, 8000h
    JZ    @lb0
    Neg   AX
    ShL   AX, 6
    Mov   BX, AX
    ShL   AX, 2
    Add   BX, AX
    Neg   BX
    Jmp   @lb1
@lb0:
    ShL   AX, 6
    Mov   BX, AX
    ShL   AX, 2
    Add   BX, AX
@lb1:
    Add   BX, DX1

    Mov   AX, DY2
    Test  AX, 8000h
    JZ    @lb2
    Neg   AX
    ShL   AX, 6
    Mov   DX, AX
    ShL   AX, 2
    Add   DX, AX
    Neg   DX
    Jmp   @lb3
@lb2:
    ShL   AX, 6
    Mov   DX, AX
    ShL   AX, 2
    Add   DX, AX
@lb3:
    Add   DX, DX2

    Mov   AL, C
    Xor   SI, SI
    Mov   CX, M
    Inc   CX
@cycle:
    Mov   ES:[DI],AL { AX - razmazvane }
    Add   SI, N
    Cmp   SI, M
    JC    @cl1
    Sub   SI, M
    Add   DI, BX                                
    Loop  @cycle
    Jmp   @end
@cl1:
    Add   DI, DX                                
    Loop  @cycle
@end:
  End
End;

(*-----====================================================------*)
(*  Тодор Арнаудов (TodProg, Tosh)                               *)

procedure li(x,y,x1,y1:word;c:byte);   {скелет на високо ниво}
var ym,xm:word;
    dx,dy:integer;
    dxa,dya:word;      {абсолюттни}
    dxaa,dyaa:word;
    a,b  :word; {текущи координати}
    q:boolean;
    sx,sy:shortint;
 begin

dx:=x1-x;       {x1>x !}
dy:=y1-y;       {y1>y !}

if (dx>=0) then sx:=1 else sx:=-1;
if (dy>=0) then sy:=1 else sy:=-1;

a:=x;
b:=y;

dxa:=abs(dx);
dya:=abs(dy);
dxaa:=dxa;
dyaa:=dya;

if dxa >= dya then
   begin
ym:=0;
 putpixel(a,b,c);

 while (dxaa>0) do
       begin
            a:=a+sx;
            ym:=ym+dya;
            if (ym > dxa) then begin
                                   b:=b+sy;
                                   ym:=ym-dxa;
                              end;
           putpixel(a,b,c);
           dec(dxaa);
      end;
   end

else
 begin
  xm:=0;
  putpixel(a,b,c);
 while (dyaa>0) do
       begin
            b:=b+sy;
            xm:=xm+dxa;
            if (xm > dya) then begin
                                   a:=a+sx;
                                   xm:=xm-dya;
                              end;
           putpixel(a,b,c);
           dec(dyaa);
      end;
   end;
 end;

{lina - 8.9.2002, използва знаци}
procedure lina(x,y,x1,y1:word;c:byte);
(*
- Изисква само сегмента на графичнната страница
- Ицяло на Асемблер
- Около 75 казби
*)
var dex,dey:integer;
    dexx,deyy:word;
    xm, ym:word;
    a,b  :word;
    buf  :word;
    sx,sy:integer; {1,-1 , 320,-320}
 begin
asm
   mov ax,x1
   cmp ax,x
   jb  @sxminus
   mov sx,1
   jmp @sxsled
@sxminus:
   mov sx,-1
@sxsled:
   mov bx,y1
   cmp bx,y
   jb  @syminus
   mov sy,320
   jmp @sysled
@syminus:
   mov sy,-320    {sx,sy - стъпки на преместването}
@sysled:
   mov dx,vsega   {точки}
   mov es,dx
   sub ax,x
   cmp ax,$F000   {ако разликата DX<0, обърни абс. стойн.}
   jb @sledsrav
   not ax         {-100 = +100}
   inc ax
@sledsrav:
   mov dex,ax
   mov dexx,ax
@smetdey:
   sub bx,y
   cmp bx,$F000
   jb @sledsravdey
   not bx
   inc bx
@sledsravdey:
   mov dey,bx
   mov deyy,bx                  {dexx,deyy - abs}
{===============================================}

@sravnixy:
  cmp ax,bx
  ja  @linx     {dex > dey}
  jmp @liny     {dey = < dex}

@linx:
  mov ax,x      {проверка за край на линията}
  mov dx,y      {Първа точка}
  mov di,ax
  shl dx,6
  add di,dx
  shl dx,2
  add di,dx
  mov dl,c

  xor bx,bx      {ym = 0 - проверка за увеличение на y}
  mov ax,dex
{==================================}
@sledplus:
  mov es:[di], dl       {точка}
@sledpix:
  dec ax                {брояч ax}
  cmp ax,0
  je @kra
  add di,sx             {Увеличава X}
  add bx,dey
  cmp bx,dex
  jnb @plusy
  jmp @sledplus
@plusy:
  add di,sy
  sub bx,dex
  jmp @sledplus

@liny:
  mov ax,x     
  mov dx,y      {Първа точка}
  mov di,ax
  shl dx,6
  add di,dx
  shl dx,2
  add di,dx
  mov dl,c

  xor bx,bx      {ym(bx) = 0 - проверка за покачване на y}
  mov ax,dey
{==================================}
@sledplusy:
  mov es:[di], dl       {точка}
@sledpixy:
  dec ax                {брояч dec/jz е по-бавно?}
  cmp ax,0
  je @kra
  add di,sy                {Увеличава X}
  add bx,dex
  cmp bx,dey
  jnb @plusx
  jmp @sledplusy
@plusx:
  add di,sx
  sub bx,dey
  jmp @sledplusy
@kra:
     end;
end;

begin
 init;
(*
Тук се вписват цикли, с които се изследва
бързината на различните процедури.
*)
end.

------------lina_sam.pas-----------------