图形学课程设计四叉树

1、基于四叉树的颜色填充等值线图绘制计算机图形学课程设计报告XXX7/6/2014Table of Contents1问题的提出11.1问题重述11.2实现目标12程序主构架12.1全局变量12.2类12.3程序流程图23算法原理43.1基于四叉树的颜色填充4算法基本思想4算法流程图43.2绘制等值线54主要部分实现及说明54.1Color54.2Rect64.3读取网格数据值84.4求最大最小值94.5建立填充颜色表94.6四叉树颜色填充104.7绘制等值线125成果截图126小结131 问题的提出1.1 问题重述等值线是一组值相等的序列连线组成的图形。等值线图在实际中应用广泛，如等高线图、等气

2、压图等等。基于四叉树的颜色填充等值线图绘制方法可利用计算机将按照固定间距采样的网格数据绘制成等值线图。1.2 实现目标读入按照固定间距采样的等值线绘制数据，利用四叉树思想进行颜色填充，之后进行等值线扫描、绘制坐标系、色码标识，形成一幅等值线图。2 程序主构架2.1 全局变量vector colorTable;/填充颜色表vectorvector bitmap;/数据文件vectorvector data;/网格数据int Zmax;/网格最大值int Zmin;/网格最小值int Gmin;/图标最小值int N;/等值线差值int dc;/等值线间距int scale = 20;/采样点间距

3、int isoline = -1;/边界线填充数值int def = -2;/bitmap默认数值static int count = 0;/测试用统计int row;/原始数据行数int col;/原始数据列数2.2 类Tricoder类：表示平面上一个点的坐标。图 1：Tricoder类UML类图Color类：用于表示颜色。图 2：Color类UML类图Rect类：表示一个矩形。c0, c1, c2, c3分别表示矩形左上、右上、左下、右下四个顶点的颜色值；StarX, startY表示矩形左上顶点的x, y坐标；endX, endY表示矩形右下顶点的x, y坐标；colorIndex(d

4、ouble n)计算矩形颜色均值的级数；isConstant()判定矩形内颜色值是否相等；isSole()判定矩形大小是否为1像素。图 3：Rect类UML类图2.3 程序流程图程序流程图如下图所示：图 4：程序流程图3 算法原理3.1 基于四叉树的颜色填充3.1.1 算法基本思想将网格中相邻的四个结点视为一个矩形，如果这四个结点的颜色值相等，则用该颜色值填充该矩形。如果不相等，则将此矩形等分为四个小矩形，并用差值的方法计算每个小网格的颜色值，（如图 5所示）递归直至条件满足或者矩形大小小于1像素。图 5：四叉树颜色填充示例3.1.2 算法流程图图 6：四叉树颜色填充算法流程图3.2 绘制等值

5、线对于如图 7所示的四联通域，若满足：f=c1+c2+c3+c4-4cc=0则点cc是等值线的边界线，都则点cc不是等值线的边界线。图 7：四联通域4 主要部分实现及说明4.1 Color#ifndef COLOR_H#define COLOR_H#include using namespace std;class Colorpublic:int red;/红色分量int green;/绿色分量int blue;/蓝色分量Color(int r, int g, int b)/构造函数red = r;green = g;blue = b;Color()void set(int r, int g,

6、 int b)red = r;green = g;blue = b;void show()/显示颜色（测试用）coutred|green|bluet;bool operator=(const Color &t)constif(red = t.red) & (green = t.green) & (blue = t.blue)return true;else return false; Color & operator=(const Color &t)red = t.red;blue = t.blue;green = t.green;return *this; ;#endif4.2 Rect/c

7、0-c1/| |/c2-c3#ifndef RECT_H#define RECT_Hextern int N;/等值线差值extern int Gmin;/图标最小值class Rectpublic:int c0;/左上角数据int c1;/右上角数据int c2;/左下角数据int c3;/右下角数据int startX;/起始横坐标int startY;/起始纵坐标int endX;/结束横坐标int endY;/结束纵坐标Rect()Rect(int cc0, int cc1, int cc2, int cc3, int sx, int sy, int ex, int ey)c0 = c

8、c0;c1 = cc1;c2 = cc2;c3 = cc3;startX = sx;startY = sy;endX = ex;endY = ey;/求颜色索引值int colorIndex(double n)int ic;ic = (int)(n-Gmin)/N;return ic;bool isConstant()/判断矩形内颜色是否相等int cc0 = colorIndex(c0);int cc1 = colorIndex(c1);int cc2 = colorIndex(c2);int cc3 = colorIndex(c3);if(cc0 = cc1 = cc2 = cc3)ret

9、urn true;elsereturn false;bool isSole()/判断举行大小是否为1像素if (endX - startX = 1) | (endY - startY = 1)return true;return false;#endif4.3 读取网格数据值/读取数据文件，并将数据存入data中void getData(string filename)ifstream OpenFile(filename);string s, sub;int pos1 = 0, pos2 = 0, i = 0;const char* p;while(!OpenFile.eof()getline

10、(OpenFile, s);vector temp;pos1 = 0;for(i = 0; i s.length(); i+)/划分行if(si = )|(i = s.length()-1)pos2 = i;sub = s.substr(pos1, pos2);p = sub.c_str();int num = atoi(p);temp.push_back(num);pos1 = i+1;data.push_back(temp);4.4 求最大最小值void getScope()Zmax = Zmin = data00;for(int i = 0; i data.size(); i+)for(

11、int j = 0; j datai.size(); j+)if(dataij Zmax)Zmax = dataij;4.5 建立填充颜色表参数：Color max 最大值颜色；Color min最小值颜色；int n颜色表的级数。颜色表的颜色应当是从最大值到最小值逐渐渐变的，渐变既是对于没级颜色的RGB值差值相等。在本函数中，先求出了每种颜色分量在每级颜色变化的渐变差值，然后循环计算出每级颜色。void getColorTable(Color max, Color min, int n)double deltaR = (double)(max.red - min.red)/n;/红色渐变差值

12、double deltaG = (double)(max.green - min.green)/n;/绿色渐变差值double deltaB = (double)(max.blue - min.blue)/n;/蓝色渐变差值double r = min.red, g = min.green, b = min.blue;colorTable.push_back(min);for(int i = 1; in; i+)r += deltaR;g += deltaG;b += deltaB;Color temp;temp.set(int(r), int(g), int(b);colorTable.pu

13、sh_back(temp);colorTable.push_back(max);4.6 四叉树颜色填充在主函数中，循环遍历网格数据矩阵，建立Rect对象，调用四叉树填充函数：/循环遍历data，填充颜色for(int i=0; idata.size()-1; i+)for(int j=0; jdatai.size()-1; j+)int c0 = dataij;/左上角int c1 = datai+1j;/右上角int c2 = dataij+1;/左下角int c3 = datai+1j+1;/右下角Rect Rij (c0, c1, c3, c3, i*scale, j*scale, (i

14、+1)*scale, (j+1)*scale);qtf(Rij);四叉树颜色填充函数：void qtf(Rect ij)/退出条件：当所判定的举行颜色一致或大小为1像素时if(ij.isConstant() = true | ij.isSole() = true)fillColor(ij);return;/否则，将矩形细分成四个小矩形elseRect r0(ij.c0, (ij.c0 + ij.c1)/2, (ij.c0 + ij.c2)/2, (ij.c0 + ij.c1 + ij.c2 + ij.c3)/4,ij.startX, ij.startY, (ij.startX + ij.end

15、X)/2, (ij.startY + ij.endY)/2);qtf(r0);Rect r1(ij.c0 + ij.c1)/2, ij.c1, (ij.c0 + ij.c1 + ij.c2 + ij.c3)/4, (ij.c1 + ij.c3)/2,(ij.startX + ij.endX)/2, ij.startY, ij.endX, (ij.startY + ij.endY)/2);qtf(r1);Rect r2(ij.c0 + ij.c2)/2, (ij.c0 + ij.c1 + ij.c2 + ij.c3)/4, ij.c2, (ij.c2 + ij.c3)/2, ij.startX,

16、 (ij.startY + ij.endY)/2, (ij.startX + ij.endX)/2, ij.endY);qtf(r2);Rect r3(ij.c0 + ij.c1 + ij.c2 + ij.c3)/4, (ij.c1 + ij.c3)/2, (ij.c2 + ij.c3)/2, ij.c3,(ij.startX + ij.endX)/2, (ij.startY + ij.endY)/2, ij.endX, ij.endY);qtf(r3);上述函数中调用的颜色填充函数，计算本矩形所应填充的颜色，在本矩形内填充颜色/填充颜色void fillColor(Rect & qd)/co

17、unt+;double x = (double)(qd.c0 + qd.c1 + qd.c2 + qd.c3) / 4;/x为区域颜色的平均值int c = qd.colorIndex(x);/c为填充颜色的等级for(int i = qd.startX; i qd.endX; i+)for(int j = qd.startY; j qd.endY; j+)bitmapij = c;4.7 绘制等值线利用边缘检测搜索等值线，其中Tricoder类记录一个点的横纵坐标，参数int iso为在bitmap中表示等值线的数值。本函数先对所有点逐一检测，发现边界点则存入一临时向量中，之后再根据临时向量中所记录的信息改写bitmap中边界点的数值。/绘制等值线void isoLine(int iso)int cl;vector isl;/边界点/查询边界点for(int m = 1; m bitmap.size()-1; m+)for(int n = 1; n bitmapm.size()-1; n+)cl = bitma