C/C++实现图形学扫描线填充算法

#include "graphics.h"
#include "stdio.h"
#include "conio.h"
#include 
#include 
#include 
#include 
 
using namespace std;
#define MAX_VOL 20
//多边形的边的数据结构
typedef struct Edge
{
 int y_max, y_min; //该有向边的y坐标的最大值与最小值
 double x, deltax; //该有向边的x的最小值以及x的变化的量（1/斜率）
 struct Edge* next; //指向下一条边的指针
 
}Edge;
//活动边表表项
typedef struct TableItem
{
 int curr_y;  //该表项的y坐标值 ymin
 Edge *firstNode; //该表项的首个节点，如果没有，NULL
 struct TableItem *next; //指向下一个活动边表表项的指针
}TableItem;
//活动边表结构体
typedef struct Table
{
 TableItem *itemHeader; //活动边表的表项header
 int item_count; //活动边表表项的个数
}ET;
 
class Point
{
private:
 int x1, x2, y1, y2;
public:
 Point(int x1, int y1, int x2, int y2)
 {
 this->x1 = x1;
 this->x2 = x2;
 this->y1 = y1;
 this->y2 = y2;
 }
 //返回两个点之中的ymax
 int YMax()
 {
 return (y1 > y2 &＃63; y1 : y2);
 }
 //返回ymin
 int YMin()
 {
 return (y1 curr_y = ymins[0];
 T.itemHeader->firstNode = NULL;
 T.itemHeader->next = NULL;
 TableItem *p = T.itemHeader; //指向头结点
 for (int i = 1; icurr_y = ymins[i];
  e->firstNode = NULL;
  e->next = NULL;
  p->next = e;
  p = e;
 }
 
 //按照用于初始化的边数组初始化活动边表
 p = T.itemHeader;
 for (int j = 0; j AppendNode(T, edges[j].y_min, edges[j]);
 }
 //方法结束
 ////////测试区////////////
 //cout <<"遍历表项。。。。。" <curr_y <firstNode;
 // while (ele != NULL) {
 // cout <<"表项中的边： x = " <x <<" y_min = " <y_min <<" y_max = " <y_max <<
 //  "deltax = " <deltax <next;
 // }
 
 // p = p->next;
 //}
 ////////测试删除结点////////
 //p = T.itemHeader;
 //int yMax = 0;
 //while (yMax <24) {
 // p = T.itemHeader;
 // cout <<"-------------------------------" <DeleteNode(T, yMax);
 // while (p != NULL) {
 // cout <<"当前表项y : " <curr_y <firstNode;
 // while (ele != NULL) {
 //  cout <<"表项中的边： x = " <x <<" y_min = " <y_min <<" y_max = " <y_max <<
 //  "deltax = " <deltax <next;
 // }
 // p = p->next;
 // }
 // yMax++;
 //}
 
 /////////////////////////
 
 
 }
 
 
 
 //用于根据边数组计算需要多少个表项
 //表项的个数取决于边的ymin的个数
 //返回值 ymin 数组
 //返回 item_num 表项的个数
 int TableItemCount(Edge *edges, int edge_num, int* ymins)
 {
 int count = 0;
 for (int i = 0; ix = (double)point.x();
  newEdge->y_max = point.YMax();
  newEdge->y_min = point.YMin();
  newEdge->deltax = 1.0 / point.KOfLine(); // 斜率分之一
  newEdge->next = NULL;
  newEdges[j++] = *(newEdge);
 }
 return newEdges;
 }
 //删除所有的小于ymax 的节点
 //参数 curr_ymax 当前扫描线的y值
 void DeleteNode(ET &T, int curr_ymax)
 {
 TableItem *p = T.itemHeader; //指向表项的指针
 while (p != NULL) {
  Edge *item = p->firstNode; //指向表项的邻接链表的指针
  Edge *itempre = p->firstNode;   //指向前一个边结点的指针
  while (item != NULL) {
  if (item->y_max <= curr_ymax) { //删除该结点
   T.item_count--; //当前活动边表中的边的个数-1
   //判断该结点是否是该链表的头结点
   if (item == p->firstNode) {
   p->firstNode = (Edge*)malloc(sizeof(Edge));
   p->firstNode = item->next;
   free(item);  //释放该结点
   item = p->firstNode; //重新指向firstnode结点
   itempre = p->firstNode;
   }
   else {
   itempre->next = item->next; //修改前一个结点的next的值
   free(item);   //删除该指针
   item = itempre->next; //继续向后遍历
   }
  }//if (item->y_max next;
  }
  }//while (item != NULL)
  p = p->next;
 }//while (p != NULL)
 
 
 }
 
 //将指定y值的节点添加到该表项, 该方法插入的顺序取决于调用该方法传入参数的顺序
 //该方法将新节点插入到对应表项的邻接链表的末尾
 void AppendNode(ET &T, int place_y, Edge &e)
 {
 ////////测试区//////////
 //cout <<"In Append , place_y = " <curr_y == e.y_min)
  break;
  p = p->next;
 }
 //将边插入到该表项的邻接链表中
 Edge *egp = p->firstNode; //egp 指向该表项的首个邻接节点
 if (egp == NULL) { //如果该表项还没有节点，直接插入
  egp = (Edge*)malloc(sizeof(Edge));
  *(egp) = e;
  egp->next = NULL;
  p->firstNode = egp;
 }
 else {
  Edge *pre = egp;
  while (egp != NULL) {
  pre = egp;
  egp = egp->next;
  }
  Edge *newedge = (Edge*)malloc(sizeof(Edge));
  *(newedge) = e;
  pre->next = newedge;
  newedge->next = NULL;
 }
 
 
 }
 
 //绘图的方法
 void Draw(ET T) {
 //首先取出ymin 值小于当前扫描线y 的边
 //按照顺序配对
 int curr_y = 0, curr_edge_num = 0, curr_gy = graphy(curr_y); //图形坐标的扫描线的y坐标
 Edge *currEdges = (Edge*)malloc(sizeof(Edge) * 20); //用于存放指针的数组
 //将每条边的记录的x 化为图形上的坐标
 TableItem *p = T.itemHeader;
 while (p != NULL) {
  Edge *q = p->firstNode;
  while (q != NULL) {
  q->x = graphx(q->x);
  q = q->next;
  }
  p = p->next;
 }
 
 
 
 for (; curr_y <30; curr_gy--, curr_y = realy(curr_gy)) {
  this->DeleteNode(T, curr_y); //删除当前扫描过的边（ymax 小于 curr_y）
  currEdges = this->GetCurrEdges(T, curr_y, curr_edge_num); //获取当前与扫描线相交的边
  //对获取到的边进行排序、配对
  for (int i = 0; i IsRightTo(currEdges[i], currEdges[j])) {
   Edge tmp = currEdges[i];
   currEdges[i] = currEdges[j];
   currEdges[j] = tmp;
   }
  }
 
  }
 
 
  ////
 // getchar();
 // cout <<"------------------------------" <" <<(int)currEdges[2 * j + 1].x <<" , " <firstNode;
  while (q != NULL) {
  if (q->y_min <= curr_y) { //等于号很重要，否则会在图形中出现空白区
   currEdges[i++] = *q; //将当前边的值取出（不改变原活动表）
  }
  q = q->next;
  }
  p = p->next;
 }
 edge_num = i; //保存取出的边的个数
 return currEdges;
 }
 
 //判断edge1 是否在edge2 的右边的方法
 bool IsRightTo(Edge edge1, Edge edge2) {
 if (edge1.x > edge2.x) //如果edge1最低点的x坐标小于edge2的最低点的x的坐标，则edge1在edge2的右边
  return true;
 else {
  if (edge1.x  x_max2)
  return true;
 }
 return false;
 }
 
};
 
int main()
{
 //TODO 测试活动边表初始化
 Solution solution;
 int edges[] = { 4,18,14,14,26,22,26,10,14,2,4,6,4,18 };
 Edge* newEdges = solution.InitEdges(edges, 6);
 ET T;
 solution.Init(T, newEdges, 6); //初始化活动边表
 
 
 
 initgraph(800, 800, SHOWCONSOLE);
 solution.DrawCoordinate(edges, 6);
 solution.Draw(T);
 getchar();
 closegraph();
 return 0;
}