[讨论]怎样实现对一封闭区域的填充～

Tuturo

不如考虑使用漫溢算法？

Eastsun

具体说说，怎么实现啊？

Tuturo

等一下，我贴代码（不过是用vb写的）

Tuturo

Sub Drawing(P_X As Long, P_Y As Long, D_Color As Integer)
'涂色模块
'******************************************************************************************
'首先获得落笔点的坐标和颜色
'在通过深度优先算法进行便历（涂色）
'(D_X，D_Y) 是落笔点的坐标值
'（X，Y）到颜色表格的映射关系：
'           ShowMessageTemp(X, Y * 2 - 1)
'           ShowMessageTemp(X, Y * 2)
'定义颜色模板
Dim Temp_Color(0 To 3, 1 To 2) As Integer
Temp_Color(0, 1) = 1: Temp_Color(0, 2) = 0          '绿色
Temp_Color(1, 1) = 1: Temp_Color(1, 2) = 1          '黄色
Temp_Color(2, 1) = 0: Temp_Color(2, 2) = 1          '红色
Temp_Color(3, 1) = 0: Temp_Color(3, 2) = 0          '无色
Dim P_Color As Integer          '落笔点的颜色
Dim Direction As Integer        '扫描的方向
Dim Chain As Long              '当前节点号
Dim x As Long, y As Long
Dim Text_color As Integer
Dim Progress As Long
Dim ProgressMax As Long
Dim Temp_Showmessage_Height As Long
Dim Temp_Showmessage_Width As Long
Dim Direct(1 To 4, 1 To 2)
Direct(1, 1) = 0: Direct(1, 2) = -1
Direct(2, 1) = 1: Direct(2, 2) = 0
Direct(3, 1) = 0: Direct(3, 2) = 1
Direct(4, 1) = -1: Direct(4, 2) = 0
Temp_Showmessage_Height = ShowMessageTemp_Height
Temp_Showmessage_Width = ShowMessageTemp_Width
ProgressMax = Temp_Showmessage_Height * Temp_Showmessage_Width

ReDim Path(1 To ProgressMax, 1 To 3)   '记录路径（定义可能的最大空间）
'Path(X, 1)      x
'Path(X, 2)      y
'Path(X, 3)      正在搜索的方向
Path(1, 1) = P_X: Path(1, 2) = P_Y: Path(1, 3) = 0                      '第一个节点就是落笔点
P_Color = Get_Color(P_X, P_Y)                                           '获取落笔点的色彩
If P_Color = D_Color Then
    Exit Sub
End If
'顺时针便历，深度优先算法
'
'           1
'
'       4       2
'
'           3
'

With Form8
    .Enabled = False
    '.Picture2.Visible = False
    .Command2.Enabled = False
    .Command3.Enabled = False
    .Command4.Enabled = False
    .Command1.Enabled = False
    .Command5.Enabled = False
    .Option1.Item(1).Enabled = False
    .Option1.Item(0).Enabled = False
    .Option1.Item(2).Enabled = False
    .Option2.Enabled = False
    .Option3.Enabled = False
    .Option4.Item(0).Enabled = False
    .Option4.Item(1).Enabled = False
   
   
    .ProgressBar1.Visible = True
    .ProgressBar1.Enabled = True
    .ProgressBar1.Max = 101
   
    .ProgressBar1.Min = 1
    .ProgressBar1.Value = 1
    .StatusBar1.Panels.Item(2).Text = "正在进行涂色操作..."
End With
Progress = 0
Chain = 1                       '从第一个节点开始
Do_It:
DoEvents                         '响应系统操作
'------------------------------------------循环体结构-------------------------------------------------

Form8.ProgressBar1.Value = Int((Progress / ProgressMax) * 100) + 1
'测试方向加1
Path(Chain, 3) = Path(Chain, 3) + 1
'回溯
If Path(Chain, 3) > 4 Then
    Chain = Chain - 1
    Progress = Progress + 1
   
    '已经全部涂色完成回到根节点的情况
    If Chain = 0 Then
        Exit Sub
    End If
   
    GoTo Do_It
   
End If

'获取当前节点状态
Direction = Path(Chain, 3)
x = Path(Chain, 1)
y = Path(Chain, 2)
If x + Direct(Direction, 1) = 0 Or y + Direct(Direction, 2) = 0 Or x + Direct(Direction, 1) > ShowMessageTemp_Width Or y + Direct(Direction, 2) > ShowMessageTemp_Height Then
'到达边界
    GoTo Do_It
End If
Text_color = Get_Color(x + Direct(Direction, 1), y + Direct(Direction, 2))

If Text_color = P_Color Then
'当测试点与初始的着色点颜色相同时，执行作色操作
'并且通过深度优先原理接上下一个节点
'初始化新节点
Chain = Chain + 1
Path(Chain, 3) = 0
Path(Chain, 1) = x + Direct(Direction, 1)
Path(Chain, 2) = y + Direct(Direction, 2)
'If Chain = 13 Then Stop
'对此节点涂色
ShowMessageTemp(Path(Chain, 1), Path(Chain, 2) * 2 - 1) = Temp_Color(D_Color, 1)
ShowMessageTemp(Path(Chain, 1), Path(Chain, 2) * 2) = Temp_Color(D_Color, 2)
End If
'-------------------------------------------循环体结构-----------------------------------------------
GoTo Do_It

With Form8
    .Enabled = True
    .Picture2.Visible = True
    .Command2.Enabled = True
    .Command3.Enabled = True
    .Command4.Enabled = True
    .Command1.Enabled = True
    .Command5.Enabled = True
    .Option1.Item(1).Enabled = True
    .Option1.Item(0).Enabled = True
    .Option1.Item(2).Enabled = True
    .Option2.Enabled = True
    .Option3.Enabled = True
    .Option4.Item(0).Enabled = True
    .Option4.Item(1).Enabled = True
End With
   
End Sub

Vortex

用DFS啊……
在文曲星上用这种算法太耗资源了吧～
6502的物理栈不够用的，即使采用软件栈也会消耗很多RAM。。。。
不过楼上的程序可以填充图案，而不只是纯色填充～
[em07]

Tuturo

我知道，文曲星上用这种算法真得很恐怖，在电脑上填充一幅图也让我等了N久……
说说DFS吧

Lendy

DFS就是深度优先搜索算法(Depth First Search)，这种方法显然太占资源了……

我想了一种方法，只需消耗1600Bytes作为缓冲区。

等这几天期考完了，再写个程序贴出来。

[此贴子已经被作者于2005-1-13 21:03:19编辑过]

Eastsun

呵呵，很无聊，随便讨论讨论～

就是怎么实现作图工具中的填充功能，注意的是所填充的区域不一定是由一条封闭曲线未成。。。

下面是我写的代码，没实际用处（对内存消耗过大～）

//**************************************************************************

#define DTIME 70*256/1000
//构造一个队列
char buff[160*60][2];
int out,in;
char tx,ty;
void _init()
{
out=0;
in =0;
}
void pop()
{
tx=buff[out][0];
ty=buff[out][1];
out++;
}
void push(char x,char y)
{
buff[in][0]=x;
buff[in][1]=y;
in++;
}
long isEmpty()
{
if(in<=out)return 1;
else return 0;
}
void isFlow()
{
if(in>=160*60-4)
{TextOut(20,16,"error!",64);
getchar();
exit(0);
}
}
//*****************
void fill(char x,char y)
{
_init();
Point(x,y,1);
push(x,y);
while(!isEmpty())
{
  pop();
  if(!GetPoint(tx+1,ty)){Point(tx+1,ty,1);push(tx+1,ty);}
  if(!GetPoint(tx-1,ty)){Point(tx-1,ty,1);push(tx-1,ty);}
  if(!GetPoint(tx,ty+1)){Point(tx,ty+1,1);push(tx,ty+1);}
  if(!GetPoint(tx,ty-1)){Point(tx,ty-1,1);push(tx,ty-1);}
  isFlow();
}//while
}
//*************************
void main()
{
char mx,my;
char ms;
mx=80;
my=40;
Box(1,1,159,79,0,1);
Point(mx,my,1);
while(1)
{
ms=Getms();
Point(mx,my,2);
Delay(30);
Point(mx,my,2);
if(CheckKey('a'))mx--;
else if(CheckKey('w'))my--;
else if(CheckKey('d'))mx++;
else if(CheckKey('x'))my++;
if(CheckKey('i'))Point(mx,my,1);
if(CheckKey('f'))fill(mx,my);
if(CheckKey('z')){Box(2,2,158,78,1,0);Point(mx,my,1);continue;}
ms=Getms()-ms;
if(ms<DTIME)Delay(((DTIME-ms)*1000)>>8);
}
}

[此贴子已经被作者于2004-12-12 12:18:05编辑过]