运行环境 vs2015 winform
其他环境只需要替换对应的画点画线算法即可。
这个算法其实很复杂的,实现起来需要有耐心,一步一步按照算法思路来写代码。
在算法中,我使用的是静态链表(c#没有指针-_-||)
下面的AET为活性边表,NET存储新边表
1.定义数组,变量
class AET//定义AET表,不论是AET还是NET表用的都是这个AET类,因为里面的内容都是一样的
{
public float x;
public float deltax;
public int ymax;
public int next;
public AET()
{
x = -1;
deltax = -1;
ymax = -1;
next = -1;
}
}
private Point[] polygon = new Point[10000];//多边形,依次连接数组中的各点以及最后一个点和第一个点形成的封闭多边形
private int indexOfPolygon;//多边形点的个数
//定义和初始化AET链表的空间
private AET[] AETSource;
void initAET()
{
AETSource = new AET[1000000];
for (int i = 0; i < 1000000; i++)
{
AETSource[i] = new AET();
}
AETSourceindex = 0;
}
2.初始化AET表和NET表
对于AET表的初始化,我们只需要简单的将其赋值为-1,对于NET的话,需要对扫描线进行遍历,把所有低端的定点等于扫描线的值的边加入NET表,因为我们多边形是用点数组来表示的,因此对于低端定点在不同位置需要有不同的写法,此外,对于斜率无穷的线(水平线)需要另外特殊讨论,此前我试过斜率无穷就不加入新边表,会造成扫描线交点的不匹配,使得该行扫描线只填充了一半,写好之后可以注释掉这个判断来试试看。
Graphics g = this.CreateGraphics();
Pen p = new Pen(Brushes.Red);
initAET();
//1.find max and min of y
int ymin = 0x3f3f3f, ymax = 0;
for (int i = 0; i < indexOfPolygon; i++)
{
if (polygon[i].Y > ymax)
ymax = polygon[i].Y;
if (polygon[i].Y < ymin)
ymin = polygon[i].Y;
}
int mAET = -1;//静态链表只需要一个int表示其在AETSource中的位置即可
int[] mNET = new int[ymax - ymin];
for (int i = 0; i < ymax - ymin; i++)
{
mNET[i] = -1;
for (int j = 0; j < indexOfPolygon; j++)
{
if (Math.Min(polygon[j].Y, polygon[(j + 1) % indexOfPolygon].Y) == i + ymin )
{
if (mNET[i] == -1)//首个
mNET[i] = AETSourceindex;
else//非首个,需要找到最后一个
{
int index = mNET[i];
while (AETSource[index].next != -1)
index = AETSource[index].next;
AETSource[index].next = AETSourceindex;
}
if (polygon[j].Y == i + ymin)//j为y比较小的值
{
AETSource[AETSourceindex].x = polygon[j].X;
if (polygon[j].Y != polygon[(j + 1) % indexOfPolygon].Y)
AETSource[AETSourceindex].deltax = (float)(polygon[(j + 1) % indexOfPolygon].X - polygon[j].X) / (float)(polygon[(j + 1) % indexOfPolygon].Y - polygon[j].Y);
else
AETSource[AETSourceindex].deltax = 0;
AETSource[AETSourceindex].ymax = polygon[(j + 1) % indexOfPolygon].Y;
AETSourceindex++;
}
el