扫描填充算法

效果图

（哈哈可以看出来，扫描从下往上）

C#代码实现

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

using System.Windows.Shapes;

namespace ScanFill
{
    public partial class Form1 : Form
    {
        static Graphics graphics;
        static Bitmap bitmap;
        Polygon mypolygon = new Polygon();
        Point[] points;
        public Form1()
        {
            InitializeComponent();
            graphics = panel1.CreateGraphics();
            bitmap = new Bitmap(panel1.Width, panel1.Height);
        }


    //画出多边形
        private void button1_Click(object sender, EventArgs e)
        {
            Point p1 = new Point(200, 200);
            Point p2 = new Point(300, 200);
            Point p3 = new Point(150, 400);
            Point p4 = new Point(400, 450);
            //Point p1 = new Point(200, 0);
            //Point p2 = new Point(50, 100);
            //Point p3 = new Point(150, 200);
            //Point p4 = new Point(350, 200);
            //Point p5 = new Point(250, 100);

            points = new Point[] { p1, p2, p3, p4 };
            Pen Mypen = new Pen(Color.Blue, 2);
            graphics.DrawPolygon(Mypen, points);
            graphics.DrawImage(bitmap, 0, 0, panel1.Width, panel1.Height);

        }
        //填充多边形。调用方法
        private void button_Fill_Click(object sender, EventArgs e)
        {
            draw.ScanFill(points, Color.Red,graphics);
        }

        public class draw
        {
            static int frist_s = 0;
            static int last_s = 0;

            #region 定义活性边表元素类
            //参与运算的四个量
            class Sideinfo
            {
                public int y_top;//某边的最大纵坐标（y_max）
                public double x_int;//某边与当前扫描线交点的横坐标，它在不断的变化。
                public int delat_y;//当前扫描线与某边最小纵坐标之差，即该边的生命值。
                public double x_change_per_san;//每一次变化x的累计值。当前扫描线每向下移动一次，某边与其交点横坐标的变化值。
                //构造函数
                public Sideinfo()//构造方法
                {
                    y_top = 0;
                    x_int = 0f;//float类型
                    delat_y = 0;
                    x_change_per_san = 0f;
                }
            }
            #endregion
            static List sides;

            //主算法。也是调度算法。相当于main函数
            public static void ScanFill(Point[] points, Color color, Graphics graphics)
            {
                int count = points.Length;//多边形中所有的顶点的数量
                Point[] RegionVertexes = new Point[count];
                Array.Copy(points, RegionVertexes, count);
                sides = new List();//新建一个活性边表
                int bottomscan = BuildSidesList(RegionVertexes, graphics, color);
                SortSidesList();//对边进行排序整理
                int scan;
                frist_s = 0;
                last_s = 0;
                for (scan=sides[0].y_top; scan>bottomscan; scan--)//bottomscan是整个多边形的最小的y值
                {
                    //扫描线scan从最高点开始到最低点的扫描
                    update_frist_and_last(sides.Count, scan);//更新标志变量。即frist和last就位。圈定了求交点的范围
                    int x_int_count = process_x_intersections(scan);//处理各交点的x横坐标。x要按大小进行排序，才能确定其奇偶顺序等……
                    draw_lines(scan, x_int_count, frist_s, graphics, color);//画出扫描线
                    update_sides_list();//更新活性边表
                }
                sides.Clear();//清空边表
                graphics.DrawPolygon(new Pen(Color.Red,2f),RegionVertexes);//画出多边形的边框
            }


            #region 建立活性边表。为边排序
            //按每条边的较大y值排序，为建立活性边表做准备
            //左右顶点等的判定
            public static int BuildSidesList(Point[]Vertexes,Graphics graphics,Color color)
            {
                int n = Vertexes.Length;
                int p1, p2, p3;//目的是判断p2是左右顶点
                p1 = n - 1;
                int bottomscan = Vertexes[p1].Y;

                for (int i = 0; i < n; i++)
                {
                    p2 = i;
                    p3 = (i + 1) % n;//防止下标越界
                    if (Vertexes[p2].Y==Vertexes[p1].Y)//水平边情况
                    {
                        graphics.DrawLine(new Pen(color, 1f), Vertexes[p1], Vertexes[p2]);//直接画出来
                    }
                    else
                    {
                        //以下就是算出该边在活性边表中的四个值。delt_y，x_change_per_san，x_int，y_top

                        double change_perscan = (double)(Vertexes[p2].X - Vertexes[p1].X) / (double)(Vertexes[p2].Y - Vertexes[p1].Y);//每次扫描x的变化
                        int x_int_tmp = Vertexes[p2].X;//x的临时交点
                        sides.Add(new Sideinfo());//把边加到活性边表里

                        sides[sides.Count - 1].delat_y = Math.Abs(Vertexes[p1].Y - Vertexes[p2].Y);//delt_y

                        if ((Vertexes[p1].YVertexes[p2].Y)&&(Vertexes[p2].Y>Vertexes[p3].Y))//右顶点
                        {
                            Vertexes[p2].Y++;
                            x_int_tmp = Vertexes[p1].X;
                            sides[sides.Count - 1].delat_y--;
                        }
                        sides[sides.Count - 1].x_change_per_san = change_perscan;
                        sides[sides.Count - 1].x_int = Vertexes[p1].Y > Vertexes[p2].Y ? Vertexes[p1].X : x_int_tmp;
                        sides[sides.Count - 1].y_top = Math.Max(Vertexes[p1].Y, Vertexes[p2].Y);
                    }
                    if (Vertexes[p2].Y0; i--)
                {
                    for (int j = 0; j < i; j++)
                    {
                        if (sides[j].y_top= scan)))//扫描线的y值小于了活性边表里的下一条边的y_top。也就是delat_y马上要缩小了
                {
                    last_s++;//>=scan,即last_s的下一边被扫描到时，last_s后移
                }
                while (sides[frist_s].delat_y == 0 && frist_s < last_s)
                {
                    frist_s++;//first_s只要所指边的delta_y为0，则first_s后移
                }
            }
            #endregion

            //若需要则按扫描线scan与多边形的交点x值大小将活性边表中first和last之间的边重新排序，以便按顺序画出填充线。
            private static void sort_on_x(int entry)
            {
                //若有当前边鱼scan交点x值小于在活性边表中排在它之前的x值，则它前移
                while ((entry>frist_s)&&(sides[entry].x_int0)//delat_y>0就代表其正在求交点
                    {
                        x_int_count++;
                        sort_on_x(k);//进行排序
                    }
                }
                return x_int_count;
            }

            //画出扫描填充线，按照交点x值的奇偶特性进行画线
            private static void draw_lines(int scan,int x_int_count,int index,Graphics graphics,Color color)
            {
                int k, x1, x2;
                //找到奇数的线开始画线。
                for (k = 1;  k<= (x_int_count)/2; k++)
                {
                    while (sides[index].delat_y==0)
                    {
                        index++;
                    }
                    x1 = (int)(sides[index].x_int);
                    index++;
                    while (sides[index].delat_y==0)
                    {
                        index++;
                    }
                    x2 = (int)(sides[index].x_int);
                    graphics.DrawLine(new Pen(color,1f),x1,scan,x2,scan);
                    index++;
                }
            }

            //更新活性边表。主要是delta_y 和x_int两项。
            private static void update_sides_list()
            {
                int k;
                for ( k = frist_s; k < last_s+1; k++)//更新只针对first和last之间的边。
                {
                    if (sides[k].delat_y>0)//条件是此边的delta_y>0，表明它正在被扫描
                    {
                        sides[k].delat_y--; //delat_y减一
                        //x_int减去每次扫描中横坐标的变化量，对于每条边他们搁置的变化量(x_change_per_san)各不相同
                        sides[k].x_int -= sides[k].x_change_per_san;
                    }
                }
            }
        }
    }
}