多边形填充 c语言 Easy-X

一、 实验目的。

使用改进的X扫描线算法进行多边形的填充。

二、 实验工具

VC6.0

三、 实验步骤

1.首先了解多边形填充：
输入：多边形顶点序列输出：最佳逼近这个多边形的像素点集

利用X-射线扫描思想：确定多边形所占用的最大扫描线数，得到多边形顶点max， min从Ymax移动到Ymin

然后进行一些 求交，排序，配对，着色。

在求交排序中采用y向连贯性算法进行改进。

**2.学习y向连贯性算法的大概思路：
** 优先
X | Ymax | 1/k | next
交点递增；交点相同，则增量递增
变成有效边表（开始为空的删除无效边之后的表）
X | Ymax | 1/k | next
X+1/k | Ymax | 1/k | next（y向递增）
（考虑到由于链表可能会很复杂，所以会用结构体代替链表。）

3.建立一个工程文件，将思路转化为c编程语言，进行编译。

代码如下：	
#include <windows.h>
#include <stdio.h>
#include <graphics.h>
#include <conio.h>
#include <string.h>
#include <queue>  
using namespace std;

struct XET   //定义了一个结构体存储来边表
{
	float xmin,ymax,ymin,dx;  
//dx=1/k, ymin为了扫描的时候判断扫描线是否在ymax和ymin之间
}pNET[1024];

struct node    //定义扫描线与边的交点
{
	float x,y;
}point[1024];

drawColor(float a,float b,int y)
{
	int x;
	for(x=a+0.5;x<=b+0.5;x++)
	putpixel(x,y,RED);   //  在指定位置画一红的像素
}
priority_queue<float,vector<float>,greater<float> >s;
int main()
{
	int i,j,t=0,N;   //t-->pNET[]数组下标
	int min_y=0x3fffffff,max_y=-1;    //分别是顶点y的最大值和最小值
	printf("输入顶点数N:");
	scanf("%d",&N);            //根据顶点个数和坐标来自定义多变形的形状
	printf("输入N个顶点\n");
	for(i=0;i<N;i++)      //循环查找所有顶点y坐标的最值
	{
		scanf("%f %f",&point[i].x,&point[i].y);
		if(point[i].y>max_y)     
			max_y=point[i].y;
		if(point[i].y<min_y)
			min_y=point[i].y;
	}
	for(i=min_y;i<=max_y;i++)
	{
		for(j=0;j<N;j++)
		{
			if(point[j].y==i)
			{
				if(point[(j-1+N)%N].y>point[j].y)   //按逆时针走
				{
					struct XET p;
					p.xmin=point[j].x;
					p.ymax=point[(j-1+N)%N].y;
					p.ymin=point[j].y;
					p.dx=(point[(j-1+N)%N].x-point[j].x)/(point[(j-1+N)%N].y-point[j].y);
					if(point[(j+1+N)%N].y<=point[j].y)  //是否局部最值
						p.ymin++;
					pNET[t++]=p;
				}
				if(point[(j+1+N)%N].y>point[j].y)    	//按逆时针走
				{
					struct XET p;
					p.xmin=point[j].x;
					p.ymax=point[(j+1+N)%N].y;
					p.ymin=point[j].y;
					p.dx=(point[(j+1+N)%N].x-point[j].x)/(point[(j+1+N)%N].y-point[j].y);//局部最值
					if(point[(j-1+N)%N].y<=point[j].y)
						p.ymin++;
					pNET[t++]=p;
				}
			}
		}
	}
	initgraph(480,480);  
	for(i=min_y;i<=max_y;i++) //扫描线从ymax到ymin
	{
		for(j=0;j<t;j++)
		{
			if(pNET[j].ymin<=i&&pNET[j].ymax>=i)
			{
				s.push(pNET[j].xmin);
				pNET[j].xmin+=pNET[j].dx;
			}
		}
		while(!s.empty())
		{	
			float a=s.top();s.pop();    //a,b均为扫描线上的x坐标
			float b=s.top();s.pop();
			drawColor(a,b,i);
		}
	}
	getch();
	closegraph();
	return 0;
}

四、 实验结果

今天的生日欸，想把代码分享给大家。嘿嘿