博文
C#实现基于三角网的等值线追踪及填充算法
|||
Captain Dialog 2010-03
1引言介绍
等值线是一种离散数据的图形表示方法，在水利、土木、地质、石油勘探等工程和技术领域内广泛的应用。常规的等值线绘制通常采用网格法，其绘制的步骤一般为：离散数据网格化；等值点的计算；等值线的追踪；光滑和标记等值线等。等值线图的显示方式一般有两种：(1)等值线显示，即采用线条上加注数值标记的方式显示数据，这种方式的特点是简捷；(2)采用彩色填充的方法来显示数据，既用不同的颜色来显示不同的数据，这种方法的特点是比较直观。两种方法的计算机实现也各不相同，一般来说，它们都需要将数据进行要用到的网格网格化。第一种方法必须进行等值线的追踪、光滑和标记等值线。而第二种方法可以在追踪出等值线的基础上进行，也可以不做等值线的追踪直接在网格数据上进行操作。
方法实现的难易程度各不相同。
本文参考了文献【1】填充等值线的方法原理，并针对文中的寻找出来用于填充的多边形不是最小多边形进行改进。基于计算机图形学的基于“左转算法”的多边形自动搜索方法可以有效的识别最简单多边形，并结合方位角计算排除重复的多边形。借此提高了填充的效率。并且，结合计算机绘图的原理，本文还在填充的基础上，实现了等值线的追踪，相对经典的等值线追踪算法，此法更加简单，易于编程。
针对非规则数据（即散乱点数据），本文同样提出了构造等值线的方法，首先采用计算机图形学中的二维。。。生成非规则的三角形网格，然后针对每个三角形使用类似规则矩形的处理方式，可顺利解决不规则等值线的绘制问题。
2散乱点数据的三角网生成
针对不规则形状的等值面，需要对特殊情况进行边界的处理，用规则网格情况下，经常进行等值线的边界进行先扩充再裁剪等方式，结果使得等值面的边界为锯齿状边界；然后利用三角形来构造边界，则会使得边界区域光滑，从而消除锯齿的产生。因此，在处理由散乱点数据构成的不规则等值面时，需要首先对所有的数据点进行三角网的生成，用三角网来构建等值面。
3设计的技术细节关键点
1、等值线的标注：
标注的数值通常写在曲线比较平坦的部分，方法如下：
(1)寻找标注位置。为寻找曲线比较平坦的部分，依次找出3点，计算3点间两线段的夹角，若夹角大于120~，则认为该处适合标注。
(2)调整等值点顺序。要求标注的数值写至等值线中间时，需断开原等值线。若原等值线是非闭合曲线，则被分成两段，原来的等值线起始点和终止点不变，但在切断处增加一个新的终止点和一个新的起始点；若原等值线是闭合曲线，则可当作非闭合曲线处理，把起始点和终止点位置调整到切断的位置。
2、等值线的追踪：
从图形角度分析，可利用当前点的颜色值，确定出一条等值线。
3、等值线的光滑处理：
三次B样条函数处理插值处理
等值线的计算
判断格网的一条边是否与雨量值为 的等高线相交，要看这条边的两个端点的雨量值是否“含有”这个 值，例如点A、B是某个三角网的两个顶点，其雨量值分别为 及 ，则边AB是否与雨量值为 的等高线相交，应判断不等式( 一 )(He一 )≤ 0是否满足，就可以知道边AB是否与等高线相交。以往的此类算法为J 编程的简单，对于W= 或 ：He的情况，
采用将雨量值增加微小值的方法，对于此类情况作了专门处理，不需要改动雨量值而是直接追踪，使生成的雨量线更为准确。如图1，穿过点A的雨量线可以看成如虚线的雨量线来处理，只是点F和点G“退化”到了点A，这样追踪时就要经过边AB、边AE，相当于绕着顶点“转”到了边DE。
判断一条边AB是否与等值线W相交的依据为：
升级处理：计算机中，除法容易导致崩溃，因此采用乘法处理：
4、以颜色表为等值线值
5、程序实现
应该用类似于计算机图形学的东西来实现，并且针对三角网等图元，采用面向对象的思路，使得每个图形元素的属性值可以得到灵活的操作性。
“点---线---三角形”
相同属性的点构成线；
相同属性的线封闭构成块；
点又可分为普通的数据点（控制点）、等值点（用于构成等值线）。
线于是也可分成边界控制线（由普通电构成）和等值线（由等值点构成）。
功能设计：
点：Cmou_Point
ID号？
坐标属性（x，y）、具体的属性值（V）
所属的线号（list_ID_Line）？
点的类型（原始数据点，等值点）
Note：在设计过程中，为了保证数据的完整性，基于点构造出来的段、线、三角形等包含的点信息，一律采用点的ID号表示，这样，针对点的修改就可以很容易实现，修改一处，用到该点的其他地方就不用重复修改了。同样，线号、段号都是这个用处！
段：Cmou_Segment
ID号
包含的起点和终点StartPoint、EndPoint
所属的线号(list_ID_Line)
所属的三角形编号（list_ID_Triangle）
段的类型（想对于三角形来说：普通边、等值边，即含有等值点的边）
线：Cmou_Line
ID号（ID）
线的类型（三角形边线，等值线，）
包含的数据点集（list_Point）
线所属的三角形ID号(list_ID_Triangle)
三角形：Cmou_Triangle
ID号
//三角形包含的边线（list_Line）
三角形包含的线段:（Cmou_Segment类型）Edge0、Edge1、Edge2
利用线段构成了三角形è在三角形边上找到等值点后，三角形需要细分为多个三角形？
点集：list_Point_Scatter 原始的散乱点数据集
List_Point 所有用来生成三角形网格的数据点（包括原始数据点和新增的等值点）
三角形的等值线追踪时，可以通过三角形边线上的ID_Triangle追踪到与之相邻的三角形（两个相邻的三角形共边）
等值线？？Cmou_ContourLine
ID编号
关于三角形的追踪，可以构造出一条条的Cmou_Line，然后绘制显示即可。
//关于三角形的填充，可以最后根据三角形所含的数据点的V值，构造出人意形状的多边形，//然后按照等值线的数值进行填充。
关于等值线的填充，完全可以按照等值线的值的大小排列，由两条等值线构成多边形，然后再用对应的颜色填充。
多边形：Cmou_Polygon
ID
List_Point 包含的点集
Vstart、Vend属性值信息
等值线追踪算法描述：
(1)非闭合等值线对应等值边系列的搜索。
① 以某等值线的数值为依据，先在边界边上找到一条等值边作为起始边，若找不到这样的起始边，则说明该等值线闭合，执行(2)。将该边记录到等值边系列后，从待搜索边系列中剔除。
② 在起始边相关三角形的相关边上寻找第二条等值边，找到后加入等值边系列，并将其从待搜索边系列中剔除。
③从待搜索三角形系列中剔除等值线已经过的三角形，则最新找到的等值边只有一个相关三角形，在该三角形内搜索下一条等值边，找到后加入等值边系列，并将其从待搜索边系列中剔除。
④递归执行③ ，直到找到的最后一条等值边是边界边。
⑤ 一条非闭合等值线的等值边系列搜索完毕。
(2)闭合等值线对应等值边系列的搜索。
① 任找一条等值边作为起始边，若找不到这样的起始边，则说明分析不出该等值线，应退出该等值线的分析而开始另一条等值线的搜索。将该边记录到等值边系列，并在该边上作一标志。
②在起始边的一个相关三角形中寻找第二条等值边，找到后加入等值边系列，并将其从待搜索边系列中剔除。
③从待搜索三角形系列中剔除等值线已经过的三角形，则最新找到的等值边只有一个相关三角形，在该三角形内搜索下一条等值边，找到后加入等值边系列，并将其从待搜索边系列中剔除。
④递归执行③ ，直到找到最后一条等值边是起始边。
⑤一条闭合等值线的等值边系列搜索完毕。
(3)循环执行(1)、(2)直到找到所有等值线对应的等值边系列。用线性插值的方法求等值边上对应等值点的坐标。将这些等值点有序地连起来即实现了等值线的自动分析。
等值线追踪相关【3】：
对每条等值线值 ，等值线的游走可按如下3个步骤进行。
(1)搜索存在等值点的所有三角形：首先在三角剖分后得到的三角形链表中进行搜索，找出所有存在等值点的三角形，并将此三角形添加到一个临时建立的三角形链表中供以后使用(此链表记为TriCheckedAngleList)。
(2)搜索开曲线等值线：从凸边三角形链表(TriChimbAngleList)中搜索等值点存在的三角形，找出等值线的起始点，记下点的位置和点所在的边(即两个三角形的公共边)。然后以此公共边在TfiCheckedAngleList链表中寻找包含此边的新三角形，找到后，在新三角形中进行等值点的判断和计算，记录等值点和新的公共边，并以新公共边按上述方法继续在TriCheckedAngleList链表中游走，直至找不到包含新公共边的三角形为止。需要注意的
是在游走过程中，必须将每次找到的新三角形从TfiChecke3dAngleList中删除，否则等值点会出现重复。按此方法进行等值线游走后，就得到了两端经过三角形网格边界的开曲线等值线。
(3)搜索闭合等值线：完成开曲线等值线搜索后，在剩下的TriCheckedAngleList链表的三角形中取第一个三角形，在其边上找出等值点后，按步骤(2)同样的方法进行等值线游走，直到TriCheekedAngleList链表的三角形为空，这样就可搜索出 值的所有闭合等值线。
Note：关键在于如何处理三角形中搜索等值边的递归关系。
参考文献:
[1] 庞世明,蔡玉华,靳文芳. 等值线图的彩色填充方法.计算机应用. 2004.1 Vol.24,NO.1, 60~62.
[2] 李顺新,刘 俊,陈建勋等. 利用不规则三角网法绘制三峡雨量等值线图. 2005.4,Vol.36,No.4, 44~46.
[3] 赵 伟,赵卓宁,李五生. 一种有效的离散数据场等值线生成方法. 成都信息工程学院学报.2007.2,Vol.22,NO.1 115~121.
2010-2-10 等值线的追踪工作基本完成
2010-2-11 关于等值线的填充：
需要制定基于单个三角形的填充，将所有的数据点（包括原始的散乱点、等值点、以及将要添加进去的圆滑插值点）进行任意形状的填充。
由此，形成有三套数据点集。每个三角形进行填充的时候都是需要查询这些点集，找出自己的点，然后根据点的属性值构造出任意多边形，再进行填充。
终于找到错误的原因了！！！
初步确定问题为三角形中的等值点没有连续。如：上面的44号三角形（102-106-107）中顶点和等值点是：
93.877， 94.812，94.812，96.260，98.675 （除了红色为等值点，剩下的为顶点）
而控制它们的等值线值为：
91.682，94.812，97.943
于是，最后的一个点98.675成了孤立点，不能参与到三角形的填充搜索中。
解决办法：仔细调试后，发现问题应该是出在等值线的追踪过程中。因此，修改了追踪算法中的一个条件，使得在一般情况下，不会出现上述问题。
但是，上面的那种情况没有做处理，只是认为正常的等值线追踪情况下，不可能出现那样的等值点不连续的情况。
关于等值线值相应的颜色填充
相应的颜色填充，可根据前面等值线填充中的判断等值点的值属于受哪个等值线值控制，取对应的颜色。下标范围是 [ 最小，最大 )
下一步工作：
1、 等值线的光滑
2、 等值线的标注
3、 等值线的颜色改进
4、 任意形状处理
2010-2-23 改进之增加颜色选择按钮
修改等值线颜色
修改等值线值的字体颜色
修改等值线的背景颜色（在等值线填充的情况下无效）
增加了图片保存功能
https://blog.sciencenet.cn/blog-244606-303491.html
上一篇：MouStudio技术储备之---C#进度条模态窗体
下一篇：MouStudio技术储备之---C#使用Firebird嵌入版数据库
