Recent

Author Topic: Vector graphics floodfill algorithms  (Read 1647 times)

zamtmn

  • Sr. Member
  • ****
  • Posts: 486
Vector graphics floodfill algorithms
« on: May 21, 2022, 12:49:38 pm »
Hi All!
Are there algorithms for vector filling of the area? I have several contours of a non-convex area (possibly with holes) and a vector description of the pattern to fill (a set of lines) Or maybe there are ready-made libraries with open source implementing this?

Roland57

  • Sr. Member
  • ****
  • Posts: 265
Re: Vector graphics floodfill algorithms
« Reply #1 on: May 21, 2022, 02:41:47 pm »
Hi. Not sure that it be what you look for, but there is Clipper.

https://github.com/AngusJohnson/Clipper2


zamtmn

  • Sr. Member
  • ****
  • Posts: 486
Re: Vector graphics floodfill algorithms
« Reply #2 on: May 21, 2022, 05:12:36 pm »
Thanks, but this is not exactly what I need, this finding offset contours.
Hi. Not sure that it be what you look for, but there is Clipper.

https://github.com/AngusJohnson/Clipper2

VTwin

  • Hero Member
  • *****
  • Posts: 1097
  • Former Turbo Pascal 3 user
Re: Vector graphics floodfill algorithms
« Reply #3 on: May 21, 2022, 06:11:25 pm »
« Last Edit: May 21, 2022, 06:14:16 pm by VTwin »
“Talk is cheap. Show me the code.” -Linus Torvalds

Free Pascal Compiler 3.2.2
macOS 10.13.6: Lazarus 2.2.0 (64 bit Cocoa)
macOS 12.0.1: Lazarus 2.2.0 (64 bit Cocoa M1)
Ubuntu 18.04.3: Lazarus 2.2.0 (64 bit on VBox)
Windows 7 Pro SP1: Lazarus 2.2.0 (64 bit on VBox)

zamtmn

  • Sr. Member
  • ****
  • Posts: 486
Re: Vector graphics floodfill algorithms
« Reply #4 on: May 21, 2022, 06:40:27 pm »
I have the contours of the area, by making a triangulation I have a set of triangles that make up the area. There are no problems with this. next, for example, I want to shade the area with oblique lines in increments of 10, starting from the point 0,0. I need to find out the coordinates of all the dinias falling inside the area.

Seenkao

  • Sr. Member
  • ****
  • Posts: 407
    • New ZenGL.
Re: Vector graphics floodfill algorithms
« Reply #5 on: May 21, 2022, 09:39:11 pm »
Привет.
Одним из самых действенных средств будет обычный перебор. Описано в этой игре.
Вероятнее всего, можно немного ускорить процедуру, записывая все пиксели отдельно, а потом просто полученные пиксели сразу залить определённым цветом. Сложность в том, что если надо заливать каким-то узором, надо дублировать изображение и все пиксели отмечать на втором изображении (для сплошной заливки не обязательно дублировать изображение, можно просто координаты всех пикселей взять) и в соответствии с отмеченными пикселями заполнять узором то, что было отмечено.

Точнее в любом случае, если ты хочешь узором заливать, то надо знать координаты всех точек, которые ты хочешь залить и сличить их с координатами полностью залитой картинки (или какой-то области).

Можешь заглянуть ещё в LazPaint, как там это реализовывалось.

----------------------------------------------
Google translate:
Hello.
One of the most effective means will be the usual enumeration. Described in this game.
Most likely, you can speed up the procedure a little by writing all the pixels separately, and then simply fill the resulting pixels with a certain color. The difficulty is that if you need to fill with some kind of pattern, you need to duplicate the image and mark all the pixels on the second image (for a solid fill, you don’t have to duplicate the image, you can just take the coordinates of all the pixels) and, in accordance with the marked pixels, fill with a pattern that was noted.

More precisely, in any case, if you want to fill with a pattern, then you need to know the coordinates of all the points that you want to fill and compare them with the coordinates of a completely filled image (or some area).

You can also look at LazPaint, how it was implemented there.
Rus: Стремлюсь к созданию минимальных и достаточно быстрых приложений.
Работаю над ZenGL.
Eng: I strive to create applications that are minimal and reasonably fast.
Working on ZenGL. :)

circular

  • Hero Member
  • *****
  • Posts: 3828
    • Personal webpage
Re: Vector graphics floodfill algorithms
« Reply #6 on: May 21, 2022, 11:31:14 pm »
What you’re looking for is a polygon filling.

You can do that for example with BGRABitmap by defining an array of TPointF with EmptyPointF to separate the main part and each hole.

This can be filled using FillPolyAntialias or PolygonAntialias.

You need to prepare a bitmap containing the pattern and supply it as fill parameter instead of a single color.

You can look at CreateBrushTexture function for example.
Conscience is the debugger of the mind

BobDog

  • Sr. Member
  • ****
  • Posts: 265
Re: Vector graphics floodfill algorithms
« Reply #7 on: May 22, 2022, 12:44:27 am »

Flood fill with scan lines.
Windows.
Code: Pascal  [Select][+][-]
  1.  
  2. uses
  3. windows;
  4. {$RANGECHECKS ON}
  5. type pt =object
  6. x,y:single;
  7. end;
  8.  
  9. type
  10.   Arr2D = array of array of single;
  11.   Arrpt=array of pt;
  12.  
  13. Const xres=1024;
  14. Const yres=768;
  15. const
  16.     DC_BRUSH=18;
  17.     DC_PEN=19;
  18.    
  19.  
  20. procedure setfontsize(h:hdc;size:integer;style:pchar);
  21. begin
  22.       SelectObject(h,CreateFont(size,0,0,0,400,0,0,0,DEFAULT_CHARSET,OUT_OUTLINE_PRECIS,CLIP_DEFAULT_PRECIS,ANTIALIASED_QUALITY,VARIABLE_PITCH,style));
  23. End;
  24.  
  25. procedure setfontcolours(h:hdc;text:longword;background:longword);
  26. begin
  27.       SetTextColor(h,text) ;
  28.       SetBkColor(h,background);
  29. End;
  30.  
  31. procedure text(h:hdc;x:integer;y:integer;s:pchar);
  32.       Var l:integer;
  33.       begin
  34.       l:=Length(s);
  35.       textouta(h,x,y,s,L);
  36. End;
  37.  
  38. procedure ClearScreen(h:hdc;colour:longint);
  39.       begin
  40.       SetDCBrushColor(h,colour);
  41.       SetDCPenColor(h,colour);
  42.       rectangle(h,0,0,xres,yres);
  43. End;
  44.  
  45. procedure hidecursor();
  46. var
  47.     consoleHandle:handle;
  48.      info:CONSOLE_CURSOR_INFO;
  49.      begin
  50.      consolehandle := GetStdHandle(STD_OUTPUT_HANDLE);
  51.      info.dwSize := 100;
  52.      info.bVisible := FALSE;
  53.      SetConsoleCursorInfo(consoleHandle, @info);
  54.      End;
  55.      
  56.      
  57. procedure switch(var a:single;var b: single);
  58. var temp: single;
  59. begin
  60.   temp := a; a := b; b := temp;
  61. end;
  62.  
  63.  
  64. procedure fill(h:hdc;p:Arrpt;c:longword); // hdc only for winapi
  65. var
  66. sy:single=1000000;
  67. by:single=-1000000;
  68. dx,dy:single;
  69. a:Arr2D=nil;
  70. i,j,y,k:int32;
  71. S:array of single=nil;
  72. xi:array of single=nil;
  73. begin
  74.  
  75. // colours//
  76. SetDCPenColor(h,c);
  77. //end colours//
  78.  
  79. SetLength(a, length(p)+1, 2);
  80.  
  81.     For i :=0 To high(p) do
  82.     begin
  83.         a[i,0]:=p[i].x;
  84.         a[i,1]:=p[i].y;
  85.         If (Sy>p[i].y) Then Sy:=p[i].y;
  86.         If (By<p[i].y) Then By:=p[i].y;
  87.     end;
  88.    
  89.     setlength(xi,length(a)+1);
  90.     setlength(S,length(a)+1);
  91.    
  92.     a[high(a),0] := a[0,0];
  93.     a[high(a),1] := a[0,1];
  94.    
  95.     For i:=0 To high(a)-1 do
  96.     begin
  97.         dy:=a[i+1,1]-a[i,1];
  98.         dx:=a[i+1,0]-a[i,0];
  99.         If (dy=0.0) Then S[i]:=1.0;
  100.         If (dx=0.0) Then S[i]:=0.0;
  101.         If (dy<>0) And (dx<>0) Then S[i]:=dx/dy;
  102.     end;
  103.    
  104.    
  105.     For y:=trunc(Sy-1) To trunc(By+1) do
  106.  begin
  107.         k:=0;
  108.         For i:=0 To high(a)-1 do
  109.        begin
  110.             If ((a[i,1]<=y) And (a[i+1,1]>y))  Or (a[i,1]>y) And (a[i+1,1]<=y) Then
  111.             begin
  112.             xi[k]:=(a[i,0]+S[i]*(y-a[i,1]));
  113.             k:=k+1;
  114.             End;
  115.         end;
  116.     For j:=0 To k-2 do
  117.     begin
  118.         For i:=0 To k-2 do
  119.         begin
  120.             If xi[i]>xi[i+1] Then Switch (xi[i],xi[i+1]);
  121.         end;
  122.     end;
  123.    
  124.    
  125.     i:=0;
  126.     while (i< k-1) do
  127.     begin
  128.     // graphics//
  129.     MoveToEx(h,trunc(xi[i]),y,nil);
  130.      LineTo(h, trunc(xi[i+1]+1),y);
  131.       //end graphics//
  132.      i:=i+2
  133.      end;
  134.    
  135.  end;
  136. End;
  137.  
  138. function createpolygon(p:pt;num:int32):Arrpt;
  139. const pi=3.141592653589793;
  140. var
  141. z,step:single;
  142. t:arrpt=nil;
  143. temp:pt;
  144. counter:int32=0;
  145. begin
  146. step:=2*pi/num;
  147. z:=0;
  148. while (z<=2*pi) do
  149. begin
  150. counter:=counter+1;
  151. temp.x:=p.x+(50+random(300))*cos(z);
  152. temp.y:=p.y+(50+random(300))*sin(z);
  153. setlength(t,counter);
  154. t[counter-1].x:=temp.x;
  155. t[counter-1].y:=temp.y;
  156. z:=z+step;
  157. end;
  158. exit(t);
  159. end;
  160.  
  161. var
  162.  Memhdc,WorkingScreen:hdc;
  163. p:hwnd;
  164.  Membitmap:HBITMAP;
  165.  sysmenu:qword;
  166.  pts:arrpt;
  167. centre:pt;
  168. colour:longint;
  169. numsides:int32;
  170. s:ansistring;
  171.  
  172. begin
  173.  p:=getconsolewindow();
  174. setwindowpos(p, HWND_TOPMOST, 100, 100, xres, yres,SWP_SHOWWINDOW);
  175. WorkingScreen:=GetDC(p);
  176. Memhdc := CreateCompatibleDC(WorkingScreen);
  177. Membitmap := CreateCompatibleBitmap(WorkingScreen, xres, yres);
  178.  
  179. SelectObject(Memhdc, Membitmap);
  180. SelectObject(Memhdc,GetStockObject(DC_BRUSH));
  181. SelectObject(Memhdc,GetStockObject(DC_PEN));
  182. setfontsize(Memhdc,35,'comic sans ms');
  183. setfontcolours(Memhdc,rgb(200,100,0),0);
  184. //'some console instructions
  185. sysMenu := GetSystemMenu(p, False);
  186. DeleteMenu(sysMenu, SC_CLOSE, MF_BYCOMMAND) ;   // 'cannot close console
  187. DeleteMenu(sysMenu, SC_MINIMIZE, MF_BYCOMMAND); //'To prevent user from minimizing console window
  188. DeleteMenu(sysMenu, SC_MAXIMIZE, MF_BYCOMMAND); //'To prevent user from maximizing console window
  189. DeleteMenu(sysMenu, SC_SIZE, MF_BYCOMMAND);     //'non resizable console
  190. hidecursor();
  191. ShowScrollBar(p, SB_BOTH, FALSE);
  192. SetBkMode (Memhdc, TRANSPARENT);
  193. centre.x:=xres/2;
  194. centre.y:=yres/2;
  195. While true do
  196.  
  197.     begin
  198.     numsides:=(4+random(8));
  199.     pts:=createpolygon(centre,numsides);
  200.     colour:=rgb(random(255),random(255),random(255));
  201.       clearscreen(Memhdc,rgb(55,255,255));
  202.       text(Memhdc,10,35,'This is drawn on the console.');
  203.       text(Memhdc,10,60,'Press escape to finish.');
  204.       str(numsides,s);
  205.       text(Memhdc,10,700,'Number of sides ');
  206.       text(Memhdc,230,700,pchar(s));
  207.       fill(Memhdc,pts,colour);
  208.       BitBlt(WorkingScreen, 0, 0, xres, yres,Memhdc, 0, 0,SRCCOPY);
  209.       If (GetAsyncKeyState($1B)<>0) Then //' escape key
  210.            begin
  211.             DeleteObject(Membitmap);
  212.             DeleteDC    (Memhdc);
  213.             GetSystemMenu(p,true);
  214.            Exit;
  215.            end;
  216.             sleep(500);
  217. end;
  218. end.
  219.  
  220.  
  221.  
  222.  

zamtmn

  • Sr. Member
  • ****
  • Posts: 486
Re: Vector graphics floodfill algorithms
« Reply #8 on: May 22, 2022, 06:09:58 am »
Thanks. But without pixels, without DC and other graphics.
Only mathematics

circular

  • Hero Member
  • *****
  • Posts: 3828
    • Personal webpage
Re: Vector graphics floodfill algorithms
« Reply #9 on: May 22, 2022, 07:29:39 am »
Ah ok.

The algorithm I have been using is the following: going through horizontal lines and compute intersections with the segments of the polygon and from there determine the beginning and end of the area to fill for each Y coordinate.

If you want lines that are oblique, for the patterns, you could use a similar algorithm, but by applying first a rotation of the the polygon, then compute the lines, then rotate back the lines.

You can look at the code in BGRAFillInfo unit of BGRABitmap to see how it is done and make your own algorithm, or use the class TSimpleFillPolyInfo or TOnePassFillPolyInfo in it:

- create a TPointF array with your area to fill (EmptyPointF to separate parts)
- create instance of TSimpleFillPolyInfo with the TPointF coordinates of your area to fill
- initialize an array of intersections with CreateIntersectionArray
- with GetBounds determine all the possible Y
- call ComputeAndSort for each Y coordinate. With the nbInter value, you know how many lines there are. For example if you have [0, 100, 150, 250, ...] and nbInter 4, then there are two lines : from 0 to 100 and from 150 to 250
- free intersection array with FreeIntersectionArray
Conscience is the debugger of the mind

Seenkao

  • Sr. Member
  • ****
  • Posts: 407
    • New ZenGL.
Re: Vector graphics floodfill algorithms
« Reply #10 on: May 22, 2022, 12:03:31 pm »
Thanks. But without pixels, without DC and other graphics.
Only mathematics
В любом из вариантов будет использоваться математика. )))
Проблемы поползут сразу со всех сторон, если ты будешь делать это пытаясь вычислить области и залить их. Первое, если это будет происходить отдельно, то надо будет состыковывать узор между собой. Второе, если заливаемое пространство будет очень сложным, то на вычисления этого пространства уйдёт очень много времени. Третье, заливка области математическим путём... это очень трудоёмкое занятие, как в плане вычислений, так и в плане работы.
Если заливку просто сличать с областью выделения, будет намного проще и быстрее.

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

Выбор всегда за тобой!
Будешь заливать пространство, делай отдельное изображение для найденного пространства. Это даст тебе возможность смещать узор, не пересчитывая всё заново.

Google translate:
Either option will use math. )))
Problems will creep in from all directions at once if you do this by trying to figure out areas and fill them. First, if this happens separately, then it will be necessary to dock the pattern with each other. Second, if the space being filled is very complex, then it will take a very long time to calculate this space. Third, filling an area mathematically... is a very time-consuming task, both in terms of calculations and in terms of work.
If the fill is simply compared to the selection area, it will be much easier and faster.

Therefore, working with each pixel will give you the opportunity to fully select any space. The only problem is that if the space is huge, then the complexity of the calculation will be long (but this is in any case).

The choice is always yours!
When you fill in the space, make a separate image for the found space. This will give you the opportunity to shift the pattern without recalculating everything again.
Rus: Стремлюсь к созданию минимальных и достаточно быстрых приложений.
Работаю над ZenGL.
Eng: I strive to create applications that are minimal and reasonably fast.
Working on ZenGL. :)

circular

  • Hero Member
  • *****
  • Posts: 3828
    • Personal webpage
Re: Vector graphics floodfill algorithms
« Reply #11 on: May 22, 2022, 02:25:25 pm »
@Seenkao: it is not necessarily so complicated, as I explained above. It is possible to determine where the lines are by comping scanlines. Here those are simply rotated 45 degrees.
Conscience is the debugger of the mind

BobDog

  • Sr. Member
  • ****
  • Posts: 265
Re: Vector graphics floodfill algorithms
« Reply #12 on: May 22, 2022, 02:54:50 pm »
I only use GDI to draw the polygon and lines.
I have marked the non GDI procedures.
steps
create a polygon
rotate it by 45 degrees
get scan lines in the rotated polygon.
rotate the scan lines back 45 degrees to fit into the original polygon.

draw the original polygon and the new scan lines (via GDI) to see what is going on.
I have set a gap of 10 for this demo viz:
 lines:=GetLines(newpoints,10);
Coded and tested in Geany ide.
Code: Pascal  [Select][+][-]
  1.  
  2.  
  3. uses
  4. windows;
  5. {$RANGECHECKS ON}
  6. type pt =object
  7. x,y:single;
  8. end;
  9.  
  10. type line=object
  11. start,finish:pt
  12. end;
  13.  
  14. type
  15.   Arrpt=array of pt;
  16.   arrline=array of line;
  17.  
  18.    
  19.   function rotate(pivot:pt;p:pt;a:single):pt; // not gdi
  20.   var
  21.   t:pt;
  22.   begin
  23.    t.x:=(Cos(a*0.0174533)*(p.x-pivot.x)-Sin(a*0.0174533)*(p.y-pivot.y)) +pivot.x;
  24.    t.y:=(Sin(a*0.0174533)*(p.x-pivot.x)+Cos(a*0.0174533)*(p.y-pivot.y)) +pivot.y;
  25.    exit(t);
  26.   end;
  27.  
  28.   function centroid(p:arrpt):pt; // not gdi
  29.   var i:int32;
  30.   var ans:pt;
  31.   begin
  32.   ans.x:=0;
  33.   ans.y:=0;
  34.   for i:=0 to high(p) do
  35.   begin
  36.   ans.x:=ans.x+p[i].x;
  37.   ans.y:=ans.y+p[i].y;
  38.   end;
  39.   ans.x:=ans.x/length(p);
  40.   ans.y:=ans.y/length(p);
  41.   exit(ans);
  42.   end;
  43.  
  44.   function rotatepolygon(p:arrpt;angle:single):arrpt; // not gdi
  45.   var c:pt;
  46.   var i:int32;
  47.   var ans:arrpt=nil;
  48.   begin
  49.   setlength(ans,length(p));
  50.   c:=centroid(p);
  51.   for i:=0 to high(p) do ans[i]:=rotate(c,p[i],angle);
  52.   exit(ans);
  53.   end;
  54.  
  55.   function rotatelines(pivot:pt;L:arrline;angle:single):arrline; // not gdi
  56.   var
  57.   i:int32;
  58.   begin
  59.   for i:=0 to high(L) do
  60.   begin
  61.   L[i].start:=rotate(pivot,L[i].start,angle);
  62.    L[i].finish:=rotate(pivot,L[i].finish,angle);
  63.   end;
  64.   exit(L);
  65.   end;
  66.  
  67.   procedure switch(var a:single;var b: single); // not gdi used in getlines
  68.   var temp: single;
  69.   begin
  70.   temp := a; a := b; b := temp;
  71.   end;
  72.  
  73.   function GetLines(p:Arrpt;gap:int32):arrline; // not gdi
  74. type
  75.  Arr2D = array of array of single;
  76.  var
  77.  sy:single=1e6;
  78.  by:single=-1e6;
  79.  dx,dy:single;
  80.  a:Arr2D=nil;
  81.  i,j,y,k,count:int32;
  82.  S:array of single=nil;
  83.  xi:array of single=nil;
  84.  ans:arrline=nil;
  85. begin
  86. count:=-1;
  87.  
  88. SetLength(a, length(p)+1, 2);
  89.  
  90.     For i :=0 To high(p) do
  91.     begin
  92.         a[i,0]:=p[i].x;
  93.         a[i,1]:=p[i].y;
  94.         If (Sy>p[i].y) Then Sy:=p[i].y;
  95.         If (By<p[i].y) Then By:=p[i].y;
  96.     end;
  97.    
  98.     setlength(xi,length(a)+1);
  99.     setlength(S,length(a)+1);
  100.    
  101.     a[high(a),0] := a[0,0];
  102.     a[high(a),1] := a[0,1];
  103.    
  104.     For i:=0 To high(a)-1 do
  105.     begin
  106.         dy:=a[i+1,1]-a[i,1];
  107.         dx:=a[i+1,0]-a[i,0];
  108.         If (dy=0.0) Then S[i]:=1.0;
  109.         If (dx=0.0) Then S[i]:=0.0;
  110.         If (dy<>0) And (dx<>0) Then S[i]:=dx/dy;
  111.     end;
  112.    
  113.    
  114.     For y:=trunc(Sy-1) To trunc(By+1) do
  115.  begin
  116.         k:=0;
  117.         For i:=0 To high(a)-1 do
  118.        begin
  119.             If ((a[i,1]<=y) And (a[i+1,1]>y))  Or (a[i,1]>y) And (a[i+1,1]<=y) Then
  120.             begin
  121.             xi[k]:=(a[i,0]+S[i]*(y-a[i,1]));
  122.             k:=k+1;
  123.             End;
  124.         end;
  125.     For j:=0 To k-2 do
  126.     begin
  127.         For i:=0 To k-2 do
  128.         begin
  129.             If xi[i]>xi[i+1] Then Switch (xi[i],xi[i+1]);
  130.         end;
  131.     end;
  132.    
  133.    
  134.     i:=0;
  135.     while (i< k-1) do
  136.     begin
  137.     if (y mod gap=0) then
  138.     begin
  139.     count:=count+1;
  140.     setlength(ans,count+1);
  141.     ans[count].start.x:=xi[i];
  142.     ans[count].start.y:=y;
  143.     ans[count].finish.x:=xi[i+1]+1;
  144.     ans[count].finish.y:=y;
  145.      end;
  146.      i:=i+2
  147.      end;
  148.  end;
  149.  exit(ans);
  150. End;
  151.  
  152.    function createpolygon(p:pt;num:int32):Arrpt; // not GDI, rough way to get a polygon
  153. const pi=3.141592653589793;
  154. var
  155. z,step:single;
  156. t:arrpt=nil;
  157. temp:pt;
  158. counter:int32=0;
  159. begin
  160. step:=2*pi/num;
  161. z:=0;
  162. while (z<=2*pi) do
  163. begin
  164. counter:=counter+1;
  165. temp.x:=p.x+(50+random(300))*cos(z);
  166. temp.y:=p.y+(50+random(300))*sin(z);
  167. setlength(t,counter);
  168. t[counter-1].x:=temp.x;
  169. t[counter-1].y:=temp.y;
  170. z:=z+step;
  171. end;
  172. exit(t);
  173. end;
  174.  
  175.  /////////////////////////  gdi stuff  //////////////////////////
  176.   procedure drawpolygon(h:hdc;p:arrpt;colour:longword);
  177.   var i:int32;
  178.   begin
  179.   SetDCPenColor(h,colour);
  180.   for i:=0 to high(p)-1 do
  181.     begin
  182.     MoveToEx(h,trunc(p[i].x),trunc(p[i].y),nil);
  183.      LineTo(h, trunc(p[i+1].x),trunc(p[i+1].y));
  184.     end;
  185.    MoveToEx(h,trunc(p[high(p)].x),trunc(p[high(p)].y),nil);
  186.    LineTo(h, trunc(p[0].x),trunc(p[0].y));
  187.    
  188.   end;
  189.    
  190.     procedure drawlines(h:hdc;L:arrline;colour:longword);
  191.     var i:int32;
  192.     begin
  193.     SetDCPenColor(h,colour);
  194.     for i:=0 to high(L) do
  195.     begin
  196.     MoveToEx(h,trunc(L[i].start.x),trunc(L[i].start.y),nil);
  197.      LineTo(h, trunc(L[i].finish.x),trunc(L[i].finish.y));
  198.     end;
  199.     end;
  200.    
  201.  
  202.  
  203. procedure setfontsize(h:hdc;size:integer;style:pchar);
  204. begin
  205.  SelectObject(h,CreateFont(size,0,0,0,400,0,0,0,DEFAULT_CHARSET,OUT_OUTLINE_PRECIS,CLIP_DEFAULT_PRECIS,ANTIALIASED_QUALITY,VARIABLE_PITCH,style));
  206. End;
  207.  
  208. procedure setfontcolours(h:hdc;text:longword;background:longword);
  209. begin
  210.       SetTextColor(h,text) ;
  211.       SetBkColor(h,background);
  212. End;
  213.  
  214. procedure text(h:hdc;x:integer;y:integer;s:pchar);
  215.       Var l:integer;
  216.       begin
  217.       l:=Length(s);
  218.       textouta(h,x,y,s,L);
  219. End;
  220.  
  221. procedure ClearScreen(h:hdc;colour:longint);
  222.       begin
  223.       SetDCBrushColor(h,colour);
  224.       SetDCPenColor(h,colour);
  225.       rectangle(h,0,0,1024,768);
  226. End;
  227.  
  228. procedure hidecursor();
  229. var
  230.     consoleHandle:handle;
  231.      info:CONSOLE_CURSOR_INFO;
  232.      begin
  233.      consolehandle := GetStdHandle(STD_OUTPUT_HANDLE);
  234.      info.dwSize := 100;
  235.      info.bVisible := FALSE;
  236.      SetConsoleCursorInfo(consoleHandle, @info);
  237.      End;
  238.      
  239.    
  240. const
  241.     DC_BRUSH=18;
  242.     DC_PEN=19;
  243.  
  244. var
  245.  Memhdc,WorkingScreen:hdc;
  246.  p:hwnd;
  247.  Membitmap:HBITMAP;
  248.  sysmenu:qword;
  249.  pts:arrpt;
  250.  centre:pt;
  251.  numsides:int32;
  252.  s:ansistring;
  253.  lines:arrline;
  254.  newpoints:arrpt;
  255.  newlines:arrline;
  256. begin
  257.  p:=getconsolewindow();
  258. setwindowpos(p, HWND_TOPMOST, 100, 100, 1024, 768,SWP_SHOWWINDOW);
  259. WorkingScreen:=GetDC(p);
  260. Memhdc := CreateCompatibleDC(WorkingScreen);
  261. Membitmap := CreateCompatibleBitmap(WorkingScreen, 1024, 768);
  262.  
  263. SelectObject(Memhdc, Membitmap);
  264. SelectObject(Memhdc,GetStockObject(DC_BRUSH));
  265. SelectObject(Memhdc,GetStockObject(DC_PEN));
  266. setfontsize(Memhdc,35,'comic sans ms');
  267. setfontcolours(Memhdc,rgb(200,100,0),0);
  268. //'some console instructions
  269. sysMenu := GetSystemMenu(p, False);
  270. DeleteMenu(sysMenu, SC_CLOSE, MF_BYCOMMAND) ;   // 'cannot close console
  271. DeleteMenu(sysMenu, SC_MINIMIZE, MF_BYCOMMAND); //'To prevent user from minimizing console window
  272. DeleteMenu(sysMenu, SC_MAXIMIZE, MF_BYCOMMAND); //'To prevent user from maximizing console window
  273. DeleteMenu(sysMenu, SC_SIZE, MF_BYCOMMAND);     //'non resizable console
  274. hidecursor();
  275. ShowScrollBar(p, SB_BOTH, FALSE);
  276. SetBkMode (Memhdc, TRANSPARENT);
  277. centre.x:=1024/2;
  278. centre.y:=768/2;
  279. While true do
  280.  
  281.     begin
  282.     //non GDI
  283.     numsides:=(4+random(8));
  284.     pts:=createpolygon(centre,numsides);
  285.     newpoints:=rotatepolygon(pts,45);
  286.     lines:=GetLines(newpoints,10);
  287.     newlines:=rotatelines(centroid(pts),lines,-45);
  288.    
  289.     // GDI
  290.       clearscreen(Memhdc,rgb(55,255,255));
  291.      
  292.       text(Memhdc,10,60,'Press escape to finish.');
  293.       str(numsides,s);
  294.       text(Memhdc,10,700,'Number of sides ');
  295.       text(Memhdc,230,700,pchar(s));
  296.      
  297.       drawpolygon(Memhdc,pts,rgb(200,0,0));  //original polygon
  298.       drawlines(Memhdc,newlines,rgb(0,0,0)); // angled lines
  299.      
  300.       BitBlt(WorkingScreen, 0, 0, 1024, 768,Memhdc, 0, 0,SRCCOPY);
  301.       If (GetAsyncKeyState($1B)<>0) Then //' escape key
  302.            begin
  303.             DeleteObject(Membitmap);
  304.             DeleteDC    (Memhdc);
  305.             GetSystemMenu(p,true);
  306.            Exit;
  307.            end;
  308.             sleep(1000);
  309. end;
  310. end.
  311.  
  312.  
  313.  
« Last Edit: May 22, 2022, 07:48:42 pm by BobDog »

Seenkao

  • Sr. Member
  • ****
  • Posts: 407
    • New ZenGL.
Re: Vector graphics floodfill algorithms
« Reply #13 on: May 22, 2022, 04:01:47 pm »
@Seenkao: it is not necessarily so complicated, as I explained above. It is possible to determine where the lines are by comping scanlines. Here those are simply rotated 45 degrees.
Да, в каких-то ситуациях это будет даже проще, чем перебирать все биты. Но чем сложнее фигуры  (более загнутые, например спиральные) которые надо заливать, то с каждым шагом процесс усложняется. А для перебора будет без разницы насколько сложная фигура.
Потому и надо выбирать от сложности заливаемых изображений. Точнее от поставленной задачи.  :)

Google translate:
Yes, in some situations it will be even easier than iterating over all the bits. But the more complex the shapes (more curved, for example spiral ones) that need to be filled in, the process becomes more complicated with each step. And for enumeration, it will not matter how complex the figure is.
Therefore, it is necessary to choose from the complexity of the fill. More precisely from the task at hand. :)
Rus: Стремлюсь к созданию минимальных и достаточно быстрых приложений.
Работаю над ZenGL.
Eng: I strive to create applications that are minimal and reasonably fast.
Working on ZenGL. :)

zamtmn

  • Sr. Member
  • ****
  • Posts: 486
Re: Vector graphics floodfill algorithms
« Reply #14 on: May 22, 2022, 04:07:42 pm »
circular
>>You can look at the code in BGRAFillInfo unit of BGRABitmap
Thanks! Thanks. I'll watch this

Seenkao
>>Потому работа с каждым пикселями даст тебе возможность полного выбора любого пространства
I repeat: I don't have a raster, bmp, ogl context, DC and similar... vectos and coords only. and as result I needed a array of coordinates (in model space, not display space), not a raster
>>Проблема только в том, что если пространство огромно, то и сложность вычисления будет длительно (но это в любом случае)
this is one of the reasons. Raster will not be usable for this!

BobDog
Thanks!

 

TinyPortal © 2005-2018