（地图学与地理信息系统专业论文）gis中的计算几何算法研究.pdf

中南大学硕士学位论文 摘要 摘要 g i s 的内容主要包括：空间数据的获取，空间数据的表达，空间 数据的处理，空间数据的分析，空间数据的显示与可视化。而这些内 容的实现将用到许多计算几何中基本算法。 计算几何是理论计算机科学领域中一个新的极有生命力的子领 域，计算几何的研究成果已在空间分析，计算机图形学，化学，统计 分析，模式识别，地理数据库以及其他许多领域中得到了广泛的应用。 计算几何研究的典型问题有几何基元( g e o m e t r i cp r i m i t i v e s ) 、查 找、优化等问题类组成。其中，几何基元包括凸壳和v o r o n o i 图，多 边形的三角剖分、划分问题与相交问题。几何查找包括点定位，可视 化、区域查找等问题。 在几何基元中的凸壳和三角剖分的算法研究过程中，本文发现了 当前简单多边形凸壳的主流算法存在的错误，并加以改正，使得改正 后的算法更加合理，效率更高；本文还提出了基于径向扫描排序和凸 壳技术的散乱点的d e l a u n a y 三角网生成算法。该方法在得到散乱点 的三角网的同时得到了该三角网的凸壳。同时根据该算法推导出一个 三角形个数、离散点的个数及凸壳上的点的个数三者之间的一个关系 式，并通过实验验证了该关系式的正确性。 在几何查找中的算法研究中，本文对其中一个重要的点定位算法 点在多边形内外检测算法进行了改进，提出将矢量和射线法结 合，解决了射线法所具有的奇异情况。当对同一个多边形需要多次进 行内外检测时，提出了一个基于单调链判断点在多边形内外的方法。 该方法的预处理简单。实验结果证明，该方法具有易实现和效率高等 优点。 关键词计算几何，d e l a u n a y 三角网，凸壳，点在多边形内外 判断算法 中南大学硕士学位论文 a b s t r a c t a b s t r a c t t h ec o n t e n to fg i si n c l u d e s ：t og a i ns p a t i a ld a t a ，t oe x p r e s ss p a t i a l d a t a ，t op r o c e s ss p a t i a ld a t a ，t oa n a l y s es p a t i a ld a t a ，t od i s p l a ya n d v i s u a l i z a t i o ns p a t i a ld a t a f i n i s ht h e s ee l e m e n t ss h o u l du s em a n yb a s i c a l g o r i t h m so fc o m p u t a t i o n a lg e o m e t r y c o m p u t a t i o n a lg e o m e t r yi s an e ws t r o n gv i t a l i t yo ft h ef i e l do f t h e o r e t i c a lc o m p u t e rs c i e n c e ，t h er e s u l to fr e s e a r c h i n go nc o m p u t a t i o n a l g e o m e t r yh a sb e e nw i d e l yu s e di ns p a c ea n a l y s e ，c o m p u t e rg r a p h i c s ， c h e m i c a l ，s t a t i s t i c a la n a l y s i s ，p a t t e mr e c o g n i t i o n ，g e o g r a p h i cd a t a b a s e a n dm a n yo t h e ra r e a s t h et y p i c a lp r o b l e m so fs t u d i n gc o m p u t a t i o n a lg e o m e t r ya r em a d e u po fg e o m e t r i cp r i m i t i v e s ，g e o m e t r yr e s e a r c h i n g ，o p t i m i z i n ga n do t h e r s t h e g e o m e t r i cp r i m i t i v e i n c l u d e sc o n v e xh u l l ，v o r o n o i d i a g r a m ， t r i a n g u l a t i o np r o b l e m s ，p a r t i t i o np r o b l e m sa n di n t e r s e c t i o np r o b l e m s g e o m e t r yr e s e a r c h i n gi n c l u d e sl o c a t i n gap o i n t ，v i s u a l i z a t i o n ，g e o m e t r y r e s e a r c h i n gi nar e g i o n a la n ds oo n w h e ns t u d i n gt h e a l g o r i t h mo fc o n v e xh u l l a n dt r i a n g u l a t i o n p r o b l e m s t h i sp a p e rf i n d sa ne r r o r i na ni m p o r t a n ta l g o r i t h ma n d i m p r o v e si t ；t h ei m p r o v e da l g o r i t h mi sm o r er a t i o n a l i z e da n de f f i c i e n t t h i sp a p e rg i v e so u ta na l g o r i t h mo fd e l a u n a yt r i a n g u l a t i o nt od i s c r e t e p o i n t sb a s e do nr a d i a l s w e e p i n gc o m p o s i t o ra n dc o n v e xh u l l ，w h i c hc a n e f f e c t i v e l yr e s o l v et h ed e g e n e r a c yp r o b l e ma n dc a ne d u c ea ne q u a t i o n ， v a l i d a t e db ye x p e r i m e n t s ，a b o u tt h en u m b e ro fd i s c r e t ep o i n t s ，t r i a n g l e s a n dp o i n t so nc o n v e xh u l l w h e ns t u d i n gt h ea l g o r i t h mo fg e o m e t r yr e s e a r i n g ，t h i sp a p e rp u t s f o r w a r d c o m b i n i n gv e c t o ra n dr a y c r o s s i n ga l g o r i t h m t or e s o l v e r a y c r o s s i n ga l g o r i t h m sa n o m a l o u sc a s e s ，i m p r o v i n gt h ea l g o r i t h mo f d e t e c t i o nap o i n tw h e t h e ri np o l y g o n w h e nt h ec o n d i t i o nn e e d i n gm u c h d e t e c t i o nt oo n ep o l y g o nc o m e so u t ，t h i sp a p e rp u tf o r w a r d sam e t h o do f p o i n ti n c l u s i o nt e s t f o rs i m p l ep o l y g o n sb a s e do nf o r k e dp o i n t t h e p r e p r o c e s so ft h i sm e t h o di sv e r ys i m p l ea n de x p e r i m e n tr e s u l t ss h o w n 中南大学硕士学位论文 a b s t r a c t t h a tt h em e t h o di ss i m p l ea n de f f i c i e n t k e yw o r d sc o m p u t a t i o n a lg e o m e t r y , d e l a u n a yt r i a n g u l a t i o n ， c o n v e xh u l l ，t h ea l g o r i t h mo fd e t e c t i o nap o i n tw h e t h e ri np o l y g o n i i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：曼磊盔日期：2 塑左年上月日作者签名：堕鱼茏日期：2 塑左年上月且日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：建殓叠 导师签名丝i , v 组望 日期：迦年上月上幽 中南大学硕士学位论文 第一章绪论 1 1 前言 第一章绪论弟一早三百t 匕 1 1 1g i s 中常用的几个计算几何算法 g i s 的内容主要包括【5 5 】：有关的计算机软、硬件；空间数据的获取；空间数 据的表达及数据结构；空间数据的处理；空间数据的管理；空间数据的分析；空 间数据的显示与可视化；g i s 的应用；g i s 的项目管理、开发、质量保证与标准 化等。而这些内容的实现和完成，将用到计算几何中许多重要的基本算法。 按照g i s 对数据进行采集、加工、管理、分析和表达，可将g i s 基础软件 分为五大子系统，即：数据输入与转换、图形与文本编辑、数据存储与管理、空 问查询与空间分析以及空间数据可视化与输出。 地表现象异常复杂。有自然地物和人文地物，各种地物形状各异、关系复杂。 但是在g i s 中人们将它们抽象，用数字表达可以归结为四大类：数字线划数据、 影像数据、数字高程模型和地物的属性数据。其中数字高程模型实际上是地表物 体的高程信息。由于高程数据的采集、处理以及管理和应用都比较特殊，所以在 g i s 中往往作为一种专门的空间数据来讨论。而数字高程模型的实现就主要用到 计算几何中的几何基元中d e l a u n a y 三角剖分算法。在数字地面模型建模中，不 规则三角网( t r i a n g u l a t e di r r e g u l a rn e t w o r k ，t i n ) 利用不规则分布的数据点生成的 连续三角面来逼近地形表面。从表达地形信息的角度而言，t i n 模型的优点【1 3 1 是它能以不同层次的分辨率来描述地形表面，即由于t i n 的三角形随点的密度 变化而变化，当点比较密集时生成的三角形小而密，稀疏时生成的三角形大而疏， 这与实际的地形特征恰好一致，所以t i n 被广泛使用。与格网数据模型相比， t i n 模型在某一特定分辨率下能使用更少的空间和时间更精确地表示更加复杂 的表面。特别当地形包含有大量特征线如断裂线和构造线时，t i n 模型能更好地 顾及这些特征线，从而更精确地表达出地形形态。 对于t i n 模型，其基本要求有三点【3 l 】： ( 1 ) t i n 是唯一的； ( 2 ) 力求最佳的三角形几何形状，每个三角形尽量接近等边形状； ( 3 ) 保证最邻近的点构成三角形，即三角形的边长之和最小。 目前已提出了许多构建三角网的算法，理论证明，在所有的构建三角网原则 中，d e l a u n a y 三角网在地形拟合方面表现最为出色。这是由于它具有两个非常重 要的性质( 空外接圆性质和最小角最大化性质) ，使得它可以最大限度地保证三角 中南大学硕士学位论文第一章绪论 网中的三角形满足近似等边性。文献【3 2 】从理论上证明了二维d e l a u n a y 三角剖分 具有最大的平均形态比，以及最小角最大准则和空圆准则具有等价性。 空间数据处理包含两方面的意义：一是将原始采集的数据或者说不符合g i s 质量要求的数据进行处理，以符合g i s 的数据质量要求；第二层意思是对于已 存储于g i s 中的数据经过处理以派生出其他信息，如进一步的空间关系的信息 或将一种类型的数据转化为另一种。在这些处理中，其中在多边形基本操作算法 中，将用到计算几何中判断点在多边形内外的算法。还有在许多情况下需要用到 图形的裁剪，包括窗口的开窗、放大、漫游显示、地形图的裁剪输出，空间目标 的提取，多边形叠置分析等，而这些对多边形进行裁剪时都可以用计算几何中的 凸壳方法来实现。 空间查询是g i s 的最基本最常用的功能，也是它与其他数字制图软件区别 的主要特征。空间查询的内容很多，其中空间定位查询是指给定一个点或一个几 何图形，检索该图形范围内的空间对象以及相应属性。其中很多查询方式( 按点 查询，按矩形查询，按多边形查询，包含查询，穿越查询，落入查询，缓冲区查 询) 都将用到计算几何中的判断点在多边形内外的算法，空间关系的查询也是的。 在空间查询中，当需要求最短路径时，也可用凸壳方法来实现，用凸壳算法先将 区域凸壳化，然后再求到区域凸壳边的最短距离。 在空间数据可视化研究中，也需用到点在多边形内外的算法，用来判断是不 是可见的。 1 1 2 计算几何的简介 1 9 7 5 年，s h a m o s ( 沙莫斯) 和h o e y ( 霍伊) 利用计算机有效的计算平面点集 的v o r o n o l 图，并发表了一篇著名论文，从此计算几何诞生了【。自那时以来该 研究领域取得了辉煌的成果，使得计算几何成为理论计算机科学领域中一个新的 极有生命力的子领域，并且，计算几何的研究成果已在计算机图形学，化学，统 计分析，模式识别，地理数据库以及其他许多领域中得到了广泛的应用。 计算几何【5 3 】研究的典型问题由几何基元、查找、优化等问题类组成【1 1 。 首先，几何基元包括凸壳和v o r o n o i 图、多边形的三角剖分、划分问题与相 交问题。矿1 中点集s 的下凸壳在中投影恰好是点集s 在中投影点的 d e l a u n a y 三角剖分，然后由d e l a u n a y 三角剖分可以容易地得到v o r o n o i 图。换 言之，v o r o n o i 图是凸壳的特例，因此构造矿1 中点集凸壳的算法也可以用于构 造点集的v o r o n o i 图。对多边形的三角剖分问题可以提出如下要求：设计复杂 度低的算法构造多边形三角剖分以及设计三角形最小角最大化的三角剖分算法； 分割线段长度之和最小的三角剖分算法。前者已有线性时间的算法。划分问题是 多边形三角剖分的推广，它要求把几何体划分成若干好的部分。所谓好的部分通 2 中南大学硕士学位论文 第一章绪论 常是指下述两个目标之一：划分成尽量少的凸部分；各凸部分最小角最大化。另 外，在几何体中可以加入s t e i n e r 点( 新的顶点) ，然后在进行划分，使得划分线 段长度之和最小化或者提出其他要求。二维中典型相交问题是：给定平面上n 条线段，确定所有相交线对。三维中的相交问题一般考虑两个凸多面体的交以及 两个多面体的交。 其次，几何查找包括点定位，可视化、区域查找等问题。计算机图形学、数 据库中的区域查找及地理图形中的点定位等都是几何查找中的典型例子。在平面 细分中定位一个询问点或者在( d 大于等于3 ) 内由n 个超平面构成的结构中 定位询问点的问题是一个典型问题，现在不仅有解决这个问题的确定型算法，而 且设计了动态随机增量算法。给定平面上n 个顶点的简单多边形p ，由点口向任 一方向引射线，确定川亏尸相交的第一条边，这个问题的解决为可视化问题的 求解提供了前提。中给定点集s 及区域集合b ，b 属于b 要求在b 中查找s 中 的点，这是区域查找问题。 再次，几何优化包括参数查找和线形规划。参数查找技术是将一个优化问题 的检验算法变成寻找解的算法，它必须满足某些条件( 检验算法是可以并行的) 并且具有广泛的应用性。 此外，计算几何中各种问题的下界的确定，推导下界的方法以及求解各种几 何问题的算法的复杂性分析等，也是计算几何研究的重要内容。 计算几何的新近发展包括几何抽样理论、计算实代数几何、计算拓扑、运动 规则、并行计算几何、隐藏面的移动、结构和图形、网格生成以及计算机视觉中 的几何问题等。计算机在各学科领域深层次的应用将为计算几何提出更多的研究 问题，反之，计算几何的研究成果也将促进这些学科的进一步发展。 本文主要针对几何查找中的判断点在多边形内外、几何基元中的凸壳问题、 和d e l a u n a y 三角网生成等部分基础算法进行研究。 1 2 研究内容和现状 本文主要研究内容包括：点在多边形内外判断算法、d e l a u n a y 三角网生成算 法( 散乱点d e l a u n a y 三角网生成算法) 和凸壳生成算法( 散乱点凸壳生成算法 和简单多边形凸壳生成算法) 等的研究。 1 2 1 点在多边形内外判断算法 判断点是否在简单多边形内1 7 h 2 9 1 是计算机图形学的最基本算法，在计算机 图形处理、模式识别、c a d 及科学计算可视化中有着广泛的应用。 点在多边形内外关系判断的经典方法【1 7 1 1 9 】主要有射线法和角度和法。 中南大学硕士学位论文第一章绪论 射线法：在工程上应用最多的是定向射线法，这种方法简单，但其难以处理 边界点在射线上、边界与射线共线等奇异情况。从检测点向右水平发出一条射线， 求出多边形上每条边与射线的交点，如果交点个数是偶数则在多边形外，奇数在 多边形内。但是它存在以下几个弊端：如果这条射线恰好与这条边重合了，交点 个数怎么算；如果多边形上的顶点落在射线上，交点个数算1 个还是2 个等问题。 常见的解决方法：若多边形的边落在射线上，则将这条射线向上微移。不过不少 人觉得这样做很不放心，而且很容易导致判断结果错误。由于多边形上的每条边 需要与射线进行求交，计算量非常大。 角度和法：将检测点与多边形上的任意一顶点相连，从该顶点按照顺时针顺 序旋转，旋转的极角累加，如果等于3 6 0 度就是在多边形内、0 度则在多边形外， 介于两者之间即为多边形边上。这种方法很完美，但代价是其中计算除法和 a f c c o s 的速度太慢，大约比射线法慢2 0 倍，而且a r c o $ 计算存在比较大的误差。 近年来，人们提出了代数判别法【1 8 1 、不需要任何先决条件的判另l j 算法1 2 1 1 、 基于可见边的点在多边形内外判别法【2 8 h 2 9 1 ，这些方法主要从可靠性、计算量等 方面进行了改进，但仍需对多边形的每条边进行处理。文献 2 2 1 提出：通过预处 理，将多边形的边进行层次化组织，检测时不必处理多边形的每条边，但其预处 理的时间复杂度达o ( n l o g n ) ，算法复杂，不易实现。 1 2 2d e i a u n a y 三角网生成算法 d e l a u n a y 三角剖分经过长期的研究，国内外已有很多成熟的生成算法，大致 可以归纳为如下几类【3 l j ： ( 1 ) 分而治之算法：该算法由l e w i s 和r o b i n s o n 提出，其基本思想是将原始 的数据排序，分成两个互不相交的子集，在每一子集建立三角网后，将两个三角 网合并以生成最终的d e l a u n a y 三角网。后来l e e 和s c h a c h e e r l 3 5 1 ，r e xad w y c r 和a n d r el t 37 j 对其做了改进。 ( 2 ) 渐次插入算法：首先用一个超三角形或矩形结构包含所有的数据点，然 后从数据中取出一点p 加入到三角网中，搜索包含点p 的三角形，将p 与此三角 形的三个顶点相连，形成三个三角形，应用l a w s o nl o p 从里到外更新所有生成 的三角形，直至所有的点都被加入到三角网中，然后再删除所有包含一个或多个 超三角形顶点的三角形。后来l e e 和s c h a c h e e r t 3 卯，刘学军【3 引，杨钦3 9 1 等先后对 该算法进行了发展和完善。 ( 3 ) - - - 角网生长算法：以任意一点为起始点，找出与该点最近的数据点连接 成d e l a u n a y 三角形的一条边，并将该边作为基线，根据d e l a u n a y 三角网的判别 法则，找出与基线构成d e l a u n a y 三角形的第三点；将基线的两个端点与第三点 相连，成为新的基线；重复以上两步直至所有基线都被处理。c h u a n c h uk u o 4 0 1 4 中南大学硕士学位论文 第一章绪论 等先后对该算法进行了改进和发展。 另外还有很多学者在上述三种主流算法的基础上，提出了改进的算法，如武 晓波幽】在分冶算法与逐点插入法的基础上提出了合成算法，潘志庚和刘强提出 了基于最小二叉树理论的三角网生成算法等。 1 2 3 凸壳生成算法 凸壳是计算几何中最普遍、最基本的一种结构。不仅它自身具有许多特性， 而且它还是构造其他几何形体的有效工具。在应用中，许多问题可以归结为凸壳 问题。凸壳是物体形状描述、特征抽取的一个重要工具，已被广泛地应用于计算 机图形学、图象处理、设计自动化、模式识别和运筹学等研究领域【2 】。如机器人 学中，一个物体相对于另一个物体无限移动，而不发生碰撞的可移动方向区域的 确定，以及图形可视性问题的研究，都可转化为判断两个简单多边形物体的凸包 是否相交。 凸壳问题可以分为基于离散点集和基于多边形两类。求取点集凸壳不仅要从 大量的离散点中判断出凸壳顶点，还要得到这些点之间的连接关系。由于简单多 边形的顶点已按某种规则连接起来，只需要排除凹顶点即可得到其凸壳，因此， 多边形可以看作点集情况的特例。 关于寻求平面点集凸壳的算法有很多【3 h g ，从大体上来说寻求平面点集凸壳 的主要算法包括卷包裹法，格雷厄姆方法，分冶算法，实时凸壳算法，增量算法 及近似算法，其中文献【8 】证明了平面点集的凸壳算法时间复杂度下界为 o ( n l o g n ) 。 卷包裹法：该算法的主要依据是凸壳的定义：凸多边形的各顶点必须在该多 边形的任意一条边的同一侧。由c h a n d 和k a p u r 于1 9 7 0 年提出，基本思想是： 首先过y 坐标最小的点p l 画条水平直线三显然该点是凸壳的一个顶点。然后 绕p l 按逆时针方向旋转，碰到s ( 顶点集合) 中的第二个点及时，直线绕见按逆 时针旋转而在p l ，p 2 之间留下一条线，该线段为凸壳的一条边。继续旋转下去， 最后直线l 旋转3 6 0 度回到p l , 便得到所求的凸壳。直线上绕点p 。旋转是通过以 下方法实现的：首先连接a 与非凸壳顶点历，= i + l ，刀，得到线段p , p j ，然后求 这些线段与( 线段p _ f - i p f ) 的夹角，组成最小夹角的另一端点辟l 就是凸壳顶点。 显而易见，该算法的时间复杂度为o ( 矛) 。在实现时，需要注意一点：当有三点 或者三点以上共线时，如果只能算两个端点上的点，中间的其他点不计，在算法 执行中要选择距离最远的一个点。 格雷厄姆方法：1 9 7 2 年，格雷厄姆发表了一篇题为“a ne f f i c i e n ta l g o r i t h mf o r d e t e r m i n i n gt h ec o n v e xh u l lo f af i n i t ep l a n a rs e t 的著名论文，这是计算几何领域 中具有重要意义的早期卓越成果，文中所提出的方法称为格雷厄姆方法。此方法 中南大学硕士学位论文第一章绪论 主要思想是：假设凸集中y 坐标最小的点为p l ，把p l 同凸集中其他各点用线段连 接，并计算这些线段与水平线的夹角。然后按夹角大小及到p l 的距离进行词典 式分类，得到一序列p l , p 2 ，肌，依次连接这些点，便得到一个多边形。然后 删去p l , p 2 ，胁一l 不是凸壳顶点的点，最后顺序输出凸壳顶点。格雷厄姆方法 是求解平面点集凸壳问题的最佳算法。 分冶算法：p r e p a r a t a 和h o n g ( 1 9 7 7 ) 把分冶技术首先应用于凸壳问题。主 要思想是：把点集s 分成两个大小近似相等的子集和，然后分别递归寻求 子集s l 和的凸壳，最后合并这两个子集凸壳，得到点集s 的最终凸壳。 简单多边形凸壳问题是平面点集凸壳问题的特殊情况。由于简单多边形的顶 点已按顺时针或逆时针方向串起来，因此可以根据其特殊情况设计出精巧的算法 来，而无需照搬平面点集的凸壳算法。现有许多简单多边形凸壳算法错误崃删引腓。 【”】均称能达到线性时间复杂度，但由于任意多边形的项点不是有序地排列( 如 按x 坐标递增的原则排列) ，从而导致算法极易出错【2 1 。文献【1 4 】提出了一种简单 多边形凸壳算法，文献 1 5 】马上举出一个反例证明其所提出的算法错误。文献 1 6 】 提出了寻求简单多边形凸壳的线性时间的算法，但其时间复杂度分析错误。 1 3 论文的组织 本文主要涉及计算几何的部分算法研究，主要内容有：判断点在多边形内外、 d e l a u n a y 三角网生成和凸壳( 散乱点凸壳和简单多边形凸壳) 生成等方面的研究。 本论文各章的内容简介如下： 第一章主要概述了本文研究内容的国内外研究现状。 第二章主要论述了点在多边形内外判断算法。在现有算法的基础上，提出了 改进算法。本算法时间复杂度为o ( m l o g n ) ( m 为单调链条数，n 为平均每条单 调链的多边形顶点数，多边形的顶点数= m 幸n ) 。通过实验验证，改进后的判断 点在多边形内外的算法在时间复杂度方面比现有的算法都优越，且易实现。 第三章主要论述了d e l a u n a y 三角网生成算法。在现有算法的基础上，提出 了一个基于凸壳技术的散乱d e l a u n a y 三角网生成算法，证明该算法的时间复杂 度达到理论上的下限o ( n l o g n ) 。 第四章主要论述了简单多边形凸壳生成算法，本文通过反例证明了文献【1 1 】 所提出的算法值得商确，并提出了改正的算法，同时证明本文所提出的改正算法 时间复杂度为o ( n l o g m ) 。 第五章是全文的总结。 6 中南大学硕士学位论文第二章判断点在多边形内外的算法研究 第二章判断点在多边形内外的算法研究 判断点在多边形内外【1 8 卜【冽是计算机图形学的最基本算法，在计算机图形处 理、模式识别、地理信息系统( g p s 中点定位) 、c a d 及科学计算可视化中有着广 泛的应用。判断点在多边形内外的算法主要有定向射线法、角度法。角度法要使 用复杂的三角运算，计算量大；在工程上应用最多的是定向射线法，这种方法简 单、可靠，但是，这种方法其难以处理对边界点及边界与射线共线等特殊情况。 人们提出了基于可见边的点在多边形内外的判断【2 1 】，网，【2 明可以缩短检测处理所 需要的时间等方法。这些方法主要从可靠性、计算量等方面进行了改进。文献 2 2 】 提出通过预处理，将多边形的边进行层次化组织，检测时不必处理多边形的每条 边，但其预处理的时间复杂度达o ( n l o g n ) ，算法复杂，不易实现。本文所提出的 方法是将有向角和射线法结合起来，解决了射线法所具有的奇异情况，具有简单、 快速、易实现等优点。 2 1 基本概念 定义2 - 1 由平面上若干条线段异，只最，只围成的封闭有界域称为 多边形。其中线段z & ，( - - 1 ，2 ，y ；r + t = p i ) 称为多边形的边，相邻的两 条边仅在端点相交，其交点只称为多边形的顶点。 定义2 - 2 多边形中具有共同端点的边成为相邻边。若多边形中不相邻的边不 相交，则称该多边形为简单多边形。 定义2 - 3 与同一顶点a 关联的两条边办一。b ，b b + 。形成的位于多边形内部 的角龟一t b b + t 称为多边形的内角。 2 2 点在多边形内外算法研究 算法2 - 1 点在多边形内外检测的算法描述如下： 设o a 、o b 是非零矢量，将o a 绕点d 旋转到与o b 方向相同的位置时，所 形成的角z a o b 称为有向角。规定逆时针旋转为正方向，顺时针旋转为负方向。 设线段s 的两个顶点为a 和b ，则j 与直线，所形成的关系可划分为三大类： ( 1 ) s 有且仅有一个顶点( 口或者6 ) 在，上，称这种关系为半跨越；( 2 ) s 的两个顶 点a 和b 分别在，的两侧，称这种关系为跨越；( 3 ) 墨的两个顶点口和b 在，的同 侧或线上，称这种关系为未跨越。 7 中南大学硕士学位论文第二章判断点在多边形内外的算法研究 ， p l 图2 - 1 射线与边相交的特殊情况 过点q 作石正方向的水平射线，。若线段s 跨越( 或半跨越) 射线，且与点q 所成的有向角么口缈为正，称为正向跨越( 或正向半跨越) ，否则称为负向跨越( 负 向半跨越) 。如图2 1 ，线段p j 乃、b n 、 岛、弦7 都属于正向半跨越直线z ， n p 3 、岛r 属于负向半跨越直线，线段p 鼎属于负向跨越直线，线段尸8 乃、 尸矿j 属于未跨越直线，。设线段s 与射线，交于点七，那么线段s 可以看作线段 础，勋组合而成( 如图2 1 中的p z p 8 可看作由p 7 k 、k p s 矢量和) 。若将s 与，的 关系用a s ，d 的值来表示其权重，如下表示： f ( s ，) = i正向半跨越 一1 负向半跨越 0 未跨越 ( 2 - 1 ) 2 正向跨越 - 2 负向跨越 定理2 1 过平面上任意一点印作x 正方向的水平射线，若y 厂( 墨，) = 0 ， 备 则点国在多边形p 外。 证明：设射线，与多边形尸的s 交点为岛，且岛不属于多边形p 的顶点， 则将交点分别插入到只、尸之间形成两条有向线段p 尚、毛只+ j 。将所有此类交 点都添加进到顶点序列中，形成一个新的多边形p ，顶点序列为p o 、只、 匆、p t + j 、厶、缸、p 辨小岛( 叫，d ) ，如图2 - 2 ( a ) 形成的顶点序列为n 、尸卜局、 乃、乃、尸d 。因此多边形尸的有向线段与射线j 的跨越情况全部转换为半跨越， 如图2 2 ( b 、c 、d 、e ) 四类情况。若将点口与多边形p 的各个顶点相连，组成一 系列有向角。设多边形p 以岛作为有向线段终点的有向边记为b ，以岛作为有 向线段起点的有向边记为e 柚在多边形尸中任选一个在射线，上的点岛作为起 始点，则每两个交点之间的所有有向线段所组成的有向角的代数和为s u m a n g l e = 厂( q ，) + 厂( 包+ l ，) ，如图2 2 ( b 、c ) 所示可知s u m a n g l e = 2 或2 时，有向角和为 3 6 0 或3 6 0 ：如图2 - 2 ( d 、e ) 所示可知s u m a n g l e = 0 时，有向角和为0 。显然可以 得出f ( s ，z ) = 0 时，有向角的角度代数和为o ，所以点q 在多边形p 外，因p 与尸耐构，因此，点q 在多边形户外。 中南大学硕士学位论文第二章判断点在多边形内外的算法研究 = = = 够毒 i 一 ( 8 )( b )( c )( d )( e ) 图2 - 2 射线与多边形的跨越关系 定理2 - 2 过平面上任意一点q 作z 正方向的水平射线，若( 墨，) 的值 t - - o 为2 或者一2 ，则点句在多边形p 内。 n - i 证明过程与定理2 - 1 证明类似，可以得出f ( s j ，) 值为2 或者一2 时，有向 i = 0 角的角度代数和为3 6 0 或者- 3 6 0 度，从而可以得出点q 在多边形尸内。 算法2 1点在多边形内外检测的算法描述如下： ( 1 ) 获得一个点只相对与点国的位置，如果p ，的y 坐标值大于国的y 坐标值， s t a t u s - - - 1 ，若小于，则s t a t u s = 1 ，否则s t a t u e = o ；用l a s t s t a t u s 记录上一点的相对 位置值。c n t 表示a s f ，d 的代数和。 ( 2 ) t e m p = s t a t u s l a s t s t a t u s ； i f ( t e m p z e r o ) 正向 近点口在有向线段b j 尸f 的右侧) 正向跨越 c n t 。c n t + t e m p ； e l s ei f ( 点q 在有向线段b 一，只上) r e t u r n ( “点口在有向线段只一，b 上) ； ) e l s ei f ( t e m p q x p i x 9 x ) i i ( 尸- ，x q x ) ) 点句在有向线段b j b 上 r e t u r n ( “点q 在有向线段只一只上”) ； ) l a s t s t a t u s = s t a t u s ；脯当前点的位置作为下一个输入点的上一点的位置 ( 3 ) 循环( 2 ) ，直到多边形所有的顶点遍历完毕， i f ( c n t 一0 ) r e t u m ( “点在多边形外”) ； e l s er e t u m ( “点在多边形内”) ； 射线法的复杂度为d ( ，z ) ，本算法的复杂度也为d ( 门) 。射线法中对每一条边 都要进行两次以上的乘法运算，而本算法只对跨越或者半跨越射线的边最多进行 一次叉积运算；射线法需要对奇异情况进行特殊处理，而本算法解决了奇异情况 的发生。在本文中，最坏的情况，即所有有向线段都负向跨越射线j ，所需的计 算量为( 8 次加减运算+ 2 次乘法运算) 木1 7 。本算法和射线法一样，都能够运用在 包含环的多边形判定。显然，同其他算法相比较，本算法具有计算量小、稳定性 和可靠性高、易实现等优点。 算法2 2 基于单调链的点在多边形内外判断的算法描述： 当需要判定的点的数目为m 时，采用前述方法进行逐点判定的时间复杂度 为o ( m n ) 。如果只需要判定一个点或少数几个点是否在多边形内，该算法是可 取的；如果m 较大，时间代价o ( m n ) 对于许多应用问题来说是难以接受的。 本文提出了一个基于单调链的判断点在多边性内外的判断方法。 图2 - 3 基于单调链的多边形分解 点历、p f 、p i + i q p j + t y = = p ， 胁+ ，如图2 3 的p 6 ，p l o 所示； ( 2 ) p j y p i + i y ，如图2 3 的尸j ，尸9 所示。 点p f ，、p i 、p 件1 是多边形尸的三个相邻顶点，检测点q 是平面上任意一点， 1 0 中南大学硕士学位论文第二章判断点在多边形内外的算法研究 若p ，是q 的相关点，当且仅当满足以下任意一个条件： ( 1 ) 若p i y p i y ，边p p u l 称为检测点q 的相关边； 引理5 1 石，办j 是多边形p 的两个相邻的极点，p k ( 7 ) ，p k + ，p k + 脚所+ j ) 是多 边形p 的顶点序列，则该序列关于y 值单调。 证明： 假设p j i q t ) ，p k + j ，p k + 肘( 瓜，) 不关于y 值单调，则必存在一个顶点 p k + 疗( n p k + n p k + n + j 或p 七+ n - l p k + 矿m + 一+ ，根据极点定义可知，肌+ 疗 是多边形p 的一个极点，与假设矛盾。证毕。根据极点，我们可以将整个多边 形划分为若干条单调链表组成( 见图2 3 ) 。 基于单调链的判断点在多边形内外的方法主要由两部分组成：( 1 ) 预处理过 程，求出多边形的所有极点；( 2 ) 检测过程，它根据相邻两个极点之间的多边形 顶点序列具有单调性，采用折半查找找到相关点和相关边，根据被检测线穿过的 相关边数就可以得出检测点是否在多边形内。 ( 1 ) 预处理过程：获得多边形尸的所有极点，将极点按顺序存储到数组尸中。 ( 2 ) 检测过程： 用f o r k c n t 表示极点链表f l i s t 中极点的个数，用p l i s t 饼，矗) 表示极点石 和瓜j 之间的多边形p 的顶点序列。 根据检测点q ，生成一条平行于x 轴的射线，射线方向为x 轴正方向； 令l a s t f o r k = f l i s t f o r k c n t 1 】，i = o ，c n t - - o ； 若i 。其中，只称 为矿( 只) 的生长点；y ( 只) 的公共边称为v o r o n o i 边，嘲的公共点称为v o r o n o i 顶点。v o r o n o i 图具有以下几大重要特征【4 l 】：势力范围特性、线性特性和局域动 态特性。 定义3 2d e l a u n a y 三角形由三个相邻点连接而成，这三个相邻点对应的 v o r o n o i 多边形有一个公共的顶点，此顶点也是d e l a u n a y 三角形外接圆的圆心， 因此d e l a u n a y 三角网也称为v o r o n o i 图的对偶图。 可以换一个角度来礼节d e l a u n a y 三角网的定义，设三角形t 是点集p 的 d e l a u n a y 三角剖分，则r 应满足如下条件： ( 1 ) 丁中的任意两个三角形互不交叠，至多有一个公共顶点或一条公共边； ( 2 ) 点集内的每一个点都是三角形的顶点； ( 3 ) 每一个三角形的外接圆内不包含除三角形三个顶点外的其他点。 d e l a u n a y 三角网具有三条重要的性质： ( 1 ) 空外接圆性质：每个三角形外接圆均不包含除三角形三个顶点外的其他 点。通常把这个性质称作为空圆准则，它是构成d e l a u n a y 三角网的充要条件。 ( 2 ) 最小角最大性质：在d e l a u n a y 三角网中的任意两个相邻三角形形成的凸 四边形中，这两个三角形中的最小内角一定大于交换凸四边形对角线后所形成的 两个三角形的最小内角。 ( 3 ) 唯一性：对于给定的点集，其d e l a u n a y 三角剖分是唯一的。 文献【3 2 】证明了空外接圆性质和最小角最大性质是等价的，同时也具有平均 形态比最大。由于这两个性质，决定了d e l a u n a y 三角网具有极大的应用价值。 3 1 2 散乱点集d e i a u n a y 三角网算法研究 根据d e l a u n a y 三角网实现过程，把生成d e l a u n a y 三角网的各种算法分为三 类【3 1 】：分治法、数据点渐次插入法和三角网生长方法。分治算法效率虽高，但 相对复杂，且对内存要求较高；数据点渐次插入算法简单而且高效，在实际应用 中具有良好的表现。数据点渐次插入算法的关键在于维护三角形之间的拓扑关 系，利用拓扑关系可以有效地减少插入操作所需的时间。义献【4 2 】中提出了利用 凸壳特性来查找与插入点有关的三角形，采用该法进行三角剖分首先需要维护一 个凸壳链表，其次在查找与插入点有关的三角形的过程中需要查找凸壳链表。对 凸壳链表的维护和查找在很大程度上影响了三角剖分算法的效率。本文在上述算 法的基础上，提出一种新的算法。该算法首先对散乱点按有向角进行排序，以排 中南大学硕士学位论文 第三章d e l a u n a y 三角网生成算法研究 序后的点顺序为基础，利用凸壳特性快速将散乱点联结成三角网，最后利用拓扑 结构快速将其优化为d e l a u n a y 三角网。在联网过程中，充分利用了有序点子集 的凸壳特性，避免了所有的交点测试，从而保证了对散乱点集生成d e l a u n a y 三 角网的效率。本算法相对于三角网生长算法来说，最大的优点是： ( 1 ) 在三角网生长过程中，能够快速地确定哪些点不可能再次参与构成新的 三角形。原理很简单：当一个点位于已形成的凸壳之内时，此点已不可能再次构 成新的三角形。通过将点按一定的顺序排序后，动态修改排在当前点前的点所形 成的凸壳，很容易确定出哪些点不会再次参与其他新插入的点形成新的三角网。 因此，相对于三角网生长算法来说，大大的降低了搜索时间。 ( 2 ) 凸壳内部的三角网的边绝对不可能再次参与三角网的生成。 从上述的几点说明可以得知，算法的效率主要取决于凸壳的动态维护和插 入。本文所提出的算法相对于文献 4 2 1 来说，凸壳的维护相对而言更加简单、易 维护( 可以在常量时间内完成) 。 3 1 2 1 有关概念和定理 定义3 3 s 是平面区域d 上的一个点集，产 7 独：=