按单海图模式设计的ECDIS,在要显示的区域超出当前海图的范围时,必须找出下一张所需的海图,然后切换显示内容,这会使整个屏幕的内容发生跳跃式的改变,给使用带来了不便。因此,许多系统都采用了基于多图模式的结构,能根据当前屏幕对应的地理范围自动在图库中搜索海图,并将需要显示的所有海图绘制在对应的位置,从而解决单幅海图存在边界而带来的问题。
基于多图模式的海图系统需要同时绘制多张电子海图,因此增加了系统的开销。由于电子海图的信息丰富,包含的数据量也大,为了提高系统性能,必须尽量减少绘制图像时的数据处理量,尤其要减少不必要的数据处理。同时,不同比例尺下海图的数目、覆盖范围都不尽相同,如果不对海图文件进行有效的管理,则不便进行快速的查找和绘制。文献从海图数据文件的管理出发,提出了一种快速显示电子海图的方法,本文对影响电子海图信息系统性能的其他因素进行了分析,并提出了对应的解决方法,用VC++6.0实现时,进一步提高了系统的性能。
1影响基于多图模式海图系统性能的因素
基于多图模式的系统在刷新屏幕内容时,其工作流程如图1所示。
其中,每一张海图的数据由总控文件、属性文件、数据文件等分别存储,在绘制时,对每个图层的每一个数据,都要先读入内存,根据显示的比例因子和显示范围判断其是否需要绘制,然后确定绘制该数据的各种参数,将图像绘制在指定的位置。因此,系统工作的大部分时间都花在打开和读取文件、绘制图像上,影响性能的主要因素有:
1)为了在使用时能快速查找,海图系统在初始化时,需要遍历图库,打开每张海图的总控文件并建立索引信息。通常图库都包含了多个比例尺的海图信息,图幅数目较大,如果每次启动都要重新建立索引信息,则系统每次初始化都要花费较长的时间,甚至使用户难以忍受。
2)在绘制一个区域时,在指定比例尺下可能存在这样的情况:有一张海图能够完全覆盖这个区域,但是另外一张或多张海图包含了这个区域的一部分。如果搜索算法没有考虑这样的情况,很可能搜索到多张海图,从而需要打开并处理多张海图。
3)相邻的海图之间会存在重叠的区域,若不进行处理,这个区域的资料就会被重复绘制,不仅影响系统性能,还可能导致图像模糊,一种方法是在该区域绘制完后保护起来,但这种方法并没有从根本上解决数据的重复绘制问题。
4)通常每一张电子海图都包含了多个图层的大量数据信息,如果每次更新屏幕时都直接打开海图文件进行绘制,更新完毕后又将所有打开的文件全部关闭,则系统需要不断对硬盘进行文件存取操作,进行大量的数据交换,从而严重影响系统的性能。
上述的最后一个问题在文献[1]中已经得到了较好的解决,因此,本文将主要研究前面三个问题。
2图库匹配检测法
系统进行初始化时建立一个海图信息链表,将系统图库中所有海图的相关信息读入内存,这样在搜索海图时,只需要对链表进行搜索,而不需要打开磁盘上的海图文件,从而提高搜索的速度。然而一个海图信息系统通常管理着多达数百张的海图,如果每次打开系统时都进行这样的工作,将耗费大量的时间来初始化。由于一个海图系统使用的图库是不会经常改变的,因此在退出系统时可以保存图库的有关信息,在下一次启动系统时,若检测到图库没有被改变,则直接读入保存的信息。
为检测而保存的信息包括图库中比例尺的数目、总的海图数目、索引信息链表,以及各比例尺下单张海图的最大幅度等信息。在下一次启动系统时,通过对比图库中总的海图张数、检验保存信息中包含的路径信息是否有效可以得知与图库中的资料是否匹配。大多数系统的图库是基本保持不变的,因此启动时只需要读入一个文件并进行匹配检测,用户基本上察觉不出这么短的时间。
3海图搜索算法
绘制一张海图的工作量很大,即使只绘制一小块区域的图像,也涉及到前面提到的众多复杂操作。而搜索海图主要是对内存中的索引数据进行比较运算,所花费的时间很少,因此,搜索算法的复杂度对系统性能影响并不大,但是算法返回的结果至关重要,因为搜索到的海图数目与绘制的工作量成正比,直接影响到系统的性能。因此,一个性能优越的海图搜索算法应该满足以下基本原则。
1)在指定比例尺下找出海图以覆盖最大的绘制范围,即屏幕上尽量不要留下空白的区域。
2)能覆盖整个绘制范围时,找到的海图数目越少越好。
3)算法具有较好的鲁棒性,在各种不利情况下(如找不到任何海图资料)都能返回有意义的结果[7]。
3.1图幅索引模型
为方便算法的设计,将一张海图与将要绘制区域的关系归纳为三类,见图2。
设绘制范围的4个边界值依次为sLeft,sTop,sRight,sBottom,宽度和高度分别定义为sWidth=sRight-sLeft、sHeight=sTop-sBottom;与之比较的海图边界依次为cLeft,cTop,cRight,cBottom,宽度定义为cWidth=cRight-cLeft,高度为cHeight=cTop-cBottom;这里前缀s表示“Screen”,c表示“Chart”。保存各比例尺下单张海图最大宽度和最大高度的数组分别为maxWidth[N]、maxHeight[N],式中N表示图库中共有N种不同比例尺的海图。
第一类关系,即海图覆盖了整个绘制范围,绘制范围的边界包含于海图范围之内,必须满足的条件为:
同时,设当前海图的比例尺对应序号为n,若该海图能包含整个绘制区域,则绘制区域的幅度要满足条件:
第二类关系中,海图覆盖了绘制区域的一部分,又可以分成两种情况:
1)海图的4个边界可分为相对的两组边,若每组中均有一条边处于绘制范围的内部,则认为该海图是应该绘制的,海图整个处于绘制区域内也属于这种情况,满足的条件为:
2)海图的一条边处于屏幕中间,而(不包含该边的)另一组边分居屏幕两侧。处于屏幕中的那条边可以是四条边中的任意一条,因此这种情况又包括四种小情况。需满足的条件可以表示如下:
3)如果海图和绘制范围的位置关系不满足上述任何条件,则说明二者没有重合的区域,海图不需要绘制。
为了使算法结构清晰,采用分两步搜索的方法。先比较绘制范围与当前比例尺下海图的最大范围,如果前者小于后者,则考虑一张海图就能覆盖绘制范围的情况。否则,直接判断海图是否覆盖了范围的一部分。需要注意的是,即使绘制范围比海图的最大幅度小,也很可能出现没有一张海图能整个覆盖的情况,此时需要继续搜索当前比例尺下的与绘制范围有重叠的海图,直到能全部覆盖为止。
3.2冗余图幅检测
多张海图拼接在一起能否覆盖整个范围,属于计算机图形学研究的范畴,可以利用VC++6.0里的ExcludeClipRect()函数进行判断,但是这种方法带来一个隐藏的问题:设一个绘制区域可由B、C两张海图完全覆盖,而A海图也包含了该区域的一部分,但是不能与其他任意一张海图一起完全覆盖绘制区域,若按链表顺序依次搜索到A、B、C海图,则搜索函数将返回3张海图的信息,从而将AB多余地绘制出来。为避免这种情况的出现,必须加上冗余图幅检测程序,对搜索到的海图进行排列组合并一一进行检验,找出能覆盖绘制范围的最少海图组合。对于3张图的情况,由于已知AB组合是不合要求的,只需检验(C23-1)种情况,即AC、BC组合。同理,对于搜索到r张海图的情况,其两两组合有C2r-1种,三三组合有C2r-1种,依此类推,需要检验的组合数R为:
当r增大时,冗余检测的工作量将迅速增大,因此要控制一次同时显示的海图数目。通常屏幕上需要显示5张以上的海图时,显示比例就会过小而导致无法分辨信息,可以改用更小的比例尺,用较少的图幅覆盖整个绘制范围。对于找到5张海图的情况,可计算出需要检验的组合数为22,所耗费的时间仍是可以忽略不计的。经过实践,在需要绘制5张海图时,这种检验通常可以减少一至两张海图的绘制量,平均减少20%的绘制海图数目,从而明显提高绘制速度。
算法主要进行两个方面的工作:找出与绘制区域有重叠区域的海图;返回能满足要求的最少海图数目。在所有的比例尺下都没有找到需要绘制区域的资料时,返回全局海图的信息。
4重叠区域绘制方法
相邻的两张海图常会出现重叠的区域。常采用的绘制方法如文献[1]中所述,这种方法能正确地将每幅图绘制在相应的位置,但没有避免重叠区域元素的重复绘制。
单图模式下,一个要素是否要绘制,取决于其是否处于绘制区域之中。对于多图模式,当元素处于两个以上海图的的重叠区域中时,可能另外一张海图对应位置的元素已经被绘制过了,因此需要改进判断的方法。为方便叙述,设需要绘制三张海图,将能覆盖绘制区域最大面积的海图记为A,其余2张记为B、C。先绘制A图能提高坐标判断的命中率。记A、B的边界分别为cALeft,cATop,cARight,cABottom和cBLeft,cBTop,cBRight,cBBottom。对于A中的元素,只需要与绘制范围进行比较,判定是否需要绘制。设元素的地理坐标为(mX,mY),那么满足以下条件的元素需要绘制,其中sLeft等为绘制范围的边界:
对于B图的绘制,即使元素坐标满足上述条件,也还有可能与A图的资料重复。若满足条件:
则说明该元素位于A图的范围内,该位置的元素已经被绘制过一次,不需要再次处理。只有不处在重叠区域的元素才有必要与屏幕绘制范围进行比较。同理对于C图的绘制,先查看元素是否处于A∪B的范围内,再与绘制区域进行判断。
经过这样的处理后,重叠区域的元素将不会被重复绘制。与绘制一个元素所需要的时间相比,这种判断的方法不会多花时间,反而能节省重复处理数据的大量时间。当重叠的区域较大时,效果更加明显。
5结论
基于上述算法和各方法设计的ECDIS,与未采用改进方法时相比,启动过程耗时从15s左右减少到2s;在绘制同一个范围的图像时,打开的图幅通常可以减少1～2张;由于采用改进的冗余元素判断方法,绘制第一张海图速度没有变化,但是后续海图的绘制速度明显加快。通过多次使用和对比分析,得到以下结论:
1)采用图库匹配检测法对电子海图信息系统进行规划和设计,可以较好地管理系统的图库,缩短了系统初始化的时间,在图库改变时能立即进行信息链表的更新。
2)在图幅搜索函数中采用冗余图幅检测的方法,使得返回的海图数目尽量减少,不仅减少数据的绘制量,而且减少操作的文件数目,可以较大幅度地提升系统的性能;搜索算法只对内存中每张海图进行边界范围的比较,其算法复杂度为O(n);而冗余检测算法中,比较次数随海图数目的增加而迅速增大,但由于限制了同时显示的海图数目,比较运算的时间开销非常小,因而不会影响系统性能。
3)对相邻海图重叠区域的绘制进行恰当的控制,可以大大减少冗余数据的绘制量,且屏幕上显示的质量丝毫不会受到影响,从而加快了绘制速度。
电子海图资料正朝着越来越详细、精确和完整的方向发展,海图信息系统必须从每一个可以改进的方面去提高性能,才能以令人满意的速度去处理海量的信息。本文从初始化、图幅搜索、重叠区元素绘制三个方面进行探讨,初步解决了制约基于多图模式系统性能的问题,并运用在某电子海图信息系统中,取得了良好的效果。
