多边形区域信息最佳注记位置分析

2014-08-15康建荣刘翘楚

测绘通报 2014年6期

康建荣，李新，刘翘楚

(1. 江苏师范大学测绘学院，江苏徐州 221116； 2. 无锡南洋职业技术学院，江苏无锡 214081；3. 连云港市国土资源局，江苏连云港 222001)

一、引言

注记是地图重要的组成部分,是计算机地图制图和地理信息系统的关键问题之一。在土地利用现状图中标注图斑号和土地类型时，标注位置直接影响图面的清晰和美观。土地利用现状图的图斑是多边形，根据多边形的几何特点，分为凸多边形和凹多边形。本文基于土地利用现状图的信息注记对多边形的最佳标注位置进行分析。

二、问题的提出

多边形区域内的注记一般是按多边形重心来标注的，如图1(a)所示。但由于多边形区域的复杂性，其重心位置可能位于边界外部，如图1(b)、(c)所示；也有的重心在边界内部，但距离边界较近或者严重偏离，如图1(d)所示。因此，仅靠重心来判断标注位置，不论在标注质量上还是美观上都远远不能满足注记要求。

MapGIS和ArcGIS是目前土地利用现状图制作较为常用的软件，能够方便快速地实现土地利用现状图斑的数字标注功能。但针对某些特殊的图斑其标注位置也不是很好，需对个别位置进行手工调整，如图2所示。当标注位置不理想、偏离图斑较大、处理的数据量较大时，仅依靠手工改动是很费时费力的。

由于标注效果的缺陷以及数字注记的特殊性与复杂性，土地利用现状图斑自动数字注记还没有完全适用于所有图斑的算法，对于某些特殊的图斑仍然会出现不理想的注记效果。科研工作者一直致力于土地利用现状图斑自动数字注记算法的研究，通过寻找相对完善的注记算法来提高图斑数字注记的质量和效率。本文从土地利用现状图斑的特点出发，提出基于最大内接四边形的图斑自动数字注记方法。

图1 不同规则形状的图斑重心位置

图2 MapGIS和ArcGIS中不理想的标注位置

三、注记位置的理论分析

根据多边形的特点，不论形状是简单还是复杂，其内部总存在一个面积最大的内接四边形，这个四边形的重心就是最适合标注的位置点。

设多边形的顶点为A1(x1,y1)，A2(x2,y2)，…，An(xn,yn)，则其函数形式为

a∈(xi,xi+1),b∈(yi,yi+1)

上述多边形函数形式可写成

设B1(a1,b1)、B2(a2,b2)、B3(a3,b3)、B4(a4,b4)为多边形边界上任意4点，其组成的四边形(顶点沿顺时针方向排列)，面积为S，则有

为了得到S的最大值，做拉格朗日函数

φ=S+λ1·f(x,y)+λ2·f(x,y)+

λ3·f(x,y)+λ4·f(x,y)

分别对a1、a2、a3、a4和b1、b2、b3、b4求偏导数并令其等0，即有

经化简后得

要使等式成立，必然有

b2=b4，a2=a4，b1=b3，a1=a3

当上述条件同时成立时，B1(a1,b1)和B3(a3,b3)为同一点，B2(a2,b2)和B4(a4,b4)为同一点，这时内接四边形退化成直线，从而确定出在多边形内的内接四边形最大面积产生的两组条件为

条件1：a2=a4，b1=b3

条件2：a1=a3，b2=b4

这两个条件实质上可归纳为：相互垂直的两直线与边界交点组成的四边形。这时针对第1个条件，其内接四边形的面积可写成

式中，Δx=|a4-a2|；Δy=|b3-b1|。

由此可得到结论：对于一个任意多边形而言，其面积最大的内接四边形是存在的，最大横向截距和最大纵向截距组成的四边形即为面积最大内接四边形。

四、实现方法

1. 最大内接四边形查找方法

根据上述分析，多边形内存在的面积最大的内接四边形是由相互垂直的两条直线与多边形边界交点组成的四边形，为了找到最大横向截距和最大纵向截距，本文提出了一种基于规则网格的四边形查找方法，即将图斑划分为若干网格，以网格点为四边形对角线的交点，网格横向、纵向扫描线与图斑边界的上下左右4个交点为四边形的4个顶点。

所构网格点如图3所示，将图斑以一定的网格间距划分，由于外部网格点不参与计算，故可先查询并记录图斑内部网格点。

图3 图斑网格示意图

由于图斑边界的复杂性，对于每条横向网格扫描线而言，所求的交点个数常多于两个，为方便对每个网格点交点信息的获取，可对交点作以下判断：若所求交点不是图斑边界线段的端点，记录此交点；若所求交点是图斑边界线段的端点，则判断该点前后两点的位置关系，若这两点在此端点的异侧，记录此交点(注意：起点和终点只记录一次)，反之，不记录。

经上述判断后所求的交点个数始终为偶数，将交点两两配对：1号交点与2号交点配对、3号交点与4号交点配对、……，交点两两配对的线段必定为图斑内部线段，减少了对两交点之间线段的判断。对位于两交点之间的网格点，可直接将这两个交点纳入其网格点的left、right点索引信息中。同样，对于纵向网格扫描线也是如此。

建立网格点索引后，对于每一个网格点都有一个与其相对应的四边形，排除与图斑边界相交的四边形即为符合要求的四边形，如图4所示，四边形ABCD、EFGH即为该图斑内的任意内接四边形。

图4 图斑内的任意内接四边形

有一种特殊情况的四边形需考虑，如图5所示，四边形虽然与图斑边界没有端点以外的交点，但此四边形并不是图斑的内接四边形，其重心位置也不符合该图斑的注记要求，该情况可通过四边形边的中点来判断排除。

图5 与边界无多余交点的特殊四边形

2. 形状因子分析

由于图斑边界的复杂性，面积最大的内接四边形的重心位置不一定是最佳的数字标注位置。因此，为确保标注位置的良好性，本文又综合考虑了四边形的形状因子，排除形状不好的内接四边形。

四边形ABCD的两条对角线为AC和BD，O为两条对角线交点，如图6所示。

形状因子K的计算公式为

为确保K≤1，上式中可限定AO

图6 形状因子示意图

可设定一定的阈值来限定需要进行形状因子比较的内接四边形，本文选取了与最大内接四边形面积差小于十分之一的四边形进行形状因子计算，意在找到面积最大且形状因子较好的内接四边形。对于图7所示的图斑而言，找到的面积最大且形状因子较好的四边形如图7(c)所示。

3. 网格密度对标注位置的影响

从图7(a)的标注情况来看，标注位置大体合适，但标注效果仍然不是十分理想。这主要是由寻找四边形时所划分的网格决定的。显然网格的密度稀疏程度对面积最大内接四边形的获取有着很大的影响，并直接影响其标注效果。若网格密度太稀疏，标注位置效果不理想；反之，若网格密度太密，则必会造成算法时间长且效率降低。

从图7的标注效果来看，50 m网格间距太稀疏，注记位置严重偏离了该图斑中心区域，网格密度加倍后，25 m相对于50 m的网格，标注效果得到了很大的改善，继续加密网格，标注位置变化不明显。因此，如何做到时间与效果的完美结合是关键，表1是本文针对不同图斑经过多次测试得到的一组较为合适的网格密度的经验值。

表1 不同图斑网格密度选取测试结果

续表1

表1中

α=图斑面积/图斑最大最小值组成矩形面积

β=图斑周长-图斑最大最小值组成矩形周长

式中，α表明了图斑的饱满程度，其值越大，图斑的形状越好且凸性越强；β表明了图斑的凹凸复杂性。β>0，表示图斑形状复杂，凹凸拐点较多；β<0，表示图斑比较狭长。

由表1可以看出，不同形状的图斑标注所需要的网格密度虽然不一样，但相差不是很大，当min(Δx,Δy)处于0～400 m之间时，网格密度的选取在20～30 m之间，当min(Δx,Δy)处于400～1600 m之间时，网格密度的选取在30～40 m之间，且同一范围内，α因子较大的图斑网格密度选取较大，β因子绝对值越大，网格密度选取也较大。可根据情况选取该范围内对所有图斑较为合适的一个网格密度。

五、结束语

本文针对土地利用现状图标注过程中某些特殊图斑的标注缺陷问题，提出了一种基于面积最大内接四边形的标注方法。通过理论推导，得到了图斑内面积最大内接四边形存在的条件，即找到具有最大横向截距和最大纵向截距组成的四边形，由此提出了基于一定密度规则格网的最大内接四边形的查找方法，结合形状因子找到最理想注记位置的面积最大的内接四边形，由该四边形的重心位置确定图斑标注位置。试验证明，面积最大且形状因子较好的四边形具有最佳标注位置。针对不同形状的图斑，分析了查找最大内接四边形的网格密度经验值，从而为编制程序提供了依据。

参考文献：

[1] 朱正国，柳荣其.地图中面状要素标注算法的设计与改进[J].西华大学学报：自然科学版，2009,28(2)：38-42.

[2] 焦明勇，苏鸿根.一套多边形内专业注记的定位方法及其应用[J].计算机工程与科学，2008，30(6)：44-47.

[3] 吴长彬，闾国年，刘昱君.基于规则库和网格算法的土地利用现状图自动数字注记[J].测绘学报，2008，37(2)：250-255.

[4] 余代俊，耿留勇.基于Delaunay三角形实现面状要素自动注记[J].测绘通报，2006(11):26-28.

[5] 杜世宏，杜道生，樊红.面状地物自动注记方法探讨[J].测绘信息与工程，2000(4)：6-8.

[5] 樊红,张祖勋,杜道生.地图线状要素自动注记的算法设计与实现[J].测绘学报，1999，28(1)：86-89.

[6] 贺彪，李霖，朱海红.数字制图中面状注记自动配置的研究[J].测绘信息与工程，2007，32(6)：12-14.

[7] 高辉，刘金义，卢英，等.利用近似骨架线进行面状要素注记算法及实现[J].计算机与数字工程，2006，34(9)：115-116.

[8] 耿留勇，余代俊.中心阵列法实现面状地图要素的自动注记[J].测绘科学，2007，32(2)：36-37，63.

[9] 姜永发，张书亮，兰小机，等.长对角线法实现GIS中矢量地图面状地物汉字注记的自动配置[J].武汉大学学报：信息科学版，2005，30(6)：544-548.

[10] 杜世宏，王桥，杜道生，等.地名注记自动配置的关键技术研究[J].地理与地理信息科学，2003，19(1)：20-24.