二维三角网格数据结构分析
网格划分是有限元计算的前提条件，而目前有限元计算精度要求越来越高，与之相应的，网格划分的数目也越来越多。数据量剧增后，与这部分数据相关的操作就很有可能成为程序性能的瓶颈。以这款水利分析软件为例，软件需要用到二维三角网格剖分。当需要较高的计算精度时，网格的数量很可能会在十万乃至五十万以上，如果网格的数据结构设计不合理，这时候与网格相关的绘图、选取等操作就可能会非常耗时，以至于影响用户体验。http://www.njtf.cn/ueditor/net/upload/2017-05-23/6f639b85-d69d-4a89-a03b-be65c7ed20be.png下面，笔者从与网格相关的操作需求出发，以stl标准模板库中常用容器为载体，来分析网格应当具有怎样的数据结构。首先罗列stl中常用的容器及其对应的数据结构：（1）动态数组：vector。（2）链表：list。（3）红黑树：set、map。（4）哈希表/散列表：hash_map、hash_set。下文中将以容器英文名称进行叙述。1.绘图绘图需要分别绘制网格结点、网格边和网格单元。其中，网格单元有时需要以填充的方式进行绘制，以显示云图、动画等计算结果。绘图是频繁进行的一个操作，必须保证效率，因此要求网格结点、网格边和网格单元都必须能以线性时间进行遍历。vector、list、set、map、hash_map、hash_set都能保证以线性时间进行遍历，但其中数组的遍历速度最快。2.元素拾取元素拾取是用户与网格交互的基础，元素拾取主要指的是结点的拾取，根据网格的拓扑关系，网格单元和网格边的拾取都可以依赖网格结点的拾取。元素拾取一般是通过判断元素是否在一给定矩形选框中来实现的，要实现高效的拾取操作，需要将元素按某种规律（如按坐标）进行排序。set和map可以保证其中元素总是按一定规律排列，而vector则需要调用排序算法来维持其中元素的有序性。相应的，set和map因为要保持元素的有序性，所以在构建容器时速度会比无序容器慢。list因为不提供随机访问迭代器，因此排序意义不大，需要需要借助其他容器完成拾取操作。hash_map、hash_set本身无法排序，需要借助别的容器。3.元素删除和插入vector的删除和插入操作代价是十分昂贵的，因为vector中的元素都在内存中连续排序，删除和插入操作都可能影响到其他的元素，一般都需要移动所操作元素后面所有的元素，而最坏的情况下，可能插入和删除需要移动整个容器中的所有的元素。而list、set、map和hash_map的删除和插入操作都比较高效。但在删除元素前，可能需要一次查找操作，而list的查找时间复杂度是线性时间，而set和map是对数时间，hash_map、hash_set是常数时间。此外，考虑到网格的拓扑结构，元素删除还有一些附带的操作。删除网格结点时，依赖该结点的网格边和网格单元都将失效，需要一并删除。同理，删除网格边时，需要同时删除对应的网格单元。因此，在元素删除的操作中，还需要进行查找关联元素的操作。4.查找关联元素查找关联元素至少可以有三种实现方式：（1）元素中储存关联元素的编号。（2）元素中储存关联元素的指针。（3）动态的计算元素拓扑结构。储存关联元素编号需要根据编号进行一次查找操作。对于vector，如果简单的将数组下标作为元素编号，则其能提供常数时间的查找操作。但这样编号方式在元素变动时难以维护编号的有效性，所以一般采取的方式是将编号内置于元素本身。这种情况下，vector查找的时间复杂度为线性时间，与list相同。set和map能实现对数时间的查找，而hash_map、hash_set能实现常数时间的查找。此外，如果对vector按编号进行排序，则其可以进行对数时间的查找。储存指针则可以直接访问关联元素，效率很高，但指针的维护确比较繁琐。动态的计算元素拓扑结构虽然可以节省储存空间，但速度太慢，以时间换空间得不偿失。5.元素修改网格元素属性（如坐标）应当是可修改的，而元素修改是在元素拾取的基础上完成的。元素属性修改除修改排序关键字外一般不会影响其他操作，而修改排序关键字会影响到元素的拾取。例如，当修改某结点坐标后，如果不更新用于元素拾取的序列，那么该对该结点的拾取操作就会出错。对于vector而言，无论是直接修改后再重新排序还是先删除元素再插入修改后的元素效率都比较低下。list本身删除和插入操作都很快，但要找到删除元素的位置却依然需要线性时间的复杂度。另外list的拾取操作需要借助别的容器实现，所以元素修改的耗时需要根据完成拾取的排序容器来判断。map和set都可以快速的删除后再在特定位置快速插入新元素，仅需要对数时间的复杂度。需要注意的是，不能直接修改set中元素排序关键字，否则会出现未定义行为。hash_map、hash_set与list情况类似。6总结根据上述分析，我们首先可以确定实现查找关联元素的方法：元素中储存关联元素的指针。这种方法保证了与网格拓扑结构相关操作的高效性，虽然过多的使用指针造成了程序易出错难维护的问题，但为了得到优良的运行效率，这些代价是值得的。其次，可以排除map、hash_map。map、hash_map提供了键和值的映射结构，但网格数据结构中除了编号—元素映射以外，并不需要用到这种映射关系。而因为我们采用了储存关联元素指针的方法，所以也不会用到编号—元素这一映射关系。剩下的几种容器，各有优缺点，我们来用表格进行对比。http://www.njtf.cn/ueditor/net/upload/2017-05-23/73ab191a-7832-4768-88a5-feff969e1da0.png从表中各项数据对比来看，set拥有最好的综合性能。但set也有一些需要处理的问题。首先是排序关键字的选取。假定我们以结点横坐标为关键字，那么因为同一横坐标下可能会有很多点，所以需要使用mutiset，以确保可以出现重复元素。选用横坐标为排序关键字，还会有另一个问题，因为网格数据是二维的，所以在极端情况下，仅有横坐标排序来完成元素拾取可能会出现效率问题，此时需要用另外一个容器来辅助拾取。其次，因为元素的拾取和元素修改都主要是在网格结点上进行的，网格边和网格单元的相应操作可以通过和网格节点的拓扑关系来完成，所以在不考虑这两项操作时，set并不一定是最好的选择。最终，我们根据以上分析，可以设计出一个较优的二维三角网格的数据结构：http://www.njtf.cn/ueditor/net/upload/2017-05-23/3c5f406e-64b9-4092-8534-c5bfba3c7621.png
最后，用一个实际例子来测试软件性能。下图所示为对某流域的仿真计算结果，网格数目约为五十万，浅绿色部分是选中的网格。实测软件绘图流畅，网格增加、删除、修改、选取等操作均无顿卡现象。
页:
[1]