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

关注
C/C++实现图形学扫描线填充算法_C 语言www.shan-machinery.com这篇文章主要介绍了C/C++实现图形学扫描线填充算法,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

在上图形学课的时候,学习了扫描线填充算法。不过在完成实验的时候在真正理解了该算法,在此记录一下,如果有表达上的错误,欢迎指正!

扫描线填充算法通过在与图形相交的第(1,2)、(3,4)... 边之间划线不断不断填充图形。因此,在扫描时就需要确定什么时候与图形的某条边相交、划线的时候x的范围是多少以及划线时是从哪个交点画至另一个交点。

结构体如下所示:

为了节省存储的空间,边表项也使用链表结构,将图形中ymin值相同的边链接在同一个边表项后,这样在扫描的时候方便添加。

具体的流程如下:

一、初始化活动边表

1. 统计并初始化表项

2. 将每条边分别链接在表项后

二、 绘制与填充

1. 取出当前与扫描线相交的边

① 取出ymin 大于当前扫描线的y值的边

② 删除ymax 小于等于当前扫描线的边(①②过程可以排除掉与扫描线平行的边)

2. 将取出的边按照左右顺序排序(根据边的最低点的坐标与直线的斜率判断)

3. 划线并直接在原结构上修改边的x值(因为是在一个函数内,修改保存的值仅限于函数内,并不影响main函数中的值)

具体的代码如下所示,使用的库是EasyX(可以在http://www.easyx.cn/下载):

#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 ? y1 : y2); } //返回ymin int YMin() { return (y1 < y2 ? y1 : y2); } //返回ymin 端点的x 值 int x() { return (y1 < y2 ? x1 : x2); } //返回直线的斜率,按照传入的参数的顺序 double KOfLine() { return ((y2 - y1)*1.0 / (x2 - x1)); } }; class Solution{public: //根据多边形初始化活动表 //参数 T 活动边表 //参数edges 用于初始化的边数组 //参数 edge_num 用于初始化的边的个数 void Init(ET &T, Edge *edges, int edge_num) { //初始化活动边表结构体 T.item_count = 0; T.itemHeader = NULL; int ymins[20]; //存储ymin ,决定活动边表的个数以及表项的内容 T.item_count = TableItemCount(edges, edge_num, ymins); T.itemHeader = (TableItem*)malloc(sizeof(TableItem)); T.itemHeader->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 < edge_num; ++j) {this->AppendNode(T, edges[j].y_min, edges[j]); } //方法结束 ////////测试区//////////// //cout next; }//while (p != NULL) } //将指定y值的节点添加到该表项, 该方法插入的顺序取决于调用该方法传入参数的顺序 //该方法将新节点插入到对应表项的邻接链表的末尾 void AppendNode(ET &T, int place_y, Edge &e) { ////////测试区////////// //cout 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 < curr_edge_num - 1; ++i) {for (int j = i + 1; j < curr_edge_num; ++j) { if (this->IsRightTo(currEdges[i], currEdges[j])) { Edge tmp = currEdges[i]; currEdges[i] = currEdges[j]; currEdges[j] = tmp; }} } //// // getchar(); // cout https://www.shan-machinery.com