CPP►algorithm

4连通种子填充算法

使用了第三方图形库EGEv19.01，C++编写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <graphics.h>
#include <iostream>
using namespace std;

// 输入直线的两端点P0(x0,y0) 和 P1(x1,y1)
void Midpoint_Line(int x0, int y0, int x1, int y1)
{
    int a, b, d1, d2, d, x, y;
    float k;
    if (x1 < x0) {
        //置反操作,使得输出结果平面左右水平翻转,防止画反线段
        d = x0, x0 = x1, x1 = d;
        d = y0, y0 = y1, y1 = d;
    }
    a = y0 - y1, b = x1 - x0;
    if (b == 0)
        //b==0,a<0(k->inf)则放入k>1,a>0(k->-inf)则放入k<-1
        //因为C++除法操作除数为零时候可能会出现undefined的结果
        k = -1 * a * 1000;
    else
        k = (float)a / (x0 - x1);
    x = x0, y = y0;
    putpixel(x, y, RED);
    // 0<=k<=1
    // 1.计算初始值，a=y0−y1， b=x1−x0， D=2a+b
    // 2.x=x0，y=y0
    // 3.绘制点(x，y)，判断D的符号
    // 若D<=0，则(x，y)更新为(x+1，y+1)，D更新为D=D+2a+2b
    // 否则(x，y)更新为(x+1，y)， D更新为D=D+2a
    // 4.当直线没有画完时，重复步骤3，否则结束
    if (k >= 0 && k <= 1) {
        d = 2 * a + b;
        d1 = 2 * a, d2 = 2 * (a + b);
        while (x < x1) {
            if (d <= 0) {
                ++x, ++y, d += d2;
            } else {
                ++x, d += d1;
            }
            putpixel(x, y, RED);
        }
    }
    // -1<=k<=0
    // 1.计算初始值，a=y0−y1， b=x1−x0， D=2a-b
    // 因为当-1<=k<=0时，b为负数，所以要2a-b
    // 2.x=x0，y=y0
    // 3.绘制点(x，y)，判断D的符号
    // 若D>0，则(x，y)更新为(x+1，y-1)，D更新为D=D+2a-2b
    // 因为当-1<=k<=0时，x越大，y越小
    // 否则(x，y)更新为(x+1，y)， D更新为D=D+2a
    // 4.当直线没有画完时，重复步骤3，否则结束
    else if (k <= 0 && k >= -1) {
        d = 2 * a - b;
        d1 = 2 * a - 2 * b, d2 = 2 * a;
        while (x < x1) {
            if (d > 0) {
                ++x, --y, d += d1;
            } else {
                ++x, d += d2;
            }
            putpixel(x, y, RED);
        }
    }
    // k>1
    // 1.计算初始值  a=y0−y1， b=x1−x0， D=2a+b
    // 2.x=x0，y=y0
    // 3.绘制点(x，y)，判断D的符号
    // 若D>0，则(x，y)更新为(x+1，y+1)，D更新为D=D+2a+2b
    // 否则(x，y)更新为(y+1，y)， D更新为D=D+2b
    // 因为当k>1时，y为步进方向。
    // 4.当直线没有画完时，重复步骤3，否则结束
    else if (k > 1) {
        d = a + 2 * b;
        d1 = 2 * (a + b), d2 = 2 * b;
        while (y < y1) {
            if (d > 0) {
                ++x, ++y, d += d1;
            } else {
                ++y, d += d2;
            }
            putpixel(x, y, RED);
        }
    }
    // k<-1
    // 1.计算初始值  a=y0−y1， b=x1−x0， D=2a-b
    // 2.x=x0，y=y0
    // 3.绘制点(x，y)，判断D的符号
    // 若D<=0，则(x，y)更新为(x+1，y-1)，D更新为D=D-2a-2b
    // 因为当k<-1时，a，b均为负数，所以要D=D-2a-2b
    // 因为当k<-1时，x越大，y越小
    // 否则(x，y)更新为(y-1，y)， D更新为D=D-2b
    // 因为当k<-1时，y为步进方向，且x越大y越小，即y-1
    // 4.当直线没有画完时，重复步骤3，否则结束
    else {
        d = a - 2 * b;
        d1 = -2 * b, d2 = 2 * a - 2 * b;
        while (y > y1) {
            if (d <= 0) {
                ++x, --y, d += d2;
            } else {
                --y, d += d1;
            }
            putpixel(x, y, RED);
        }
    }
}
// 上面为中点画线法
// 这里开始为种子填充算法
void SeedFillTC4(int seedx, int seedy)
{
    unsigned int current = getpixel(seedx, seedy);
    if ((current != 11010048) && (current != 43008)) {
        putpixel(seedx, seedy, GREEN);
        cout << endl;
        SeedFillTC4(seedx + 1, seedy); //右
        SeedFillTC4(seedx - 1, seedy); //左
        SeedFillTC4(seedx, seedy + 1); //上
        SeedFillTC4(seedx, seedy - 1); //下
    }
}

int main()
{
    initgraph(800, 600);
    setbkcolor(WHITE);

    Midpoint_Line(20, 40, 20, 20);
    Midpoint_Line(20, 40, 80, 60);
    Midpoint_Line(80, 60, 120, 20);
    Midpoint_Line(120, 20, 80, 10);
    Midpoint_Line(80, 10, 20, 20);

    SeedFillTC4(60, 30);

    getch();
    closegraph();

    return 0;
}