论文部分内容阅读
文章编号1000-5269（2018）06-0083-04DOI：10.15958j.cnki.gdxbzrb.2018.06.14
摘要：在等值線、等值面生成及填色的的绘制过程中，合理有效地处理等值线、等值面以及判断等值面的包含关系是需要解决的关键技术问题。其处理的好坏直接影响等值线、等值面绘制的完整性以及效率。针对等值线和等值面的生成、绘制、排序、填色各个步骤的方法进行分析，在已有算法上进行优化改进，提高了结果的准确性。同时提出了根据周围边框交点判断等值面包含关系的方式，确保在不牺牲太多效率的前提下，绘制准确完整的等值面图片。
关键词：等值线;等值面;包含关系;填色;Delaunay三角网格
中图分类号：TP391文献标识码：A
等值线研究对于科学计算可视化而言是十分重要的。由于等值线图（如降雨量，犯罪率等）看起来相当形象、直观，因此它在地理信息产业中有着广泛的应用。等值线的绘制算法主要包括建立网格，寻找等值线以及平滑等值线。由于三角网格具有高精度、高效率和易处理等优点，因此受到普遍的认可。在三角网格中，Delaunay三角网格形态良好，同时在表达形态方面表现较为出色，因此被广泛使用于寻找等值线中[1]。如何快速高效地构建Delaunay三角网格，一直是研究关注的重点。目前已有不少成熟的算法，包括分割—合并算法[2]、逐点插入算法[3-5]以及三角网生长法[6-8]等等。其中目前较少采用的三角网生长算法效率较低;而逐点插入算法易于实现，占用内存小，但是时间复杂度高;分割—合并算法则最为高效，但是实现起来相对复杂[1]。而本文主要介绍的是一种快速、实现起来相对简单的三角网格构建算法（QGDTN），同时结合边界点位顺序判断等值面包含关系来进行等值面的绘制和填色。
1创建Delaunay三角网格
本算法的基本思路是向三角网中不断添加新的三角形，然后在三角网格构建完全之后，利用LOP法则来优化三角网格。使得三角网格满足Delaunay三角网格的要求。和原先的QGDTN算法相比，将LOP优化步骤移动到网格生成之后来数次进行，在复杂的、点集中存在较多经度相同或相似点的情况下，确保了生成结果的正确性。
实现步骤：
a）用快速排序法，将点集中的点，按照从上到下，从左到右的顺序排序。
b）选择最左边的三个点——A，B，C，构建第一个三角形（如果A，B，C在同一条直线上，则选择第四个点，以此类推），然后把这个三角形当作最初的凸包，按照逆时针顺序存入凸包的数组中。
c）从排序后的点集中选取第一个未被选取的点，和凸包集合中所有的点连接，创建n条线段存入新建线段集合L。
d）去除新建线段集合L中和凸包的边有交点的线段，利用剩余线段和凸包集合中的边构建新的三角形，加入三角网格集合T中。
e）把剩下的线段按照斜率排序，把斜率最大和最小的两条线段增加如凸包集合，并且从凸包集合中去除夹在这两条线段中间的线段。
f）循环步骤c）到e），直到点集中没有剩余的点。
g）重复利用LOP法则（两个三角形ABC和ABD，共用边AB，如果C在三角形ABD的外接圆中或者D在三角形ABC的外接圆中，则用CD取代原来的对角线AB，构建成两个新的三角形ACD和BCD），直到三角网格没法再被LOP法则优化（如图1所示）。
以图5为例的实现步骤：
a）逆时针顺序寻找非闭合曲线和边界的交点A，B，C，D，E，F，G和H。并把交点按顺序存入数组中。同时链接属于同一条等值线的两个交点，排序链接后的效果如图6所示，如果没有交点，说明所有边界上的点都属于一个等值区间，利用边界创建一个shape并根据边界点的值选择颜色，存入shape队列中。
b）寻找与第一个点属于相同等值线的交点，如（A，D）。然后利用点A，D所属的等值线以及A，D之间的外边界点生成shape放入shape队列中。同时根据等值线的值以及两个端点左右两边相邻的端点的值，判断该shape中所应该填入的颜色。
c）如果b）步骤中创建的shape是shape队列中第一个shape利用之前找到的两个点和之前创建shape没用到边界的点创建第二个shape，同时根据第一个shape的颜色（同一条等值线两边属于相邻的两种颜色），选取这个shape所应该填充的颜色。并把这个shape存入shape队列。
d）把创建shape所使用的交点从交点集中移除。
e）重复步骤b）直到交点集中没有任何点。
f）利用闭合曲线创建shape，存入临时shape集S。
g）查找闭合曲线创建的shape，如果该shape不被任何临时shape集S中其他的shape包含。就把该shape存入shape队列中。根据在该shape中的点且不被其他shape包含的点来判断该shape所应该填充的颜色。
h）把该shape从临时shape集S中移除。
i）重复步骤f）到h）直到临时shape集S中没有一个shape剩余。
j）按顺序填充shape（结果如图7所示）。
5结语
本文改进了原有的QGDTN算法，于原有的算法相比，略微增大了时间复杂度，但确保了结果的唯一性和正确性，同时并没有增加代码的实现难度。之后利用Bezier曲线方程式平滑了曲线。在等值面填色方面，通过边界的点位顺序判断，找出等值线面的包含关系，进行排序和填色，确保不会缺漏填色，同时也可以为后续的判断提供相应的依据。
参考文献：
[1]蒋瑜，杜斌，卢军，王鹏.基于Delaunay三角网的等值线绘制算法[J].计算机应用研究，2010，27（1）：101-103.
[2]胡金星，潘懋，马照亭，等.高效构建Delaunay三角网数字地形模型算法研究[J].北京大学学报，2003，39（5）：736-741.
[3]武晓波，王世新，肖春生.一种生成Delaunay三角网的合成算法[J].遥感学报，2000，4（1）：32-35.
[4]刘学军，符锌砂，赵建三.三角网数字地面模型快速构建算法研究[J].中国公路学报，2000，13（2）：31-36.
[5]宋占峰，蒲浩，詹振炎.快速构建Delaunay三角网算法研究[J].铁道学报，2001，23（5）：85-91.
[6]徐青，常歌，杨力.基于自适应分块的TIN三角网建立算法[J].中国图象图形学报，2000，5（6）：461-465.
[7]刘永和，王燕平，齐永安.一种快速生成平面Delaunay三角网的横向扩张法[J].地球信息科学，2008，10（1）：20-25.
[8]何俊，戴浩，谢永强等.一种改进的快速Delaunay三角剖分算法[J].系统仿真学报，2006，18（11）：3055-3057.
（责任编辑：曾晶）
摘要：在等值線、等值面生成及填色的的绘制过程中，合理有效地处理等值线、等值面以及判断等值面的包含关系是需要解决的关键技术问题。其处理的好坏直接影响等值线、等值面绘制的完整性以及效率。针对等值线和等值面的生成、绘制、排序、填色各个步骤的方法进行分析，在已有算法上进行优化改进，提高了结果的准确性。同时提出了根据周围边框交点判断等值面包含关系的方式，确保在不牺牲太多效率的前提下，绘制准确完整的等值面图片。
关键词：等值线;等值面;包含关系;填色;Delaunay三角网格
中图分类号：TP391文献标识码：A
等值线研究对于科学计算可视化而言是十分重要的。由于等值线图（如降雨量，犯罪率等）看起来相当形象、直观，因此它在地理信息产业中有着广泛的应用。等值线的绘制算法主要包括建立网格，寻找等值线以及平滑等值线。由于三角网格具有高精度、高效率和易处理等优点，因此受到普遍的认可。在三角网格中，Delaunay三角网格形态良好，同时在表达形态方面表现较为出色，因此被广泛使用于寻找等值线中[1]。如何快速高效地构建Delaunay三角网格，一直是研究关注的重点。目前已有不少成熟的算法，包括分割—合并算法[2]、逐点插入算法[3-5]以及三角网生长法[6-8]等等。其中目前较少采用的三角网生长算法效率较低;而逐点插入算法易于实现，占用内存小，但是时间复杂度高;分割—合并算法则最为高效，但是实现起来相对复杂[1]。而本文主要介绍的是一种快速、实现起来相对简单的三角网格构建算法（QGDTN），同时结合边界点位顺序判断等值面包含关系来进行等值面的绘制和填色。
1创建Delaunay三角网格
本算法的基本思路是向三角网中不断添加新的三角形，然后在三角网格构建完全之后，利用LOP法则来优化三角网格。使得三角网格满足Delaunay三角网格的要求。和原先的QGDTN算法相比，将LOP优化步骤移动到网格生成之后来数次进行，在复杂的、点集中存在较多经度相同或相似点的情况下，确保了生成结果的正确性。
实现步骤：
a）用快速排序法，将点集中的点，按照从上到下，从左到右的顺序排序。
b）选择最左边的三个点——A，B，C，构建第一个三角形（如果A，B，C在同一条直线上，则选择第四个点，以此类推），然后把这个三角形当作最初的凸包，按照逆时针顺序存入凸包的数组中。
c）从排序后的点集中选取第一个未被选取的点，和凸包集合中所有的点连接，创建n条线段存入新建线段集合L。
d）去除新建线段集合L中和凸包的边有交点的线段，利用剩余线段和凸包集合中的边构建新的三角形，加入三角网格集合T中。
e）把剩下的线段按照斜率排序，把斜率最大和最小的两条线段增加如凸包集合，并且从凸包集合中去除夹在这两条线段中间的线段。
f）循环步骤c）到e），直到点集中没有剩余的点。
g）重复利用LOP法则（两个三角形ABC和ABD，共用边AB，如果C在三角形ABD的外接圆中或者D在三角形ABC的外接圆中，则用CD取代原来的对角线AB，构建成两个新的三角形ACD和BCD），直到三角网格没法再被LOP法则优化（如图1所示）。
以图5为例的实现步骤：
a）逆时针顺序寻找非闭合曲线和边界的交点A，B，C，D，E，F，G和H。并把交点按顺序存入数组中。同时链接属于同一条等值线的两个交点，排序链接后的效果如图6所示，如果没有交点，说明所有边界上的点都属于一个等值区间，利用边界创建一个shape并根据边界点的值选择颜色，存入shape队列中。
b）寻找与第一个点属于相同等值线的交点，如（A，D）。然后利用点A，D所属的等值线以及A，D之间的外边界点生成shape放入shape队列中。同时根据等值线的值以及两个端点左右两边相邻的端点的值，判断该shape中所应该填入的颜色。
c）如果b）步骤中创建的shape是shape队列中第一个shape利用之前找到的两个点和之前创建shape没用到边界的点创建第二个shape，同时根据第一个shape的颜色（同一条等值线两边属于相邻的两种颜色），选取这个shape所应该填充的颜色。并把这个shape存入shape队列。
d）把创建shape所使用的交点从交点集中移除。
e）重复步骤b）直到交点集中没有任何点。
f）利用闭合曲线创建shape，存入临时shape集S。
g）查找闭合曲线创建的shape，如果该shape不被任何临时shape集S中其他的shape包含。就把该shape存入shape队列中。根据在该shape中的点且不被其他shape包含的点来判断该shape所应该填充的颜色。
h）把该shape从临时shape集S中移除。
i）重复步骤f）到h）直到临时shape集S中没有一个shape剩余。
j）按顺序填充shape（结果如图7所示）。
5结语
本文改进了原有的QGDTN算法，于原有的算法相比，略微增大了时间复杂度，但确保了结果的唯一性和正确性，同时并没有增加代码的实现难度。之后利用Bezier曲线方程式平滑了曲线。在等值面填色方面，通过边界的点位顺序判断，找出等值线面的包含关系，进行排序和填色，确保不会缺漏填色，同时也可以为后续的判断提供相应的依据。
参考文献：
[1]蒋瑜，杜斌，卢军，王鹏.基于Delaunay三角网的等值线绘制算法[J].计算机应用研究，2010，27（1）：101-103.
[2]胡金星，潘懋，马照亭，等.高效构建Delaunay三角网数字地形模型算法研究[J].北京大学学报，2003，39（5）：736-741.
[3]武晓波，王世新，肖春生.一种生成Delaunay三角网的合成算法[J].遥感学报，2000，4（1）：32-35.
[4]刘学军，符锌砂，赵建三.三角网数字地面模型快速构建算法研究[J].中国公路学报，2000，13（2）：31-36.
[5]宋占峰，蒲浩，詹振炎.快速构建Delaunay三角网算法研究[J].铁道学报，2001，23（5）：85-91.
[6]徐青，常歌，杨力.基于自适应分块的TIN三角网建立算法[J].中国图象图形学报，2000，5（6）：461-465.
[7]刘永和，王燕平，齐永安.一种快速生成平面Delaunay三角网的横向扩张法[J].地球信息科学，2008，10（1）：20-25.
[8]何俊，戴浩，谢永强等.一种改进的快速Delaunay三角剖分算法[J].系统仿真学报，2006，18（11）：3055-3057.
（责任编辑：曾晶）