摘要：为解决嵌入式系统应用电子航海图出现的单幅图存储量、图廓范围过大，以及图幅重叠等问题，以SHAPE格式图为例，设计并实现了矢量电子航海图的分割方法。采用多边形布尔运算法则处理多边形的剪裁，不限制实体和剪裁多边形类型，使得该分割方法不仅适用于等经纬网格分割，也适用于不规则分割。应用该分割方法对海图数据进行预处理，可以适应硬件资源有限的嵌入式应用，从而提高系统设计的自由度、降低总体成本，促进电子海图系统的推广。

关键词：水路运输；电子航海图；嵌入式系统；多边形剪裁；布尔运算

矢量电子航海图（以下简称矢量图）是目前国内外电子海图应用系统主流的数据类型，具体格式包括SHAPE、S57、MAPINFO等。在嵌入式系统上开发矢量图的应用程序，将不可避免地面临以下问题：

1．单幅矢量图的存储数据量大，而且大小很不平均。以我国的SHAPE格式为例，单幅图存储的数据量从几百k到十几M，对主机内存和CPU速度有较高要求。高端的PC机很容易满足这两点，而很多基于电子海图的嵌入式应用，由于CPU速度有限，装载数据的时间往往超出用户预计的范围；或者其内存就不足以装载一幅海图。

2．单幅矢量图的范围大大超过了一般显示终端的大小。我国SHAPE格式海图分幅与纸质海图一致，尺寸约100cm×80cm。为显示屏幕内小范围数据，而遍历整幅海图，造成海图绘制时间过长，效率不高。

3．矢量图之间存在重叠现象。不仅浪费了存储空间，而且在查询物标时容易出现二义性。

本文提出分割矢量图的方法解决以上问题。通过调整分割大小，可保证所有单幅图的数据量在一定限度之内适应不同主机资源约束。通过预先的分割，可以采用简单的数据结构达到较高的显示效率。而且，对于数据的重叠部分，分割后可以剔出，保证数据的唯一性。本文以SHAPE格式海图为研究对象，应用计算机图形学中多边形布尔运算法则处理多边形的剪裁，不限制实体和剪裁多边形类型，使得该方法不仅适用于等间隔经纬网分割，也适用于不规则分割。

1 矢量图组织结构

SHAPE格式矢量图以图幅为单位组织，一幅图一个目录，其文件由一个控制文件、多个图形文件、索引文件、属性文件组成。从内容上看，一幅图主要包括图幅元数据、物标的几何和属性数据。

图形文件记录物标的几何位置数据，为可变长记录文件。索引文件记录对应的图形文件，记录相对于图形文件开始点的偏移量。属性文件为dBase表文件结构，记录了物标的属性。图形文件记录与属性文件记录通过记录号一一对应。控制文件主要包括：图幅名称、比例尺、图廓边界、投影方式等海图元数据。

图1 SHAPE格式图组织结构示意

2 分割流程

分割不仅包括几何数据的剪裁，也包括元数据、属性数据的重新赋值。分割后生成的新图必须符合原有标准。受分割操作影响的元数据主要是图廓边界，属性数据依赖于几何数据存在，除类似周长、面积、最小外接矩形等属性随之改变外，其它类似灯标灯质、等深区水深等描述性属性不随分割操作而改变。

设定分割窗口；

if（矢量图是否与分割窗口相交）then

{以原始图廓与分割窗口的交集作为新的图廓边界；

Repeat

提取物标层的信息，如物标种类、数量、几何类型、最小外接矩形、属性类型列表等；

Repeat

根据记录号提取物标几何数据和属性数据

采用不同的剪裁算法处理点、线、面物标

将原物标属性复制到分割后的物标，重新计算新物标与几何特征相关属性信息（周长、面积、长度、最小外接矩形等）

Until该层所有物标处理完毕；

重新计算该层包含的物标数量，最小外接矩形等信息；

Until所有物标层处理完毕；

}

分割结束；

对于点状物标，分割方法很简单，只需判断点位是否位于分割窗口之内，采取保留或放弃即可。线状物标的剪裁算法[1-2]也比较成熟，本文采用Reppaport A提出的线段剪裁算法。

3 多边形剪裁

面状物标的处理相对复杂，特别是SHAPE格式规定的多边形有如下几个特点：

1．包含有“洞”多边形。

2．多边形顶点数目巨大。

3．顶点位置用浮点数表示。

以上特点分别从适用范围、时间空间复杂度、数值鲁棒性方面，对剪裁算法提出较高的要求。在分析比较文献[3-10]的基础上，本文依据Vatti B.R.算法[3]，采用布尔运算法则剪裁SHAPE图中的复杂多边形，取得较好效果。为了便于描述，首先引入多边形裁剪的一些基本概念。

3.1 基本概念

1）多边形边的方向与内外区域的关系

当多边形边的方向为顺时针时，沿着边的方向，右侧区域为多边形的内部，左侧区域为多边形的外部。反之，如果多边形边的方向为逆时针，则左侧区域为多边形的内部，右侧区域为多边形的外部。

2）进点和出点的定义

设I是多边形S和C的一个交点。如果S沿着S的边界方向在I点从C的外部进入C的内部，则称I为S对于C的一个进点。反之，如果S在I点从C的内部出到C的外部，则称I为S对于C的一个出点。进点和出点定义是一个多边形相对另一个同多边形的[5]。如图2所示，阴影部分为多边形内部，I为S对于C的进点，是C对于S的出点。

图2 进点和出点的定义

3.2 布尔运算和实例

下面介绍采用布尔运算法则处理矢量图中有“洞”多边形的基本思路。不失一般性，设实体多边形S和剪裁多边形C都为有洞多边形，采用集合表示方法

（1）

（2）

式（1）和式（2）中：S0、C0分别为两多边形的外部轮廓，S1…n、C1…n分别为两多边形的“洞”。在这里，多边形的内外边界都是顺时针方向。

1）确定两多边形内外部轮廓之间的布尔算子。

多边形剪裁的结果是两个多边形的交集。根据集合的布尔运算法则，

（3）

以上结论可描述为：两外部轮廓进行交集运算，得到交集的结果多边形；洞与洞之间进行并集运算，如果结果多边形之间还有相交，继续并运算；然后将洞的并集多边形全部反向，与外部轮廓的交集多边形再求交，得到最终结果。

对于分解后的每个布尔运算，进行“2）~4）”的操作：

2）求两多边形之间的交点，形成交点集。

3）判断各交点处一个多边形相对于另一个多边形的出点、入点性质。

4）从多边形第一个交点出发，根据布尔算子和交点的进出点性质，判断是否把跟踪路线切换到另一个多边形，并选择正确的方向沿着相应多边形的边继续跟踪。对于“交”操作，在交点处进入多边形；对于“并”操作，在交点处出多边形。当到达下一个交点时，再次判断是否切换多边形，以及选择正确的方向继续跟踪，直至又回到第一个交点，形成一条完整的回路[3]。如果交点集中仍有没有被经过的剩余交点，则继续按照同样的方法处理剩余的交点，直到所有的交点都被经过。处理完毕得到的多边形就是布尔运算的结果。

如图3所示，S0与C0交点为（I0，I6）。根据进出点的定义，I0是S0到C0的进点、I6是S0到C0的出点。S0∩C0的结果多边形为（I0，，I6，），设为A。S0与C0没有未处理交点。再看S1与C1交点为（I2，I4），I2是S1到C1的进点、I4是S1到C1的出点。S1∪C1的结果多边形为（I2，，，，I4，，，），设为B。S1与C1也没有未处理交点。将B反向得（I2，，，，I4，，，）。又求得A与B的交点（I1，I5，I7，I3）。其中，I1、I7是A相对B的出点，B相对A的进点；I5、I3是A相对B的进点，B相对A的出点。从I1开始，A∩B的一个结果多边形为（I1，I2，I3，I0）；由于还有未处理的交点（I5，I7），再从I1开始，另一个结果多边形为（I5，I6，I7，I4）。因此，A∩B得到的两个多边形即为S∩C的最终结果。

图3 多边形剪裁实例

该算法具备以不规则形状分割矢量图的功能，图4是对同一幅海图进行星型和矩形分割的结果。从应用角度来看，矩形分割最为广泛。矩形大小主要考虑内存和显示器尺寸。以我国出版的SHAPE格式矢量电子航海图为例，数据总量约800MByte，存在700万、400万、230万、100万、50万、25万、10万等比例尺级别的单幅图对应纸质图幅。对于两种硬件条件（工业主板：64M内存、12寸液晶屏；掌上电脑：32M程序内存、5寸液晶屏），对相应比例尺图采用30°、20°、10°、5°、2°、1°和20°、10°、5°、2°、1°、30′经纬度方格两种方案进行分割。两种方案分割后的矢量图，在相应的硬件环境下均满足内存约束，且显示速度达到适时性要求。

图4 海图分割结果

4 结语

目前本文研究的算法仅限于无拓扑关系的矢量图。对于类似S57等有拓扑的矢量图，还需考虑分割后拓扑关系的重建。

参考文献

[1] Reppaport A．An efficient algorithm for line and polygon clipping[J]．Visual Computer，1991，7（1）：19-28

[2] 刘勇奎，颜叶，石教英．一个有效的多边形窗口的线裁剪算法[J]．计算机学报，1999，22（11）：1209-1214．

[3] Vatti B R．A generic solution to polygon clipping[J]．Communications of the ACM，1992，35（1）：56-63．

[4] Greiner G，Hormann K．Efficient clipping of arbitrary polygons[J]．ACM Transactions on Graphics，1998，17（2）：71-83．

[5] Rivero M L，Feito F R．Boolean operations on general planar polygons[J]．Computer &Graphics，2000，24（6）：881-896

[6] 刘勇奎，高云，黄有群．一个有效的多边形裁剪算法[J]．软件学报，2003，14（4）：845-856．

[7] 刘红军，王从军，黄树槐．带有孔洞的多边形的布尔算法[J]．华中科技大学学报（自然科学版），2003，31（8）：18-20．

[8] 董未名，玛依拉•巴榜，周登文，等．平面扩展简单多边形的布尔运算[J]．计算机辅助设计与图形学学报，2003，15（9）：1134-1140．

[9] 谢步瀛，张岩．用分段法与链表法的二维布尔运算[J]．工程图学学报，2003，24（2）：78-84．

[10] 姚辉学，卢章平．海量数据多边形布尔运算的区域分割算法[J]．中国图象图形学报，2007，12（3）：552-557．

作者：钟云海 郑海 周建波  来源：中国航海