不规则区域面积的矩形四等分割计算法

第34卷第6期201112测绘与空间地理信息

GEOMATICS ＆SPATIAL INFORMATION TECHNOLOGY

Vol．34，No．6Dec．，2011

不规则区域面积的矩形四等分割计算法

张海涛，杨敏华

（中南大学信息物理工程学院，湖南长沙410083）

要：如何对图纸上的区域面积进行计算，尤其是曲边不规则区域的面积计算，是一项基础工作。本文在详细

分析了现有区域面积计算法的基础上，提出了一种应用于图纸上不规则区域的面积计算方法。应用本文提出的摘

不规则区域面积的矩形四等分割计算法逐次将目标区域所在的矩形四等分割，直到满足精度阀值要求为止，将区域内所有有效值相加，得出区域总面积。此方法灵活性强，分辨率高，且易于在计算机上编程实现。关键词：不规则区域；四等分割法；面积计算；四叉树中图分类号：O174．41文献标识码：B 文章编号：1672－5867（2011）06－0272－03

Calculation of the Irregular Area Based on Fourth －Division Method

ZHANG Hai －tao ，YANG Min －hua

（School of Information and Physics Engineering ，Central South University ，Changsha 410083，China ）

Abstract ：How to calculate the size of the region on the map or paper ，especially the curved region of the irregular area is a basis for the work．In this paper ，Based on a detailed analysis of existing regional space law it give a drawing applied to the irregular method of calculating the size of the region．The method is based on grid data storage methods Quadtree principle ，first of all to identify anomalies outside the region where the MBR （Minimum Bounding Rectangle ）．Then ，using the method of this paper ，four successive division of calculation of irregular rectangular area to the target area where the four rectangular partition ，and so on ，until the accuracy to meet the threshold requirements ，the region will all add up to RMS ，come to the region total area．This method is flexible ，variable resolution ，and easy －to －computer programming．

Key words ：irregular area ；fourth －division method ；calculation of the area ；Quadtree

0引言

低，而且计算量同样较大的问题，如果需要较高精度时只

能换用更小方格的透明纸，重新进行方格的统计工作，从而增加了工作量。如何较为简单并且准确地计算不规则曲线图形的面积成为本文的研究重点。

本文所采用的方法是先确定不规则区域所在的最小

［6］

Minimum Bounding Rectangle ），外接矩形（MBR ，然后将

其依次进行四等分割，直至满足精度要求时停止划分，同时在与其对应的四叉树上进行标记，对区域内所包含的各层次矩形进行统计相加，从而得到不规则区域的总面积。

面积计算历来是数学计算中的一类重要问题，其涉

［1］

及到经济建设中的诸多方面。在城市规划和水利建设工程中，经常会遇到计算平面或断面面积的问题。规则图形的面积计算简单，可以根据公式直接计算得到；而不规则图形，尤其是不规则曲线图形面积的计算十分烦琐，是一件较为麻烦的工作。但是现实中大多数情况下为不规则图形，如何较为准确地计算图纸上一不规则区域的面积成为一个重要问题。面积计算方法现在主要有几何图形法、网格法、辛普逊3/8法、求积仪法、坐标计算法［2－5］

。坐标法计算面积，等早已被人们所熟悉，其优点是精度高、数据稳定、资料便于整理等。但至今未被广泛使用，其主要原因就是因为计算工作量太大，使其受到限制。现实中往往采用规则正方形格网法，将一画有格网的透明纸附于图纸之上，通过计算区域内方格的数目来

但是存在精度较计算面积。此方法虽能计算区域面积，

收稿日期：2010－09－13

1基本概念

矩形四等分割法思想来源于栅格数据的四叉树存储

［7－9］

，四元树是最有效的数据压法。四叉树又叫四分树、

缩方法之一。同时四叉树分割法具有分块灵活、算法简单等优点，目前已成为最流行、最实用的分割方法之一。其基本原理如下：选取初始矩形（可以是正方形也可以是

作者简介：张海涛（1984－），男，河北沧州人，地图学与地理信息系统专业硕士研究生，主要研究方向为GIS 应用及国土信息化。

第6期

张海涛等：不规则区域面积的矩形四等分割计算法273

长方形）对应四叉树的树根，当面积误差超过预定阀值

将初始矩形等分为4个子块，分别对应于四叉树树根时，

的四个子节点。依次考虑4个子块中的每一块，当误差超

再将此块等分成四个子块。重复这一过过预定阀值时，

程直至包含边界的子块满足精度阀值要求时为止。图1

表示一个四叉树的分割过程

。

图2四叉树标记示意图

Fig．1Sketch map of quad tree marker

5）通过四叉树图形，对目标区域所包含的各级矩形

m 0，m 1，m 2，m 3，……，m n ，将其与对应的面个数进行统计，

积相乘后相加求和得到总面积：

S =m 0ˑ S 0+m 1ˑ S 1+m 2ˑ S 0+m 3ˑ S 0+……+

Fig．1

图1四叉树分割过程

The division progress of Quadtree

m n ˑ S n

=m 0ˑ ab +m 1ˑ ab /4+m 2ˑ ab /42+m 3ˑ ab /43

+……+m n ˑ ab /4n

下面举例说明算法的具体过程：首先，确定区域的最小外切矩形如图3所示

。

矩形四等分割法将目标矩形区域逐步分解为一系列

最小区域为满足精度阀值要求的单元。的小矩形区域，

它使区域中不包含边界的部分以较大的图像块表示，以从减少划分次数；而区域边界部分以较小的图像块表示，

而保证较高的计算精度。

Minimum Bounding Rectangle ），最小外接矩形（MBR ，

它是指包含目标区域在内且与其外边界相切的矩形。

MBR 具有唯一性，特殊性。

2算法的设计与实现及性能分析

不规则区域的四等分割法是一种逐次分级划分的方

图3目标区域的MBR 确定过程

Fig．3The progress of identifying MBR

of the target area

第二步，对MBR 进行划分后，以左下方子块划分为例进行计算（其他子块计算类似）如图4所示

。

法，其精度随着包含边界区域的矩形的划分次数的增加而逐步提高。所以计算时可以根据实际情况对精度要求的变化而确定划分级数。

2．1算法计算步骤流程

下面介绍该方法的计算流程：

1）确定不规则区域所在的最小外切矩形，进行标记，

b ，边长分别为a ，则初始矩形的面积为S 0=ab 。

2）依次对各级矩形进行四等分割，对包括边界的矩形再进行四等划分，每次划分后矩形面积与划分层次的关系为：

S 0=ab S 1=ab /4S 2=ab /42S 3=ab /43S 4=ab /4

4S n =ab /4n

由上可以得出，进行n 次划分后包含边界的小矩形的

n 面积为S n =ab /4。

3）根据精度阀值的要求，确定划分的层次，当阀值ε

≥s n /2为止。

4）划分结束后，用四叉树进行标记，标记过程中，如果某一子块包含于要计算面积之内，则在其子叶下标记“0”，“①”（如图2所示）

。为如果不在，则标记为

Fig．4

图4四等分割及标记过程

The progress of fourth －division and mark

274

测绘与空间地理信息

3

结束语

2011年

第三步，根据四叉树标记统计出个级别子块的个数，见表1。

表1对应于四叉树的统计表

Tab．1The statistical table of Quadtree

S n 数目m 面积s

S 00ab

S 10ab /4

S 21ab /42

S 32ab /43

S 44ab /44

………………

本文根据四叉树栅格存储模型，提出了一种基于矩

通过形区域四等分割法来计算不规则区域面积的方法，对于包含边界的子叶矩形有选择地进行四等划分，减少

了不必要划分带来的时间消耗，并且此法具有可变分辨率，精度可以根据要求逐级提高。

该方法对于矩形区域接近正方形时计算较为准确，但是如果区域为狭长形时，其最小外切矩形的长宽比过大，再进行四等分割时，对边界区域控制不够明显，为此应将其分为几个区域后再进行分割计算。

再根据面积公式：

S =m 0ˑ S 0+m 1ˑ S 1+m 2ˑ S 0+m 3ˑ S 0+……+m n ˑ S n

=m 0ˑ ab +m 1ˑ ab /4+m 2ˑ ab /42+m 3ˑ ab /43

+……+m n ˑ ab /4n

计算即可得到面积的近似精确值。

参考文献：

［1］万海清，卢华斌，周国庆，等．不规则地形表面积的测算

．湖南文理学院学报，2004，16（4）：74方法及应用［J ］－76．

［2］周传根，郑银生．解析法计算不规则图形面积的探讨

［J ］．当代建设，1995（5）：31－33．

［3］李勇．不规则图形面积测算的精度分析［J ］．南华大学学

2001，15（1）：57－58．报（理工版），

［4］张丽．数点法求不规则图形面积初步探讨［J ］．东北水利

2004，22（5）：8－11．水电，

［5］李惜民．Excel 法计算不规则图形面积在水文上的应用

［J ］．水利水文自动化，2004，9（3）：49－50．

［6］邬伦，——原理、刘瑜，张晶，等．地理信息系统—方法及应

M ］．北京：科学出版社，2001．用［

［7］任秀芳，姬光荣，姬光玉．基于四叉树分割的分型图像编

J ］．微计算信息，2007，23（3）：291－293．码改进法［

［8］赵慧，．宋星．基于线性四叉树的快速邻域查询算法［J ］

2007，18（28）：4333－4335．计算机工程与设计，

［9］钱春强，王继成．四叉树理论在分形图像编码中的应用

［J ］．计算机工程与应用，2007，43（23）：61－63．

2．2算法性能分析

对于算法的性能分析，首先分析其时间复杂度。由

上可知本算法的实现大致可以分为三步：

第一步，根据区域范围确定区域的最小外切矩形，这一步所需时间有限。

第二步，对矩形进行有选择地逐次分割，所谓有选择性就是根据精度要求对包含边界的矩形进行分割，比起全部进行格网划分的方法，减少了对一些完全处于或完全不处于所计算面积之内的矩形的不必要的划分，从而节约了时间。减少工作量，

第三步，分析结果的精确性和算法的健壮性。四等分割法与格网划分方法的最大区别在于四等分割法的叶节点所对应的区域面积大小不等，划分灵活，可以根据精度要求对包含边界的矩形进行多次划分，从而提高精度，方便快捷。再者四等分割法具有任意划分的自由度，不用将所有区域依次进行四等分割，简化了分割处理，增强了算法的健壮性。

［责任编辑：王丽欣］

（上接第271页）

表4不同转换参数解算同点坐标对照表Tab．4

坐标X Y

The calculated coordinates of the same points

using different conversion parameters

解算值13192179．3763678940．3407

解算值23192179．3803678940．3386

差值0．0040－0．0021

来求取空间转换参数，以便在GPS 解算时直接采用平面坐标和水准高。

3）空间转换模型中，转换参数受大地高影响较小，在高程要求不高的时候可以直接采用观测大地高求算七参数，从而计算出平面坐标。

参考文献：

［1］朱华统，．北杨元喜，吕志平．GPS 坐标系统的转换［M ］

1994．京：测绘出版社，［2］李征航，．武汉：武汉黄劲松．GPS 测量与数据处理［M ］2005．大学出版社，［3］刘基余，李征航，王跃虎，等．全球定位系统原理及其应

M ］．北京：测绘出版社，1999．用［［4］徐卫明，赵俊生．GPS 测量坐标转换实用性问题的分析［J ］．测绘工程，2000，9（2）：10－15．

4结束语

通过理论研究和实例验证，可以得出以下结论：

1）高斯投影是非线性变形，平面转换模型只适合范

围较小的工程使用，对于大面积的GPS 测量就应该使用空间转换模型。

2）由于GPS 观测数据中，点的大地高一般无法精确求得，一般采用水准联测的方法代替转换坐标的大地高

［责任编辑：王丽欣］