следующий фpагмент (2)From: "Kevin Killingsworth" <kkil6139@stu.oru.edu>
Newsgroups: comp.graphics.algorithms
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
kkil6139@stu.oru.edu
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 : user@eudil.univ-lille1.fr 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 <3118FA41.EBA@www.lib.uconn.edu>, sh@www.lib.uconn.edu 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 = JRM94001@uconnvm.uconn.edu
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)
}
}
Alexandre.Mavel@eudil.univ-lille1.fr
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 : jeffery@bst.dec.com 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.