ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Boris Sivko                          2:452/26.14    08 Sep 2001  12:19:52
 To : Andrew Plyako
 Subject : заливка
 -------------------------------------------------------------------------------- 
 

 
  По данным контрразведки я узнал, что в Четверг Сентябрь 06 2001 20:27, Andrew
 Plyako писал Alexey Asemov:
 
  >>>  JK> Я yже как-то кидал сюда пpимеp заливки по линиям. Итак: Для
  >>>  JK> данной точки (x, y) опpеделяется и заполняется наибольший
  >>>  JK> гоpизонтальный отpезок (xR, xL), содеpжащий этy точкy и
  >>>  JK> лежащий внyтpи заливаемой области. После этого в поисках еще
  >>>  JK> незаполненных пикселей пpовеpяются отpезки, лежащие над и под
  >>>  JK> данным. Для них pекypсивно вызывается данная фyнкция.
  >>>   Для областей с большими пустотами будет просто летать. А вот для
  >>> лабиринтов с проходами в 1 пиксель вряд ли.
 
   Вот только протестил для лабиринтов и для пустот. В пустотах по линиям
 работает ~ 2-2.5 раза быстрее, требует раз в 50-100 меньше памяти. В лабиринтах 
 по линиям скорость ~ в 1.2 раза меньше, памяти нада ~ 2.5-3.5 раза больше.
   ИМХО по линиям в большинстве случаев эффективнее. Hо случаи разные бывают...
 
  AP> Можно по подробней описать алгоритм? Ибо то, как я его понимаю, он
  AP> работает только для выпуклых фигур. Ибо вот такую фигуру:
 
  AP>   ***
  AP> ******
  AP> **  **
  AP> *   **
  AP>    ***
  AP>   *X**
  AP> Если мы стартуем закраску из X, то закрасится лишь такая область
  AP> (закраска помечена X, * - то что не закрасилось):
 
  AP>   XXX
  AP> XXXXXX
  AP> **  XX
  AP> *   XX
  AP>    XXX
  AP>   XXXX
  AP> Ы? Или я не прав? Тогда можно по-подробнее? Или, в крайнем случае,
  AP> конкретную реализацию...
 
   ИМХО Ярослав имел ввиду ~ такую реализацию:
 
 ДДД Тут начинается филя PAINT3.PAS ДДД
 {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
 {$M 16383,0,655360}
 Program main;
 Uses graph;
 Const maxx=639;
       maxy=449;
       mem = 10;
 Var
   a1,a2:integer;
  maxuse:integer;
 
 Var a,b,y:array[0..mem] of integer;
 p,i,n,s:integer;
       r:longint;
 
 Function dec_n:integer;
 Begin
   if n=0 then dec_n:=mem else dec_n:=n-1;
 End;
 
 Procedure output;
 Var ss:string;
 Begin
   setfillstyle(1,black);
   bar(10,452,120,470);
   str(maxuse,ss);
   setcolor(white);
   ss:='Max Use:'+ss;
   outtextxy(10,452,ss);
 End;
 
 Procedure process(xx,yy:integer);
 Var a,b:integer;
 Begin
   a:=xx;
   b:=xx;
   while getpixel(a-1,yy)=0 do dec(a);
   while getpixel(b+1,yy)=0 do inc(b);
   main.a[n]:=a;
   main.b[n]:=b;
   main.y[n]:=yy;
   setcolor(blue);
   line(a,yy,b,yy);
   inc(n);
 
   if n>mem then n:=0;
 
   if s=n then
   begin
     setfillstyle(1,black);
     bar(10,452,120,470);
     setcolor(red);
     outtextxy(10,452,'Overflow!');
     readln;
     halt;
   end;
 End;
 
 Procedure paint(xx,yy:integer);
 Begin
   s:=0;
   n:=0;
   r:=0;
   maxuse:=1;
   y[0]:=yy;
   process(xx,yy);
   repeat
     p:=a[s];
     repeat
       if getpixel(p,y[s]-1)=0 then
       begin
         process(p,y[s]-1);
         p:=b[dec_n];
       end;
       inc(p);
     until p>b[s];
     p:=a[s];
     repeat
       if getpixel(p,y[s]+1)=0 then
       begin
         process(p,y[s]+1);
         p:=b[dec_n];
       end;
       inc(p);
     until p>b[s];
 
     if (n-s+mem) mod mem > maxuse then maxuse:=(n-s+mem) mod mem;
     if r and 127 = 0 then output;
     inc(s);
     inc(r);
     if s>mem then s:=0;
   until s=n;
   output;
 End;
 
 BEGIN
   a1:=0;
   a2:=0;
   randomize;
   initgraph(a1,a2,'c:\bp\bgi\');
   cleardevice;
   setcolor(White);
   line(0,0,0,maxy);
   line(0,0,maxx,0);
   line(maxx,0,maxx,maxy);
   line(0,maxy,maxx,maxy);
 
   for i:=1 to 5 do line(random(maxx),random(maxy),random(maxx),random(maxy));
 
   paint(maxx div 2,maxy div 2);
 
   readln;
   closegraph;
 END. ДДД А здесь филя PAINT3.PAS кончается ДДД
 
      Счастливо, Andrew. Вспоминай обо мне...
 ... I'll be back...
  * Origin: Я такой же осёл, как и Вы, сэр! (2:452/26.14)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: заливка   Alexey Asemov   05 Sep 2001 10:54:13   заливка   Andrew Plyako   06 Sep 2001 20:27:50   заливка   Boris Sivko   08 Sep 2001 11:56:23   заливка   Boris Sivko   08 Sep 2001 12:19:52