Lazarus

Programming => Graphics and Multimedia => Graphics => Topic started by: zamtmn on May 21, 2022, 12:49:38 pm

Title: Vector graphics floodfill algorithms
Post by: zamtmn 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?
Title: Re: Vector graphics floodfill algorithms
Post by: Roland57 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

Title: Re: Vector graphics floodfill algorithms
Post by: zamtmn 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
Title: Re: Vector graphics floodfill algorithms
Post by: VTwin on May 21, 2022, 06:11:25 pm
Maybe this:

https://wiki.lazarus.freepascal.org/Developing_with_Graphics#Self-overlapping_polygons

Perhaps not, only color fills.
Title: Re: Vector graphics floodfill algorithms
Post by: zamtmn 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.
Title: Re: Vector graphics floodfill algorithms
Post by: Seenkao on May 21, 2022, 09:39:11 pm
Привет.
Одним из самых действенных средств будет обычный перебор. Описано в этой игре. (http://delphiexpert.ru/delphi-uroki-sozdayom-prostuyu-igruchast-2.html)
Вероятнее всего, можно немного ускорить процедуру, записывая все пиксели отдельно, а потом просто полученные пиксели сразу залить определённым цветом. Сложность в том, что если надо заливать каким-то узором, надо дублировать изображение и все пиксели отмечать на втором изображении (для сплошной заливки не обязательно дублировать изображение, можно просто координаты всех пикселей взять) и в соответствии с отмеченными пикселями заполнять узором то, что было отмечено.

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

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

----------------------------------------------
Google translate:
Hello.
One of the most effective means will be the usual enumeration. Described in this game. (http://delphiexpert.ru/delphi-uroki-sozdayom-prostuyu-igruchast-2.html)
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.
Title: Re: Vector graphics floodfill algorithms
Post by: circular 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.
Title: Re: Vector graphics floodfill algorithms
Post by: BobDog 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.  
Title: Re: Vector graphics floodfill algorithms
Post by: zamtmn on May 22, 2022, 06:09:58 am
Thanks. But without pixels, without DC and other graphics.
Only mathematics
Title: Re: Vector graphics floodfill algorithms
Post by: circular 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
Title: Re: Vector graphics floodfill algorithms
Post by: Seenkao 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.
Title: Re: Vector graphics floodfill algorithms
Post by: circular 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.
Title: Re: Vector graphics floodfill algorithms
Post by: BobDog 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.  
Title: Re: Vector graphics floodfill algorithms
Post by: Seenkao 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. :)
Title: Re: Vector graphics floodfill algorithms
Post by: zamtmn 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!
Title: Re: Vector graphics floodfill algorithms
Post by: circular on May 22, 2022, 06:34:58 pm
You're welcome.

By the way, to rotate the points you can use unit BGRATransform to create affine matrices that you can apply to arrays of TPointF.
Title: Re: Vector graphics floodfill algorithms
Post by: zamtmn on May 22, 2022, 06:51:51 pm
There will be no problems with transformations.
I thought that this topic already has a lot of solutions, as it is for raster. and I was surprised when I didn't find anything on the first try
Title: Re: Vector graphics floodfill algorithms
Post by: BobDog on May 22, 2022, 08:01:21 pm

I noticed a couple of hints in my code, so I repaired them.
What will be your graphics method to plot these lines once you have sorted out an algorithm?
I more or less use the Windows console for simple graphics in freepascal.
I tend just to write plain code (no projects) in Geany, I don't go through the process of creating a library (unit) on the fly. I avoid those complications. I only use Lazarus for testing, it is very good at giving warnings and hints.
Title: Re: Vector graphics floodfill algorithms
Post by: zamtmn on May 22, 2022, 08:07:55 pm
>>What will be your graphics method to plot these lines once you have sorted out an algorithm?
OpenGL or GDI
it for zcad https://forum.lazarus.freepascal.org/index.php/topic,16665.0.html
Title: Re: Vector graphics floodfill algorithms
Post by: BobDog on May 22, 2022, 08:51:45 pm

Thanks, I see your project. I ran a couple of samples in zcad.exe.
Looks very neat.


Title: Re: Vector graphics floodfill algorithms
Post by: ADMGNS on May 28, 2022, 01:42:05 am
hello

have you tried "point in polygon" ways? you know, it's a kind of solution for irregular polygon filling..

pls see the attachment

regs
Title: Re: Vector graphics floodfill algorithms
Post by: zamtmn on June 01, 2022, 08:21:10 am
ADMGNS
thanks, it's a little different

Seenkao
>>First, if this happens separately, then it will be necessary to dock the pattern with each other
Everything turned out to be much simpler than it seems at first glance. Nothing needs to be dock-connect-attach. For example, in the picture it seems that this is a complex pattern, but in fact it is just a set of dotted lines at different angles with different steps
Title: Re: Vector graphics floodfill algorithms
Post by: ADMGNS on June 01, 2022, 10:12:04 pm
hello again..

in my example code, you can see a line below...

imgDraw.Canvas.Pixels[x, y] := imgPattern.Canvas.Pixels[x, y];

so, if you have a bitmap that made of a tiled pattern, you can copy the pixels from this bitmap into the polygon using "point in polygon" methods.. and, as a result, you can get a pattern filled polygon..

i know, this is a very simple, even maybe a primitive approach.

if we talk more wideview angle, we must define a record that consists of (multi)shapes (ie, ellipses, polygons, arcs etc) and some statues, ie including or excluding, and also color/stroke/pattern etc features.. as you know, this is a REGION logic supported many graphics libraries.. anyway..

regs
TinyPortal © 2005-2018