Frequently Asked Questions
оглавление | demo party в ex-СССР | infused bytes e-mag | новости от ib/news | другие проекты | письмо | win koi lat

следующий фpагмент (2)
From: "Kevin Killingsworth" <> Newsgroups: Subject: Floodfill algorithm: solution! Hey there... I've been trying to figure out a good flood fill that doesn't recurse a function and is still relatively fast. I believe I've found an answer using OOP. I know that several people were asking about a good algo. Check it out and let me know what you think... --Kevin Killingsworth enum Rotation {R_NONE, R_HORIZONTAL, R_VERTICAL}; typedef unsigned short int ushort; class Line { public: Line(); Line(ushort px1, ushort py1, ushort px2, ushort py2, Rotation r, ushort basecolor, ushort fillcolor); ~Line(); void set(ushort px1, ushort py1, ushort px2, ushort py2, Rotation r, ushort basecolor, ushort fillcolor); ushort itsLength(); void expand(ushort basecolor, ushort fillcolor); ushort check(ushort pos, ushort basecolor); ushort x1, y1, x2, y2; Rotation itsRotation; Line *prev, *next; }; Line::Line() { x1 = 0; x2 = 0; y1 = 0; y2 = 0; itsRotation = R_NONE; next = NULL; prev = NULL; } Line::Line(ushort px1, ushort py1, ushort px2, ushort py2, Rotation r, ushort basecolor, ushort fillcolor) { set(px1, py1, px2, py2, r, basecolor, fillcolor); } Line::~Line() { } void Line::set(ushort px1, ushort py1, ushort px2, ushort py2, Rotation r, ushort basecolor, ushort fillcolor) { x1 = px1; x2 = px2; y1 = py1; y2 = py2; itsRotation = r; next = NULL; prev = NULL; expand(basecolor, fillcolor); } ushort Line::itsLength() { if (itsRotation == R_HORIZONTAL) return (x2 - x1); else if (itsRotation == R_VERTICAL) return (y2 - y1); else return 0; } void Line::expand(ushort basecolor, ushort fillcolor) { if (itsRotation == R_HORIZONTAL) { while (getpoint(x1-1, y1) == basecolor) { x1--; } while (getpoint(x2+1, y1) == basecolor) { x2++; } } else if (itsRotation == R_VERTICAL) { while (getpoint(x1, y1-1) == basecolor) { y1--; } while (getpoint(x1, y2+1) == basecolor) { y2++; } } drwline(SET, fillcolor, x1, y1, x2, y2); } ushort Line::check(ushort pos, ushort basecolor) { ushort check_val = 0; if (itsRotation == R_HORIZONTAL) { if (getpoint(x1+pos, y1-1) == basecolor) check_val += 1; if (getpoint(x1+pos, y1+1) == basecolor) check_val += 2; } else if (itsRotation == R_VERTICAL) { if (getpoint(x1-1, y1+pos) == basecolor) check_val += 1; if (getpoint(x1+1, y1+pos) == basecolor) check_val += 2; } return check_val; } /*** Okay, here's the actual function... ***/ void Linefill(ushort xseed, ushort yseed, ushort basecolor, ushort fillcolor) { ushort i; Line *cLine = new Line; Line *cNext; ushort dead_end; cLine->set(xseed, yseed, xseed, yseed, R_HORIZONTAL, basecolor, fillcolor); while(cLine != NULL) { dead_end = 1; /* go down the line and see if there are basecolor pixels on either side */ for (i=0; i <= cLine->itsLength(); i++) { if (cLine->check(i, basecolor) > 0) { cNext = new Line; if (cLine->itsRotation == R_HORIZONTAL) cNext->set(cLine->x1+i, cLine->y1, cLine-x1+i, cLine->y1, R_VERTICAL, basecolor, fillcolor); else if (cLine->itsRotation == R_VERTICAL) cNext->set(cLine->x1, cLine->y1+i, cLine->x1, cLine->y1+i, R_HORIZONTAL, basecolor, fillcolor); dead_end = 0; cNext->prev = cLine; cLine->next = cNext; cLine = cNext; break; } /* if */ } /* for */ if (dead_end) { cLine = cLine->prev; if (cLine != NULL) { free(cLine->next); cLine->next = NULL; } } /* if */ } /* while */ } Well.. that's it... fin. Let me know what you all think... --Kevin
следующий фpагмент (3)|пpедыдущий фpагмент (1)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS - Msg : 65 of 89 From : 2:5030/315 14 Feb 96 12:48:14 To : All 17 Feb 96 02:10:24 Subj : Re: How to fill a 2D polygon? -------------------------------------------------------------------------------- In article <>, says... > >Can anyone help me with an algorithm to fill a 2d polygon? > >I am aware of the even-odd method of filling, though I haven't tried it >yet. Finding info on this topic is impossible!! >Any suggsetions? > > Thanks, > -Jason = This following function fill a polygon but it must be closed and you have to know the inside color of the polygon. the new color must be different than the old color void Flood(int x,int y,int oldcol, int newcol) { if(Getpixel(x,y)=oldcol) { putpixel(x,y,newcol) Flood(x+1,y,oldcol,newcol) Flood(x-1,y,oldcol,newcol) Flood(x,y-1,oldcol,newcol) Flood(x,y+1,oldcol,newcol) } } also called Wizoot you can also modify it so you just have to know the color of the border.
следующий фpагмент (4)|пpедыдущий фpагмент (2)
- [90] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 61 of 61 From : Alex Skoltsov 2:5020/272.3 17 Nov 94 19:57:00 To : Dmitry Vinogradov Subj : Заполнение -------------------------------------------------------------------------------- .MSGID: 2:5020/272.3 2ecbfc1a Hello Dmitry! Saturday November 12 1994 23:33, Dmitry Vinogradov wrote to All: DV> P.S. Еще хотелось бы поиметь алгоpитмы/исходники быстpого заполнения DV> выпуклого четыpехугольника заданным цветом. Я когда-то заполнял многоугольники методом построчного сканирования.Если область экрана на которой рисуется полигон локализована (скажем определены Max(X[i]),Min(X[i]), Max(Y[i]), Min(Y[i] по всем вершинам многоугольника) то метод работающий быстрее придумать трудно. Закрашивание делается так: берем начальную точку у края нашей области (скажем у левого) и ползем от него вправо. После пересечения границы полигона начинаем закрашивать точки по которым ползем. После повторного пересечения прекращаем. Если многоугольник выпуклый то после повторного пересечения можно сразу переходить в начало следующей линии. Если этого не делать то правильно будут заполняться произвольные фигуры не имеющие внутри незамктутых или самопересекающихся кривых: /----------- / | / /----\ | B...|*******|....|**|... | \ | | | \/ | |---- | | | **** Рисуем ------------ Такую фигуру можно .... е рисуем B -начальная точка некоей строки /---------- / | / \ | B...|*********\.....|**** | \ | | | |---- | | | ------------ Такую фигуру нельзя Метод просто адаптируется под закраску битмапом. Alex
следующий фpагмент (5)|пpедыдущий фpагмент (3)
- Various nice sources (2:5030/84) ------------------------------ NICE.SOURCES - Msg : 1336 of 1359 From : Yuriy Kuznetsov 2:5030/333.14 06 Apr 97 01:12:00 To : Alexey Ivanov 11 Apr 97 05:05:58 Subj : FillPoly -------------------------------------------------------------------------------- Hi Alexey ! AI> Hет ли y кого иcходника пpцедypы fillpoly или пpоcто закpаcки пpоизвольного AI> тpеyгольника. ;)) Вот. Самый пpостой способ. Я это пpидyмал еще давно. Одна беда - pекypсия. Поэтомy заполняет лишь небольшие площади, напp. : ... circle(100, 100, 29); fill(105, 100, 14); ... зы. Сгодится для пpимитивного pедактоpа иконок ;) >=== Cut ===< procedure fillrec(x,y:word;col,orcol:byte); begin putpixel(x,y,col); if getpixel(x+1,y)=orcol then {Пpосто точки вокpyг} fillrec(x+1,y,col,orcol); if getpixel(x-1,y)=orcol then fillrec(x-1,y,col,orcol); if getpixel(x,y+1)=orcol then fillrec(x,y+1,col,orcol); if getpixel(x,y-1)=orcol then fillrec(x,y-1,col,orcol); end; procedure fill(x,y:word;col:byte); {Ее надо юзить} begin fillrec(x,y,col,getpixel(x,y)); end; >=== Cut ===<
следующий фpагмент (6)|пpедыдущий фpагмент (4)
- Usenet echoes (21:200/1) -------------------------- COMP.GRAPHICS.ALGORITHMS - Msg : 27 of 52 From : 2:5030/144.99 04 Jul 94 14:21:44 To : All 07 Jul 94 05:55:14 Subj : (1) Re: Bresenham Variant: PLEASE HELP!!!!!!! -------------------------------------------------------------------------------- Hi, This has to be the definition of loneliness! (writing replies to your own notes, that is). Anyway, after much cupboard searching, I have found a Turbo Pascal program of 1986 vintage on 5.25" floppy disc! bres.pas, contains implementations of line drawing, triangle filling and circle filling, all of which use only integer calculations, with very simple multiplications, and should, on the right hardware be blindingly fast! These were produced from "The Fundamentals of Interactive Computer Graphics" by J.D. Foley and A. Van Dam, with their wonderful "This is left as an exercise for the reader!". By the way, I saw a great send up of this book called "The fun of interactive computer graphics". Does anyone know of the existence of this pamphlet? Enjoy Mark Jeffery (program follows) program bresenham; const pattern:array[0..3,0..7] of byte=(($aa,$55,$aa,$55,$aa,$55,$aa,$55) ,($ff,$ff,$ff,$ff,$ff,$ff,$ff,$ff) ,($7f,$7f,$7f,$00,$f7,$f7,$f7,$00) ,($00,$66,$ff,$db,$ff,$66,$5a,$81)); type lincor=record xcor,ycor:integer; (* current x and y co ordinates *) xaim,yaim:integer; (* x and y co ordinates aimed for *) actx,acty:integer; (* active increments of x and y *) whichact:boolean; (* if true then x always changed by actx *) (* otherwise y always changed by acty *) inc1,inc2:integer; (* used in internal *) vard:integer (* calculations *) end; var pat,i,x1,x2,y1,y2,x3,y3,colour:integer; c:char; function sgn(num:integer):integer; begin if num=0 then sgn:=0 else if num>0 then sgn:=1 else sgn:=-1 end; procedure plot_point(var xp,yp,value:integer); var nv:boolean; i:integer; begin nv:=(pattern[pat,yp mod 8] and (1 shl (xp mod 8))>0); if nv then i:=1 else i:=0; plot(xp,yp,i) end; procedure setupline(var sl:lincor); var dx,dy:integer; begin sl.actx:=sgn(sl.xaim-sl.xcor); sl.acty:=sgn(sl.yaim-sl.ycor); dx:=abs(sl.xaim-sl.xcor); dy:=abs(sl.yaim-sl.ycor); if dy>dx then begin sl.inc1:=dx shl 1; sl.vard:=sl.inc1-dy; sl.inc2:=sl.vard-dy; sl.whichact:=false end else begin sl.inc1:=dy shl 1; sl.vard:=sl.inc1-dx; sl.inc2:=sl.vard-dx; sl.whichact:=true end end; procedure horz_line(var x1,x2,y2,value:integer); var x:integer; begin if x1>x2 then for x:=x2 to x1 do plot_point(x,y2,value) else for x:=x1 to x2 do plot_point(x,y2,value) end; procedure down_line(var dl:lincor); var oldy:integer; begin oldy:=dl.ycor; repeat if dl.whichact then dl.xcor:=dl.xcor+dl.actx else dl.ycor:=dl.ycor+dl.acty; if dl.vard<0 then dl.vard:=dl.vard+dl.inc1 else begin if dl.whichact then dl.ycor:=dl.ycor+dl.acty else dl.xcor:=dl.xcor+dl.actx; dl.vard:=dl.vard+dl.inc2 end until dl.ycor<>oldy end; procedure swap(var sw:lincor); var tx,ty:integer; begin tx:=sw.xcor; ty:=sw.ycor; sw.xcor:=sw.xaim; sw.ycor:=sw.yaim; sw.xaim:=tx; sw.yaim:=ty; setupline(sw) end; procedure triangle(x1,y1,x2,y2,x3,y3,value:integer); var sl:array[1..3] of lincor; a,b,c,i,v,k:integer; begin sl[1].xcor:=x1; sl[1].ycor:=y1; sl[1].xaim:=x2; sl[1].yaim:=y2; sl[2].xcor:=x1; sl[2].ycor:=y1; sl[2].xaim:=x3; sl[2].yaim:=y3; sl[3].xcor:=x3; sl[3].ycor:=y3; sl[3].xaim:=x2; sl[3].yaim:=y2; v:=0; for i:=1 to 3 do with sl[i] do begin setupline(sl[i]); if abs(yaim-ycor)>v then begin v:=abs(yaim-ycor); a:=i end end; case a of 1:begin b:=2; c:=3 end; 2:begin b:=1; c:=3 end; 3:begin b:=1; c:=2 end end; if (sl[a].ycor=sl[c].ycor) or (sl[a].ycor=sl[c].yaim) then begin k:=b; b:=c; c:=k end; if sl[a].ycor<>sl[b].ycor then swap(sl[b]); if sl[b].yaim<>sl[c].ycor then swap(sl[c]); repeat if sl[a].ycor=sl[b].yaim then b:=c; down_line(sl[a]); down_line(sl[b]); horz_line(sl[a].xcor,sl[b].xcor,sl[a].ycor,value) until (sl[a].ycor=sl[a].yaim) or keypressed end; procedure line(x1,y1,x2,y2,value:integer); var ln:lincor; begin ln.xcor:=x1; ln.ycor:=y1; ln.xaim:=x2; ln.yaim:=y2; setupline(ln); repeat plot_point(ln.xcor,ln.ycor,value); if ln.whichact then ln.xcor:=ln.xcor+ln.actx else ln.ycor:=ln.ycor+ln.acty; if ln.vard<0 then ln.vard:=ln.vard+ln.inc1 else begin if ln.whichact then ln.ycor:=ln.ycor+ln.acty else ln.xcor:=ln.xcor+ln.actx; ln.vard:=ln.vard+ln.inc2 end until (ln.xaim=ln.xcor) and (ln.yaim=ln.ycor) or (ln.xcor>640) or (ln.xcor<0) or (ln.ycor<0) or (ln.ycor>200); plot_point(ln.xcor,ln.ycor,value) end; procedure circle_points(cx,cy,x,y,value:integer); begin draw(cx-x,cy-y,cx+x,cy-y,value); draw(cx-y,cy+x,cx+y,cy+x,value); draw(cx-x,cy+y,cx+x,cy+y,value); draw(cx-y,cy-x,cx+y,cy-x,value) end; procedure circle(cx,cy,radius,value:integer); var x,y,d:integer; begin x:=0; y:=radius; d:=3-2*radius; while x<y do begin circle_points(cx,cy,x,y,value); if d<0 then d:=d+4*x+6 else begin d:=d+4*(x-y)+10; y:=y-1 end; x:=x+1 end; if x=y then circle_points(cx,cy,x,y,value) end; begin c:=' '; hires; circle(320,100,50,7); repeat if upcase(c)='C' then hires; pat:=random(3); triangle(random(640),random(200),random(640),random(200),random(640),random(200) ,1); if keypressed then read(kbd,c); if c in ['0'..'7'] then hirescolor(ord(c)-48); until (upcase(c)='X'); textmode; crtinit end..
следующий фpагмент (7)|пpедыдущий фpагмент (5)
{ DAB726 } { Laboration 3 } { 951021 } { Andy Ekberg 710519 } { Per-Johan AlzКn 710501 } program lab3; uses Crt,Dos,Graph; type dcpts = array[1..50] of pointtype; procedure scanfill(cnt : integer; pts : dcpts;the_color : word); type edgeptr = ^edgerec; edgerec = record yupper : integer; xintersect : real; dxperscan : real; next : edgeptr; end; var edges : array[1..480] of edgeptr; active : edgeptr; scan,i : integer; procedure insertedge(list : edgeptr;var edge : edgeptr); var p,q : edgeptr; begin q:=list; p:=q^.next; while p <> nil do if edge^.xintersect < p^.xintersect then p:=nil else begin q:=p; p:=p^.next; end; edge^.next:=q^.next; q^.next:=edge; end; procedure buildedgelist(cnt : integer;pts : dcpts); var edge : edgeptr; v1,v2 : pointtype; yprev,i : integer; function ynext(k : integer) : integer; var j : integer; begin if (k+1) > cnt then j:=1 else j:=k+1; while pts[k].y = pts[j].y do if (j+1) > cnt then j:=1 else j:=j+1; ynext:=pts[j].y; end; procedure makeedgerec(lower,upper : pointtype;ycomp : integer); begin edge^.dxperscan:=(upper.x-lower.x)/(upper.y-lower.y); edge^.xintersect:=lower.x; if upper.y < ycomp then edge^.yupper:=upper.y-1 else edge^.yupper:=upper.y; insertedge(edges[lower.y],edge); end; begin v1:=pts[cnt]; yprev:=pts[cnt-1].y; for i:=1 to cnt do begin v2:=pts[i]; if v1.y <> v2.y then begin new (edge); if v1.y < v2.y then makeedgerec(v1,v2,ynext(i)) else makeedgerec(v2,v1,yprev); end; yprev:=v1.y; v1:=v2; end; end; procedure buildactivelist(scan : integer); var p,q : edgeptr; begin p:=edges[scan]^.next; while p <> nil do begin q:=p^.next; insertedge(active,p); p:=q; end; end; procedure fillscan(scan : integer); var p1,p2 : edgeptr; i : integer; ch : char; begin p1:=active^.next; while p1 <> nil do begin p2:=p1^.next; for i:=round(p1^.xintersect) to (round(p2^.xintersect)-1) do putpixel(i,scan,the_color); if(scan mod 3)=0 then ch:=readkey; p1:=p2^.next; end; end; procedure updateactivelist(scan : integer); var p,q : edgeptr; procedure deleteafter(q:edgeptr); var p:edgeptr; begin p:=q^.next; q^.next:=p^.next; dispose(p); end; begin q:=active; p:=active^.next; while p <> nil do begin if scan >= p^.yupper then begin p:=p^.next; deleteafter(q) end else begin p^.xintersect:=p^.xintersect + p^.dxperscan; q:=p; p:=p^.next; end; end; end; procedure resortactivelist; var p,q : edgeptr; begin p:=active^.next; active^.next:=nil; while p <> nil do begin q:=p^.next; insertedge(active,p); p:=q; end; end; begin for i:=1 to 480 do begin new(edges[i]); edges[i]^.next:=nil; end; new(active); active^.next:=nil; buildedgelist(cnt,pts); for scan:=1 to 480 do begin buildactivelist(scan); if active^.next <> nil then begin fillscan(scan); updateactivelist(scan); resortactivelist; end; end; end; procedure testGraphError(graphErr: integer); var ch : char; begin if graphErr <> grOk then begin writeLn('Graphics error: ', graphErrorMsg(graphErr)); repeat until keyPressed; ch:=readKey; halt(1) end; end; procedure initGraphics; var graphDriver, graphMode : integer; begin graphDriver:=detect; detectGraph(graphDriver,graphMode); testGraphError(graphResult); initGraph(graphDriver,graphMode,''); testGraphError(graphResult) end; procedure slumppoly(n : integer;var slump : dcpts); var i,j : integer; begin randomize; j:=1; while j <=n do begin slump[j].x:=random(302)+338; slump[j].y:=random(236)+1; for i:=1 to j-1 do if (slump[j].x=slump[i].x) and (slump[j].y=slump[i].y) then j:=j-1; j:=j+1; end; slump[n+1]:=slump[1]; end; var x,y,w,h : integer; star,strange,slump : dcpts; begin initGraphics; setcolor(7); outtextxy(30,360,'Scan-Line Polygon Fill Demo'); outtextxy(30,371,'Please, Press any key to proceed'); x:=490;y:=360;w:=30;h:=120; star[1].x := x-w; star[1].y := y-w; star[2].x := x; star[2].y := y-h; star[3].x := x+w; star[3].y := y-w; star[4].x := x+h; star[4].y := y; star[5].x := x+w; star[5].y := y+w; star[6].x := x; star[6].y := y+h; star[7].x := x-w; star[7].y := y+w; star[8].x := x-h; star[8].y := y; star[9]:= star[1]; strange[1].x := 100; strange[1].y := 120; strange[2].x := 160; strange[2].y := 40; strange[3].x := 185; strange[3].y := 85; strange[4].x := 205; strange[4].y := 10; strange[5].x := 235; strange[5].y := 140; strange[6].x := 235; strange[6].y := 200; strange[7].x := 335; strange[7].y := 100; strange[8].x := 335; strange[8].y := 300; strange[9].x := 185; strange[9].y := 250; strange[10].x := 180; strange[10].y := 300; strange[11].x := 150; strange[11].y := 335; strange[12].x := 25; strange[12].y := 250; strange[13].x := 200; strange[13].y := 180; strange[14] := strange[1]; slumppoly(25,slump); drawpoly(26,slump); drawpoly(14, strange); drawpoly(9,star); scanfill(13,strange,LIGHTGREEN); scanfill(8,star,RED); scanfill(25,slump,LIGHTCYAN); setcolor(YELLOW); outtextxy(30,392,'Press ESC to end'); while ord(readkey)<>27 do ; closegraph; end.

Всего 6 фpагмент(а/ов) |пpедыдущий фpагмент (6)

Если вы хотите дополнить FAQ - пожалуйста пишите.

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,
При перепечатке материалов этой страницы пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ,".