计算几何空间数据处理算法

计算几何是研究几何图形的计算机存储、表达、处理和分析等的理论 与技术。而地理信息系统（GIS）处理的主要对象是空间数据（图形数据）。因此，如何 运用 计算几何的基本理论、方法、算法等为空间数据处理服务，已成为近年来 GIS领域 研究的焦点问题之一。《计算几何：空间数据处理算法》首 先介绍计算几何基元及算法，然后依据计算几何在空问数据处理中的 不同作用，分别论述空间分析算法、空间查询算法、空间数据可视化算法、空间关系 表达算法及地图自动综合算法。本书注重介绍算法的基本原理与具体的实 现过 程。其论述深入浅出、图文并茂，便于读者理解与掌握。本书适合于地理、地图、测量、城建等 领域的广大研究人员和技地理信息系统理论与应用丛书计算几何:空间数据处理算法闫浩文王明孝王中辉编著鄞州区减书YaLIYzL0890188328学出版訣北京内容简介计算几何是研究几何图形的计算机存储、表达、处理和分析等的理论与技术。而地理信息系统(GIS处理的主要对象是空间数据(图形数据)。因此,如何运用计算几何的基本理论、方法、算法等为空间数据处理服务,已成为近年来GIs领域研究的焦点问题之一。本书首先介绍计算几何基元及算法,然后依据计算几何在空间数据处理中的不同作用,分别论述空间分析算法、空间查询算法、空间数据可视化算法、空间关系表达算法及地图自动综合算法。本书注重介绍算法的基本原理与具体的实现过程。其论述深入浅出、图文并茂,便于读者理解与掌握本书适合于地理、地图、测量、城建等领域的广大研究人员和技术工作者阅读参考,也可作为地理学科、测绘学科及其他相关学科本科生、研究生的教学用书。图书在版编目(CIP)数据计算几何:空间数据处理算法/闫浩文,王明孝,王中辉编著.一北京:科学出版社,2012(地理信息系统理论与应用丛书)ISBN978-7-03-036015-1I.①计…Ⅱ.①闰…②王…③王…Ⅲ.①计算几何-应用空间测量数据处理Ⅳ.①018②P236中国版本图书馆CIP数据核字(2012)第268481号责任编辑:韩鹏朱海燕吕晨旭/责任校对:刘亚琦责任印制:钱玉芬/封面设计:王浩斜学版社出版北京东黄城根北街16号邮政编码:100717http://www.sciencep.com新科印刷有限公司印刷科学出版社发行各地新华书店经销2012年11月第一版开本:787×10921/162012年11月第一次印刷印张:123/4字数:302000定价:59.00元(如有印装质量问题,我社负责调换)前言早在2000年笔者撰写博士学位论文时就已经产生撰写本书的想法。当时,笔者在做空间关系理论问题的研究时,就发现地图上目标之间的空间关系计算问题,即在许多情况下都需要借助于凸包、 Delaunay三角网、 Voronoi图等来实现,而查阅当时的文献,中、外文书籍数量了了,于是心中闪过撰写本书的念头。后来,笔者在香港理工大学和瑞士苏黎世大学进行地图自动综合方面的研究时,发现计算几何在地图综合的空间描述和算法设计中应用同样广泛,这更加剧了笔者撰写本书的冲动。因此,从2006年开始,笔者尝试在兰州交通大学地图学与地理信息系统专业为硕士研究生开设了两门相关的课程:“计算几何”和“地图数据智能化处理”,这使得笔者有机会投入专门的精力为本书写作积累资料心得和人力支持。经过近5年多的探索,笔者大致理清了本书的思路。于是,在2011年上半年,笔者撰写了本书的提纲,邀请了王明孝博士、王中辉博士作为合作者,共同启动了本书初稿的撰写。本书的撰写有两个目的:一是综括计算几何在空间数据处理算法方面的最新研究成果,为地图学、地理信息科学等领域的科研人员提供方法和技术手段;二是比较系统地论述计算几何的基本原理及其在空间数据处理中的经典算法,为地理信息学科的高年级本科生、硕士和博士研究生提供课本或课程参考资料。因而,本书在组织上着重于系统性,内容上强调新颖性为了论述上的系统性,本书在第1章提出并回答了计算几何与空间数据处理的关系问题,为后续各章的展开进行了导引;然后在第2章介绍了计算几何的基元和相关算法为把计算几何算法应用到空间数据处理中奠定了基础。接下来进入了本书的重点章节依据计算几何在空间数据处理中的不同作用,把这些算法归为4类,分别是:第3章“空间分析与空间查询算法”;第4章“空间数据可视化算法”;第5章“空间关系表达算法”;第6章“地图自动综合算法”。最后,第7章对全书进行了总结和展望。本书的新颖性体现在4个方面。其一是书中的引文追求时效性,即针对某一具体问题的论述,尽量引用最近期的研究成果;其二是把计算几何和空间数据处理结合在一起进行系统论述的构想,到目前为止为本书所仅见;其三是书中给出了一个全新的计算几何在空间数据处理中的算法分类体系;其四是本书的第7章列出了计算几何在空间数据处理中潜在的研究方向,以便同行学者寻找感兴趣的研究课题本书撰写的具体分工如下:前言、第1章、第6章和第7章由闫浩文撰写;第4章的第4、5节和第5章由王明孝撰写;第2章、第3章和第4章的第1、2、3节由王中辉撰写。全书由闫浩文统一组织和统稿。本书的出版得到兰州军区信息工程科技创新工作站、国家自然科学基金(40871208)863重大项目(2009AA121404)、教育部创新团队资助计划(RT0966等的支持。本书完成后的初稿,曾在兰州交通大学地图学与地理信息系统专业2011级研究生中试用。期间,张宁、窦鹏、李双元、易珍言、程亚辉等同学在文字方面进行了修订,在此表示诚挚的谢意。特别感谢科学出版社领导和韩鹏先生在本书编辑出版中付出的辛勤劳动。把计算几何理论和空间数据处理的实践结合在一起进行系统论述是空间信息科学中极具挑战性的课题。囿于作者的学识与经验,本书撰写虽然尽心尽力,但论述问题不免挂一漏万,遣词造句可能贻笑大方。文责尽在作者,欢迎同行批评指正。闫浩文2012年2月目录前言第1章绪论…1.1计算几何的概念1.2计算几何的缘起与发展11231.3从空间数据处理到计算几何算法……1.4本书的组织和约定主要参考文献。。0。0第2章计算几何基元及算法0002.1多边形2.2凸壳2.3 Voronoi图和 Delaunay三角网●。0。指24曲线拟合……242.5图论…………………………………………………………27主要参考文献第3章空间分析与空间查询算法…323.1空间目标捕捉算法…………………………………………………323.2叠置分析算法353.3缓冲区分析算法363.4空间网络分析算法…413.5空间查询算法47主要参考文献…0●56第4章空间数据可视化算法…584.1等值线引绘算法584.2图形开窗算法……………………………634.3地图矢量符号(库)算法704.4地图注记自动配置算法……824.5曲线光滑算法………92主要参考文献……101第5章空间关系表达算法●。·4·中·非·非。音。自。非量…………………10351空间距离关系计算…1035.2空间拓扑关系计算…………………………………………1075.3拓扑多边形自动生成算法。。0。01175.4空间方向关系计算…………1225.5多尺度地图空间相似关系……………………………143主要参考文献……147第6章地图自动综合算法………………1496.1点群综合算法………1496.2等高线综合算法1576.3道路网综合算法……………1696.4居民地综合算法177主要参考文献….。.。。。。.0000。。。192第7章结束语…………………………………195第1章绪论让我们用一个简单的事例开始本书的论述。设想你是—一个大学新生,初次进入陌生的大学校园,炎热难耐之际,想要在校园找个地方购买冷饮。学校里面零零落落地分布了数个冷饮小店。此时,你从哪里知道这些冷饮店的位置,并确定距离你最近的一个呢?一张校园地图无疑是非常合适的选择。在校园地图上,你可以很快确定自己的位置,明白你所在的校园分区,进而用简单的判断确定最佳的冷饮店位置(图1.1)。图1.1借助校园地图寻找冷饮店大学新生借助地图寻找校园冷饮店的过程,如果换作机器人来自动实现,就包含了障碍物的识别、最短路径搜寻和计算等问题。简言之,该类问题可归纳为借助于计算机算法对几何图形进行计算的范畴,即属于计算几何( Computational Geometry,CG)所研究的问题。计算几何的产生只有短短30多年的历史,但其发展势头极其迅猛,应用范围也非常广泛。目前,计算几何已成为计算机辅助设计、计算机辅助制造、运动规划、空间数据挖掘、图像处理、地图自动综合等领域的重要研究手段1.1计算几何的概念计算机科学( Preparata and Shamos,1988)和几何学(罗钟铉等,2010)的学者从各自的研究角度出发,均认为计算几何是自己学科的发展分支,从而各有侧重地对计算几何进行了定义。总括这两类定义,可以认为:计算几何是研究几何图形(或数据、模型)的计算机存储、表达、分析、综合、管理和处理等的理论与技术的总括。由于计算几何更偏重于算法的研究,因此,在许多情况下计算几何也被称为算法几何学( Algorithmic Geometry)或者几何算法学( Geometric Algorithms)显然,计算几何的研究对象是几何形体和几何数据,借助的工具是计算机相关学科,目的是实现图形处理的自动化和智能化(图1.2)几何学、图论数据结构、算法、学科基础计算数学等模式识别等计算几何计算机辅助制造、计算机辅助设计、图像处理、地图制图、城市规划、交通规划与管理…应用领域图1.2计算几何的相关学科及计算几何的应用领域1.2计算几何的缘起与发展计算几何的“影子”可从20世纪60年代进行的样条曲线光滑、组合几何学等中窥见斑。 Minsky与 Papert在1969年出版的著作 Perceptrons: An Introduction to Compitational geometry中最早提出“计算几何”这一术语,并进行了较为系统的论述。该书的出发点是模式识别。随后, Forrest(1971)在一篇名为“ Computational geometry”的会议论文中论述了几何曲线和曲面的建模问题。真正对当代计算几何学产生重大影响的标志性事件之一,应该是 Shamos于1978年在耶鲁大学的博士学位论文“ Computational geometry”及其前后公开发表的一系列论文。他对计算几何的基本概念、工具和一些算法如最近点问题、相交问题)进行了研究并给出了非常出色的解答。由于 Shamos的突出贡献和他本人的计算机学科背景,后来者多把计算几何归结为理论计算机科学( Theoretical Computer Science)F中的算法理论( Algorithm Theory)的一个分支。从20世纪80年代开始,计算几何的研究在世界范围内进入了一个非常活跃的时期。典型的事件,如1983年,关于计算几何的第一个国际学术研讨会召开;1985年,关于计算几何的第一个国际学术大会( Annual Symposium on Computational Geometry)召开,并规定此大会每年举行1次;也是在这一年,第一本计算几何的教科书出版( Shamos and Preparata,1985)。计算几何在中国的起源和发展几乎和世界同步,但是中国学者最初的研究方向却与其他国家有很大差异。1980年,我国著名数学家苏步青、刘鼎元出版了《计算几何》书。他们从计算机辅助设计的角度对样条曲线、样条曲面的光滑和变换问题进行了系统阐述;虽然这可视为计算几何在中国起源的标志性成果,但很显然,其着眼点与彼时的国际潮流并不一致。相比较而言,周培德(2000)撰写的著作《计算几何—算法设计与分析》,其内容及研究手段、研究思路、应用领域等与国际上计算几何研究的主流较为吻合。虽然,计算几何在中国已经得到了深入的研究和广泛的应用,也有部分高校开设了专门的计算几