C/C++實(shí)現(xiàn)圖形學(xué)掃描線填充算法
在上圖形學(xué)課的時(shí)候,學(xué)習(xí)了掃描線填充算法。不過(guò)在完成實(shí)驗(yàn)的時(shí)候在真正理解了該算法,在此記錄一下,如果有表達(dá)上的錯(cuò)誤,歡迎指正!
掃描線填充算法通過(guò)在與圖形相交的第(1,2)、(3,4)... 邊之間劃線不斷不斷填充圖形。因此,在掃描時(shí)就需要確定什么時(shí)候與圖形的某條邊相交、劃線的時(shí)候x的范圍是多少以及劃線時(shí)是從哪個(gè)交點(diǎn)畫至另一個(gè)交點(diǎn)。
結(jié)構(gòu)體如下所示:
為了節(jié)省存儲(chǔ)的空間,邊表項(xiàng)也使用鏈表結(jié)構(gòu),將圖形中ymin值相同的邊鏈接在同一個(gè)邊表項(xiàng)后,這樣在掃描的時(shí)候方便添加。
具體的流程如下:
一、初始化活動(dòng)邊表
1. 統(tǒng)計(jì)并初始化表項(xiàng)
2. 將每條邊分別鏈接在表項(xiàng)后
二、 繪制與填充
1. 取出當(dāng)前與掃描線相交的邊
① 取出ymin 大于當(dāng)前掃描線的y值的邊
② 刪除ymax 小于等于當(dāng)前掃描線的邊(①②過(guò)程可以排除掉與掃描線平行的邊)
2. 將取出的邊按照左右順序排序(根據(jù)邊的最低點(diǎn)的坐標(biāo)與直線的斜率判斷)
3. 劃線并直接在原結(jié)構(gòu)上修改邊的x值(因?yàn)槭窃谝粋€(gè)函數(shù)內(nèi),修改保存的值僅限于函數(shù)內(nèi),并不影響main函數(shù)中的值)
具體的代碼如下所示,使用的庫(kù)是EasyX(可以在http://www.easyx.cn/下載):
#include "graphics.h" #include "stdio.h" #include "conio.h" #include <stdlib.h> #include <math.h> #include <cmath> #include <iostream> using namespace std; #define MAX_VOL 20 //多邊形的邊的數(shù)據(jù)結(jié)構(gòu) typedef struct Edge { int y_max, y_min; //該有向邊的y坐標(biāo)的最大值與最小值 double x, deltax; //該有向邊的x的最小值以及x的變化的量(1/斜率) struct Edge* next; //指向下一條邊的指針 }Edge; //活動(dòng)邊表表項(xiàng) typedef struct TableItem { int curr_y; //該表項(xiàng)的y坐標(biāo)值 ymin Edge *firstNode; //該表項(xiàng)的首個(gè)節(jié)點(diǎn),如果沒(méi)有,NULL struct TableItem *next; //指向下一個(gè)活動(dòng)邊表表項(xiàng)的指針 }TableItem; //活動(dòng)邊表結(jié)構(gòu)體 typedef struct Table { TableItem *itemHeader; //活動(dòng)邊表的表項(xiàng)header int item_count; //活動(dòng)邊表表項(xiàng)的個(gè)數(shù) }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; } //返回兩個(gè)點(diǎn)之中的ymax int YMax() { return (y1 > y2 ? y1 : y2); } //返回ymin int YMin() { return (y1 < y2 ? y1 : y2); } //返回ymin 端點(diǎn)的x 值 int x() { return (y1 < y2 ? x1 : x2); } //返回直線的斜率,按照傳入的參數(shù)的順序 double KOfLine() { return ((y2 - y1)*1.0 / (x2 - x1)); } }; class Solution { public: //根據(jù)多邊形初始化活動(dòng)表 //參數(shù) T 活動(dòng)邊表 //參數(shù)edges 用于初始化的邊數(shù)組 //參數(shù) edge_num 用于初始化的邊的個(gè)數(shù) void Init(ET &T, Edge *edges, int edge_num) { //初始化活動(dòng)邊表結(jié)構(gòu)體 T.item_count = 0; T.itemHeader = NULL; int ymins[20]; //存儲(chǔ)ymin ,決定活動(dòng)邊表的個(gè)數(shù)以及表項(xiàng)的內(nèi)容 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; //指向頭結(jié)點(diǎn) for (int i = 1; i<T.item_count; ++i) { //依次創(chuàng)建活動(dòng)邊表的各個(gè)表項(xiàng),并連接在一起 TableItem *e = (TableItem*)malloc(sizeof(TableItem)); e->curr_y = ymins[i]; e->firstNode = NULL; e->next = NULL; p->next = e; p = e; } //按照用于初始化的邊數(shù)組初始化活動(dòng)邊表 p = T.itemHeader; for (int j = 0; j < edge_num; ++j) { this->AppendNode(T, edges[j].y_min, edges[j]); } //方法結(jié)束 ////////測(cè)試區(qū)//////////// //cout << "遍歷表項(xiàng)。。。。。" << endl; //p = T.itemHeader; //while (p != NULL) { // cout << "當(dāng)前表項(xiàng)y : " << p->curr_y << endl; // Edge *ele = p->firstNode; // while (ele != NULL) { // cout << "表項(xiàng)中的邊: x = " << ele->x << " y_min = " << ele->y_min << " y_max = " << ele->y_max << // "deltax = " << ele->deltax << endl; // ele = ele->next; // } // p = p->next; //} ////////測(cè)試刪除結(jié)點(diǎn)//////// //p = T.itemHeader; //int yMax = 0; //while (yMax < 24) { // p = T.itemHeader; // cout << "-------------------------------" << endl; // cout << "當(dāng)前y max :" << yMax << endl; // this->DeleteNode(T, yMax); // while (p != NULL) { // cout << "當(dāng)前表項(xiàng)y : " << p->curr_y << endl; // Edge *ele = p->firstNode; // while (ele != NULL) { // cout << "表項(xiàng)中的邊: x = " << ele->x << " y_min = " << ele->y_min << " y_max = " << ele->y_max << // "deltax = " << ele->deltax << endl; // ele = ele->next; // } // p = p->next; // } // yMax++; //} ///////////////////////// } //用于根據(jù)邊數(shù)組計(jì)算需要多少個(gè)表項(xiàng) //表項(xiàng)的個(gè)數(shù)取決于邊的ymin的個(gè)數(shù) //返回值 ymin 數(shù)組 //返回 item_num 表項(xiàng)的個(gè)數(shù) int TableItemCount(Edge *edges, int edge_num, int* ymins) { int count = 0; for (int i = 0; i<edge_num; ++i) { if (!isInArray(ymins, edges[i].y_min, count)) { ymins[count++] = edges[i].y_min; } } //將ymin 升序排序 for (int j = 0; j<count - 1; ++j) { for (int k = j + 1; k<count; ++k) { if (ymins[k] < ymins[j]) { int tmp = ymins[k]; ymins[k] = ymins[j]; ymins[j] = tmp; } } } return count; } //判斷一個(gè)整數(shù)是否在整數(shù)數(shù)組中 bool isInArray(int *array, int e, int array_length) { for (int i = 0; i<array_length; ++i) { if (array[i] == e) { return true; } } return false; } //傳入edges數(shù)組,初始化,返回Edge 結(jié)構(gòu)體數(shù)組 //因?yàn)樾枰欠忾]圖形,所以,在邊數(shù)組中,最后的點(diǎn)的坐標(biāo)設(shè)為起始點(diǎn)的坐標(biāo),傳入的edge_num 不變 Edge* InitEdges(int *edges, int edge_num) { Edge *newEdges = (Edge*)malloc(sizeof(Edge)*edge_num); int j = 0; for (int i = 0; i<edge_num; ++i) { Point point(edges[2 * i], edges[2 * i + 1], edges[2 * (i + 1)], edges[2 * (i + 1) + 1]); Edge *newEdge = (Edge*)malloc(sizeof(Edge)); newEdge->x = (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 的節(jié)點(diǎn) //參數(shù) curr_ymax 當(dāng)前掃描線的y值 void DeleteNode(ET &T, int curr_ymax) { TableItem *p = T.itemHeader; //指向表項(xiàng)的指針 while (p != NULL) { Edge *item = p->firstNode; //指向表項(xiàng)的鄰接鏈表的指針 Edge *itempre = p->firstNode; //指向前一個(gè)邊結(jié)點(diǎn)的指針 while (item != NULL) { if (item->y_max <= curr_ymax) { //刪除該結(jié)點(diǎn) T.item_count--; //當(dāng)前活動(dòng)邊表中的邊的個(gè)數(shù)-1 //判斷該結(jié)點(diǎn)是否是該鏈表的頭結(jié)點(diǎn) if (item == p->firstNode) { p->firstNode = (Edge*)malloc(sizeof(Edge)); p->firstNode = item->next; free(item); //釋放該結(jié)點(diǎn) item = p->firstNode; //重新指向firstnode結(jié)點(diǎn) itempre = p->firstNode; } else { itempre->next = item->next; //修改前一個(gè)結(jié)點(diǎn)的next的值 free(item); //刪除該指針 item = itempre->next; //繼續(xù)向后遍歷 } }//if (item->y_max < curr_ymax) else { itempre = item; item = item->next; } }//while (item != NULL) p = p->next; }//while (p != NULL) } //將指定y值的節(jié)點(diǎn)添加到該表項(xiàng), 該方法插入的順序取決于調(diào)用該方法傳入?yún)?shù)的順序 //該方法將新節(jié)點(diǎn)插入到對(duì)應(yīng)表項(xiàng)的鄰接鏈表的末尾 void AppendNode(ET &T, int place_y, Edge &e) { ////////測(cè)試區(qū)////////// //cout << "In Append , place_y = " << place_y << " e.ymin = " << e.y_min << endl; //cout << "item count" << T.item_count << endl; /////////////////////// TableItem *p = T.itemHeader; //指向活動(dòng)邊表的頭結(jié)點(diǎn) //將邊e插入到對(duì)應(yīng)的表項(xiàng) //之后在該表項(xiàng)中按照x的大小確定插入的位置 for (int i = 0; i < T.item_count; ++i) { if (p->curr_y == e.y_min) break; p = p->next; } //將邊插入到該表項(xiàng)的鄰接鏈表中 Edge *egp = p->firstNode; //egp 指向該表項(xiàng)的首個(gè)鄰接節(jié)點(diǎn) if (egp == NULL) { //如果該表項(xiàng)還沒(méi)有節(jié)點(diǎn),直接插入 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 值小于當(dāng)前掃描線y 的邊 //按照順序配對(duì) int curr_y = 0, curr_edge_num = 0, curr_gy = graphy(curr_y); //圖形坐標(biāo)的掃描線的y坐標(biāo) Edge *currEdges = (Edge*)malloc(sizeof(Edge) * 20); //用于存放指針的數(shù)組 //將每條邊的記錄的x 化為圖形上的坐標(biāo) 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); //刪除當(dāng)前掃描過(guò)的邊(ymax 小于 curr_y) currEdges = this->GetCurrEdges(T, curr_y, curr_edge_num); //獲取當(dāng)前與掃描線相交的邊 //對(duì)獲取到的邊進(jìn)行排序、配對(duì) 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 << "------------------------------" << endl; setcolor(BLUE); for (int j = 0; j < curr_edge_num / 2; ++j) { /// // cout << "line :" << (int)currEdges[2 * j].x << " , " << curr_y << "----->" << (int)currEdges[2 * j + 1].x << " , " << curr_y << // " edge_num = " << curr_edge_num << endl; line((int)currEdges[2 * j].x, curr_gy, (int)currEdges[2 * j + 1].x, curr_gy); Edge *curr_edge1 = this->GetThisEdge(T, currEdges[2 * j].x, currEdges[2 * j].y_min, currEdges[2 * j].y_max); //獲取當(dāng)前邊的指針,修改x值,保存修改 curr_edge1->x += curr_edge1->deltax; Edge *curr_edge2 = this->GetThisEdge(T, currEdges[2 * j + 1].x, currEdges[2 * j + 1].y_min, currEdges[2 * j + 1].y_max); curr_edge2->x += curr_edge2->deltax; //line((int)currEdges[2 * j].x, curr_gy, (int)currEdges[2 * j + 1].x, curr_gy); //在兩條直線之間劃線 //currEdges[2 * j].x += currEdges[2 * j].deltax; //currEdges[2 * j + 1].x += currEdges[2 * j + 1].deltax; //更新x 的坐標(biāo)值 } //////////測(cè)試模擬輸出劃線/////////////// /*cout << "------------------------------------------" << endl; cout << "curr_y = " << curr_y << endl; cout << "當(dāng)前掃描的邊的個(gè)數(shù) = " << curr_edge_num << endl; for (int i = 0; i < curr_edge_num / 2; ++i) { cout << "draw line bwtwen :" << endl; cout << "直線1 x = " << currEdges[2 * i].x << " ymin = " << currEdges[2 * i].y_min << " ymax = " << currEdges[2 * i].y_max << endl; cout << "直線2 x = " << currEdges[2 * i + 1].x << " ymin = " << currEdges[2 * i + 1].y_min << " ymax = " << currEdges[2 * i + 1].y_max << endl; }*/ //////////////////////////////////// //在1,2 3,4 ... 邊之間劃線 //TODO 坐標(biāo)轉(zhuǎn)換以及劃線 } ///////測(cè)試區(qū)///////////////// //cout << "-------------------------------------" << endl; //cout << "當(dāng)前取出的邊。。。。。。。。。。" << endl; //cout << "curr_edge_num = " << curr_edge_num << endl; //for (int i = 0; i < curr_edge_num; ++i) { // cout << "x = " << currEdges[i].x << " y_min = " << currEdges[i].y_min << " y_max = " << currEdges[i].y_max << endl; //} //////////////////////////////// } //返回某個(gè)邊的指針 //可通過(guò)此指針修改原結(jié)構(gòu)體中邊的x的值 Edge* GetThisEdge(ET T, double x, int y_min, int y_max) { TableItem *p = T.itemHeader; while (p != NULL) { Edge *q = p->firstNode; while (q != NULL) { if ((q->x == x) && (q->y_max == y_max) && (q->y_min == y_min)) { return q; } q = q->next; } p = p->next; } return NULL; } //用于坐標(biāo)轉(zhuǎn)換的函數(shù) double graphx(double x) { return x * 10 + 100; } double realx(double gx) { return (gx - 100)*1.0 / 10; } int graphy(int y) { return 400 - y * 10; } int realy(int gy) { return (400 - gy) / 10; } //繪制坐標(biāo)系 void DrawCoordinate(int edges[], int edge_num) { line(100, 100, 100, 400); line(100, 400, 400, 400); outtextxy(85, 95, "y↑"); outtextxy(400, 393, "→x"); for (int i = 0; i < 30; ++i) { if (i % 2 != 0) continue; //TODO 字符轉(zhuǎn)換 outtextxy(i * 10 + 100, 390, "|"); char *text = (char*)malloc(sizeof(char) * 10); itoa(i,text,10); outtextxy(i * 10 + 100, 410, text); free(text); } for (int j = 0; j < 30; ++j) { if (j % 2 != 0) continue; outtextxy(100, 400 - j * 10, "_"); char *str = (char*)malloc(sizeof(char)*10); itoa(j,str,10); outtextxy(100, 400 - j * 10,str); free(str); } //繪制原多邊形 for (int k = 0; k < edge_num; ++k) { setcolor(YELLOW); int x1 = 0, x2 = 0, y1 = 0, y2 = 0; x1 = edges[2 * k] * 10 + 100; y1 = 400 - edges[2 * k + 1] * 10; x2 = edges[2 * (k + 1)] * 10 + 100; y2 = 400 - edges[2 * (k + 1) + 1] * 10; line(x1, y1, x2, y2); } } //獲取當(dāng)前的涉及的掃描線的邊 //即取出當(dāng)前ymin 小于curr_y的邊 //通過(guò)參數(shù)返回取出的邊的個(gè)數(shù) Edge* GetCurrEdges(ET T, int curr_y, int &edge_num) { Edge *currEdges = (Edge*)malloc(sizeof(Edge) * 20); //分配最大容量 int i = 0; TableItem *p = T.itemHeader; while (p != NULL) { Edge *q = p->firstNode; while (q != NULL) { if (q->y_min <= curr_y) { //等于號(hào)很重要,否則會(huì)在圖形中出現(xiàn)空白區(qū) currEdges[i++] = *q; //將當(dāng)前邊的值取出(不改變?cè)顒?dòng)表) } q = q->next; } p = p->next; } edge_num = i; //保存取出的邊的個(gè)數(shù) return currEdges; } //判斷edge1 是否在edge2 的右邊的方法 bool IsRightTo(Edge edge1, Edge edge2) { if (edge1.x > edge2.x) //如果edge1最低點(diǎn)的x坐標(biāo)小于edge2的最低點(diǎn)的x的坐標(biāo),則edge1在edge2的右邊 return true; else { if (edge1.x < edge2.x) return false; double x_max1 = (edge1.y_max - (edge1.y_min - 1.0 / edge1.deltax*edge1.x))*edge1.deltax; double x_max2 = (edge2.y_max - (edge2.y_min - 1.0 / edge2.deltax*edge2.x))*edge2.deltax; if (x_max1 > x_max2) return true; } return false; } }; int main() { //TODO 測(cè)試活動(dòng)邊表初始化 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); //初始化活動(dòng)邊表 initgraph(800, 800, SHOWCONSOLE); solution.DrawCoordinate(edges, 6); solution.Draw(T); getchar(); closegraph(); return 0; }
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)交換排序算法(冒泡,快速排序)的示例代碼
這篇文章主要為大家詳細(xì)介紹了如何利用C語(yǔ)言實(shí)現(xiàn)交換排序算法(冒泡排序、快速排序),文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2022-07-07C++利用代理模式實(shí)現(xiàn)遠(yuǎn)程代理,虛擬代理和保護(hù)代理
今天給大家簡(jiǎn)單介紹代理模式,一個(gè)很簡(jiǎn)單的設(shè)計(jì)模式,旨在不改變?cè)瓕?duì)象的情況下通過(guò)代理對(duì)象來(lái)控制對(duì)原對(duì)象的訪問(wèn)。代理模式根據(jù)具體情況還可以分為遠(yuǎn)程代理、虛擬代理、保護(hù)代理等,下面來(lái)介紹一下2023-04-04c++連接mysql數(shù)據(jù)庫(kù)的兩種方法(ADO連接和mysql api連接)
現(xiàn)在正做一個(gè)接口,通過(guò)不同的連接字符串操作不同的數(shù)據(jù)庫(kù)。要用到mysql數(shù)據(jù)庫(kù),C++連接mysql有2種方法:利用ADO連接、利用mysql自己的api函數(shù)進(jìn)行連接,下面看看如何用吧2013-12-12IOS開發(fā)之UIScrollView實(shí)現(xiàn)圖片輪播器的無(wú)限滾動(dòng)
這篇文章主要介紹了IOS開發(fā)之UIScrollView實(shí)現(xiàn)圖片輪播器的無(wú)限滾動(dòng)的相關(guān)資料,需要的朋友可以參考下2017-07-07C++智能指針shared_ptr與weak_ptr的實(shí)現(xiàn)分析
shared_ptr是一個(gè)標(biāo)準(zhǔn)的共享所有權(quán)的智能指針,允許多個(gè)指針指向同一個(gè)對(duì)象,定義在 memory 文件中,命名空間為 std,這篇文章主要介紹了C++ 中 shared_ptr weak_ptr,需要的朋友可以參考下2022-09-09