（模式识别与智能系统专业论文）室内移动导航系统的路径规划方法研究.pdf

摘要 随着科技的发展，导航系统已经成为人们日常生活的重要组成部分。为了在二些 陌生或复杂的室内环境中找到特别的地方、特定的人或目标，引起了人们对室内导航 系统的关注。由于室内这个特殊环境的影响致使室内导航系统与室外导航系统在某些 技术方面存在一些差异，本文结合存在的技术差异，重点研究了室内导航系统的路径 规划方法问题。进行的工作如下： 本文详细介绍了有限元划分方法d e l a u n a y = 角法，针对环境信息的处理问题， 对d e l a u n a y - - - 角法进行了改进优化，并对其进行仿真实验；在环境信息处理结果的基 础上，通过模型建立及数据分析，证明了添加剖分结点的d e l a u n a y - - 角法构造的路径 具有最短特性。 最后，对d i j k s t r a 算法和a 半算法进行了研究讨论，并在建立的室内路径图上对 d i j k s t r a 算法和a 枣算法进行实验仿真，仿真结果证明a 宰算法更为有效。 关键词：路径规划d e l a u n a y 三角法d i j k s t r a 算法a 幸算法室内导航 a b s t r a c t a l o n gw i t ht h et e c h n i c a ld e v e l o p m e n t ，t h en a v i g a t i o ns y s t e ma l r e a d yb e c a m et h e i m p o r t a n tc o n s t i t u e n ti nt h ep e o p l ed a i l yl i f e h e n c e ，f o rf i n d i n go u ts p e c i a lap a r t i c u l a rp l a c e ， p e r s o n ，o ro b j e c ti ns o m eu n f a m i l i a ro rc o m p l i c a t e di n d o o re n v i r o n m e n t ，p e o p l ea l s om o r e a n dm o r ep a ya t t e n t i o nt ot h ei n d o o rn a v i g a t i o ns y s t e m b e c a u s eo ft h ei n d o o re n v r i m e n t p a r t i c u l a r i t yc a u s et h eo u t d o o rn a v i g a t i o ns y s t e ms a v e ss o m ed i f f e r e n c e sw i t ht h eo u t d o o r g u i d a n c es y s t e mi nc e r t a i nt e c h n i c a la s p e c t t h i sa r t i c l ec o m b i n e dt h ee x i s t e n tt e c h n i q u e d i f f e r e n c ei nt h ei n d o o re n v i r o n m e n t ，a n dm a i n l ys t u d i e dt h em e t h o do ft h ep a t hp l a n n i n g u n d e rt h ei n d o o rn a v i g a t i o ns y s t e m t h ef o l l o w i n gi st h em a i nw o r k s ： t h i sp a p e rm a i n l yi n t r o d u c e dt h ed e l a u n a yt r i a n g u l a t i o nm e t h o do ft h ef i n i t ee l e m e n t d i v i s i o nm e t h o d ，u s e ss o m em e t h o dt oi m p r o v et h ed e l a u n a yt r i a n g u l a t i o nm e t h o d ，a n d c a r r i e so ns o m es i m u l a t i o ne x p e r i m e n t t h r o u g hm o d e l i n ga n dd a t a sa n a l y z i n g ，p r o v e dt h a t t h ep a t hw h i e l li sb u i l tb yt h ei m p r o v i n gt r i a n g u l a t i o nm e t h o di st h es h o r t e s tc h a r a c t e r i s t i c s f i n a l l y , t h i sp a p e rs y u d i e st h ed i j k s t r aa l g o r i t h ma n dt h ea 宰a l g o r i t h m ，a n dt h i s a l g o r i t h mi ss i m u l a t e di nt h ee s t a b l i s h m e n tp l a n n i n gg r a p hb yu s ，r e s u l t so fs i m u l a t i o n e x p e r i m e n tp r o v e dt h a tt h ea 宰a l g o r i t h mi sb e t t e rt h a nt h ed i j k s t r aa l g o r i t h m k e yw o r d s ：p a t hp l a n n i n gd e l a u n a yt r i a n g u l a t i o nd i j k s t r aa l g o r i t h m a 掌a l g o r i t h m i n d o o rn a v i g a t i o n 长春理工大学硕士学位论文原创性声明 本人郑重声明：所呈交的硕士学位论文，室内移动导航系统的路径规划方 法研究是本人在指导教师的指导下，独立进行研究工作所取得的成果。除文中 已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的 作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标 明。本人完全意识到本声明的法律结果由本人承担。 作者签名：缝磐砌仝年j 月4 同 长春理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“长春理工大学硕士、博士学位论文版 权使用规定”，同意长春理工大学保留并向中国科学信息研究所、中国优秀博硕 士学位论文全文数据库和c n k i 系列数据库及其它国家有关部门或机构送交学 位论文的复印件和电子版，允许论文被查阅和借阅。本人授权长春理工大学可以 将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印 或扫描等复制手段保存和汇编学位论文。 作者虢型浏l 哗年三月卑h 指导导师签名：毒翌l 她年土月乒同 第一章绪论弟一早瑁比 1 1 本文的研究目的和意义 出门在外，我们每个人都离不开导航。特别是在城市变化突飞猛进，城市的建筑 物不断增加，而且越来越高，很多大型建筑物内部的结构也更加紧凑和密集，有效的 导航就像一双明亮的眼睛，帮助我们用最短的时间，走最短的路，办最快的事。传统 意义上的导航信息都是从一张纸质的地图和一本厚重的城市网页上获得的。用双眼在 纷繁复杂的图符和文字中查寻我们的目的地，在繁琐的索引和目录中找到目的地等信 息，成为令大家烦恼的事。 为了人们在一些陌生或复杂的环境中找到特别的地方，特定的人或目标。例如包 括飞机场、会议室、展览厅、企业、校园、医院、博物馆等室内区域。引起了人们对 室内导航系统的关注，它可以引导使用者在一定的时间内使用一系列的方向序列找到 目的地。导航系统不仅可以用于在不熟悉的地方引导使用者，而且可以将程序用于导 航机器人引导视觉或身体上残疾的人通过某些环境中的安全通道。 现有的室外导航技术“1 己相当成熟，如室外车载导航系统2 1 、手机导航、手机+ g p s 接收器导航、p d a 手持导航等类型。这些均采用g p s 3 1 卫星信号来进行定位，利用导 航电子地图进行引导，结合相关的导航软件完成导航服务。但是，室内导航系统的设 计与室外导航系统在某些技术方面存在很多不同点： 首先，室内导航系统所能提供的坐标系和测量精度不同于全球定位系统g p s 所提 供的。但是利用现有g p s 系统进行室内定位时，由于射频信号穿透建筑物的墙壁后， 信号强度变得非常弱，并且室内障碍物较多，多径现象严重，因此g p s 系统在室内环 境中的定位结果并不理想。同时，为能够支持室内导航系统应用程序，需要提供室内 定位系统的空间边界的检测精度，它比精确的坐标估计更加重要。 其次，建筑物内的导航与道路系统的导航不同。室内移动设备没有一组明确定义 的路径可以任意的在环境中移动，而汽车只能彼限制在道路网上行驶。结果，用于绘 制室内原点到目的地的路径技术不同于在网路，i i 绘制实际路径。 最后，为在网路上使用而设计的电子数字地图4 1 和地理信息系统( g i s ) 5 1 的数据 库可以从商业资源或公共资源中获得，然而建筑物的地图和校园的地图则没有现成的 数据库可以直接提供。因为建筑物和校园的平面布置图不能表示成一种易t ：被室内导 航系统处理的数据形式，需要一套工具能自动处理创建的室内地图。 由于存在的各种原因，使得室内导航系统1 i 能将现在的室外导航系统直接转移到 室内复杂环境中，必须考虑再种条件限制。当前有关室内导航系统的研究还很少，大 部分室内导航系统均采用移动机器人“1 进行导航，但机器人领域本身枕存他很多且复 杂的问题需要研究解决；一些国家的实验室虽然对室内导航系统有所研究，但也只是 将其作为实验项目的一部分进行初步的设计和应用，处于探索阶段，所以实现室内导 航系统( 尤其是在国内) 更存在很多需要研究和解决的问题，有一定的发展空间。例 如：如何在室内提供优秀的定位信息；室内环境模导航图n 1 的设计；以及导航中需要 最短路径的路径规划算法等等，这些问题需要做进一步的验证和研究。 1 2 室内导航系统的国内外研究现状 到现在为止，室内导航系统的研究热点主要分为两类。第一类主要是开发和研制 室内定位系统，其代表性的研究项目有室内感知系统、上下文感知环境、智能教室等。 第二类用移动机器人的控制与避障实现导航任务，这种类型大家主要专注于问题复杂 的机器人本身的改进与研究，对导航系统本身的技术研究则忽略了许多。 首尔大学g p s 3 1 实验室的d o o h e ey u n 和h a e y o u n gj u n 做了相关室内导航系统的 研究，利用能够发射类似g p s 信号的电子仪器。这样可以将g p s 应用到室内环境，并 利用载波相位双差分进行测量。 凯立德移动导航系统是运行在智能手机或p d a 上，提供位置指示和导航、功能的 应用软件信息系统，该系统由导航软件和电子地图组成，硬件设备是智能手机或者 p d a ，辅助设备是g p s 信号接收器。 法国航天公司t h a l e s 表示，已在伦敦r e a d i n g 的实验室研发出一套室内定位系统 ( i n d o o rp o s i t i o n i n gs y s t e m ；i p s ) 。它利用一种新型的无线电信号一一超宽带技术，采用 r a d i op u l s e s ，消防人员可用来在冒烟的建筑物内，确定跟其它消防队员以及救火车的相 对位置。 我国自行研制的北斗卫星导航系统已具备区域导航能力，2 0 0 8 年该系统将首先应 用于北京奥运会，为北京奥运会的交通调度或场馆监控服务，并于2 0 1 0 年前在上海使 用。 介于室内定位技术和室外定位技术的差异性，对室内导航系统中的定位技术8 1 作 以下简单介绍。 ( 1 ) r a d a r 定位系统是由m i c r o s o f t 研究所在现有无线通信网的基础上开发研 制的。与其他室内定位系统相仿，该系统也是通过采集接收器与多个发射器之间的距 离，并使用三角测量法计算出用户的位置。数据可以由接收器本地处理，也可由中心 服务器集中处理。不同之处在于系统把信号强度作为估算射频发射器与接收器间距的 依据。但是在建筑物内，射频信号传输环境是不断变化的，如果采用同一传输模型， 不可避免地影响丫系统的精确度。 ( 2 ) b a t 定位系统由a t & t 研究所设计开发的b a t 室内定位系统9 ，是通过对用 户的跟踪来提供室内定位信息。标识包括射频发射机和超声发9 , j - 4 ：j l ，它附在需要定位 的移动物体 二，配置i 惟一识别号码，接收农( j 系统皋站的射频信号，同时发送超声波 脉冲作为响应。接收机由射频接收机和超声波接收机两部分组成。当标识接收到监控 中心发给自己的消息时，就会发射一个超声波脉冲作为响应。同时接收机会接收到来 自监控中心的射频信号和来自标识的超声波脉冲，比较两者的到达时间差使用三角测 量法进行计算，实现对物体的跟踪定位。 ( 3 ) a c t i v eb a d g e 定位系统是b a t 系统的前身，在一个环境中跟踪目标并且存入 中心位置数据库。通过连接的标记来跟踪目标，并用红外发射机定期的发送它的唯一 i d 标示符。固定的红外发射机采集该信息并通过有线网络传播出去。如同b a t 系统， a c t i v eb a d g e 系统的目标跟踪特性可以影响到用户之间的隐私问题。 ( 4 ) c r i c k e t 系统由用户携带的接收器、固定放置在建筑物内的信标以及中心 服务器组成。将主动发射器( 信标发射器) 安置在顶棚上并且将被动的接收器( 接收 器) 固定在目标物体和设备上。信标发送超声波脉冲，以及携带数据包的射频信号； 射频信号的速率接近3 1 0 0 ，0 0 0 ，0 0 0 m s ，远远高于超声波3 4 4 m s 的速率。接收器会先 收到射频信号，而后才是超声波脉冲。通过测量两种信号的到达时间差，来估算出与 信标之间的距离。c r i c k e t 体系结构的主要优点1 n 2 1 是部署上的可调性、保密性和简 单性。c r i c k e t 是一个a dh o c 1 3 1 分散的系统。信标发生器可以随意安放甚至不需要人工 配置，所有元件自动工作，不需要同步或集中式控制，这样使得系统配置简单化。c r i c k e t 信标发射器“钉是可编程的，加强了对定位感知系统程序的支持，它提供自身的空间位 置及坐标位置。 通过分析，我们可以利用不同的定位方式满足导航要求，为今后建筑物的智能化 建设提供了方便，结论可为实际应用及进一步研究提供参考。 在室内导航系统的实际应用中，实时性要求是显而易见的，在出行过程中一旦由 于发生特殊情况未能按预定导航路径移动，则系统必须重新计算最优路线，因此对规 划算法的执行效率要求较高，即运行速度一定要快。另外，在应用中，导航电子图的 规模往往十分庞大，使得执行路径规划算法所需要的时间和存储空间要求都变得非常 苛刻。为适应导航系统的要求，必须研究高效的路径规划算法。即使算法求得的最优 路径解可能并非理论意义上的“最优”，而只是次优或较优，只要能在运算速度或存储 开销方面获得较大的利益，同样适合于导航系统的要求。 基于图论的图搜索算法一一从起始点出发向目标点搜索的算法，很适合导航系统 的要求。d i j k s t r a 算法可以求出图中从一个顶点到其它各项点的最短路径的长度及一条 最短路径，但是，该算法具有其局限性，效率不高。张巧荣，崔明义提出一种利用栅 格法铂和改进的d i j k s t r a 算法进行机器人路径规划的方法，该方法利用栅格法对机器 人的工作环境进行描述，改进了d i j k s t r a 算法，实践汁明该方法具有实时性和路径最优 性：陈益富等人在对经典的d i j k s t r a 算法6 思想进行分析的基础七，论述j - d i j k s t r a 算法的种改进算法，将算法的时间复杂度d ( 门) 中的n 降到一个很小的值。 事史j 二，经过这螳年的努力，目前存在的一屿技术和处理算法也能够在定程度 ? 解决呼航系统l f i 的路径问题，但每一种f i 州的处j = l l ! 疗法都足用j 二解决f i f i d 的问题或 支持不同的应用，在导航系统的应用环境、定位精度、能量需求、时间效率等多方面 都有不同的效果。总体而言，研究者们针对不同的应用环境要求提出各种各样的解决 方案，在相应的条件下能达到好的效果，但真正的用在实际系统中的还很少，而且受 严格的条件限制，还有待提出更好的办法，以求解决好导航中的路径问题。 1 3 本文的组织结构 目前，室内导航系统中的选路及路径规划的难点问题主要有：环境信息图的构建， 能够描绘室内环境下的路网问题；在建立的路网上进行路径规划问题。结合大量相关 的文献资料，本文的研究任务将围绕上面两部分进行，组织结构安排如下： 第一章主要介绍了室内导航系统及其路径规划技术的研究现状和研究意义，并概 括了论文的组织结构。 第二章详细介绍了一般的有限元划分方法中的d e l a u n a y = 角法，针对环境信息的 处理问题，对d c l a u n a y - - - 角法进行了改进优化，并进行仿真实验，为路径构建做基础。 第三章在第二章的环境信息处理结果的基础上，通过模型建立及数据分析证明了 添加剖分结点的d e l a u n a y 三角法构造的路径具有最短特性，并讨论了路径图的存储方 法，为路径规划做基础。 第四章对d i j k s t r a 算法和a 木算法进行了研究。在建立的室内路径图上进行仿真实 验，分析仿真结果，总结了两种算法性能。通过实验仿真，证明a 宰算法更为有效。 第五章对全文工作进行总结，并分析下一步需要研究的方向。 4 第二章室内空间位置信息构建及信息处理 建筑物内的导航与道路系统的导航不同。室内移动设备没有一组明确定义的路径， 这样用户就不能像汽车在道路网上一样自由的行使。必须找到合适的且不同于在网路 上绘制实际路径的方法，来绘制室内起始地到目的地的路径。 所谓的路，即一条线段，移动的时候就只能沿着它移动。线段是由点连接而成的， 这样路就可看作是由一个一个的点连接构成。这些连接成路径的点并不是任意选择的， 确定点的位置关系到下一步移动的位置和方向。 于是，需要首先建立室内环境图，描述室内环境空间位置信息；然后，确定某具 体区域内部的路径点；最后，将这些点有效的连接构建路径。如何处理环境信息将是 本章要解决的关键问题。 2 1 室内位置信息图的建立 对于实际室内空间分布图，由于目前仍未出现可以直接应用的建筑物室内空间信 息数据库，我们必须根据实际情况进行分析，经过处理得到需要的环境图，反映室内 空间信息布局情况，怎样区分障碍物与非障碍物构成的可利用的空间信息图。 一般建筑物内部有一些常见的结构物( 如墙壁、门口、走廊等) ，这些物体将空间 划分成让人们使用的一个个房间，公共区域以及可以进入、不可直接进入的区域，类 似于街道上的安全护栏，可视为街道这个可以通行空间的障碍物，当你在街道上行使 但是目的地刚好在安全栏杆的外面，就必须找到一个通道通过栏杆而不能直接翻越栏 杆。这里统一称之为障碍物。在构造室内环境图时，我们必须解决障碍物及各个物体 的表示问题。 于是，我们用有限元描述室内空间结构。具体方法是将空间存在相互连接的地方 表示成点的形式，如门与墙连接处、墙壁与墙壁的连接处、楼梯与墙壁连接处等等。 于是，结果得到横墙壁与竖墙壁连接处表示为一种交节点，门口属于墙壁的边界点分 开的部分于是一个门口需要用两个门节点表示。对于不能进入或不能直接通过的区域， 我们用直线将其的边界点连接，表示这是不能直接穿越的障碍物；可以直接通过或者 能直接进入的区域，这样区域的边界点不用直线连接，表示该区域没有障碍物，可以 放心穿越。 图2 1 室内部分区域的环境图 根据以上思想，对图2 1 所示的房间框架图实现空间描述，将结构图中的墙壁、门、 室内物体等信息转换成相应的坐标位置，用点线方式表示如下： 从图2 2 中，我们可以很清楚地看到某建筑部分区域的房间布局结构，其中，这些 直线段是表示不能穿越的区域，一般即指室内的墙壁；大点用于记录两种建筑结构相 交时的交点信息，如墙壁与墙壁的交点，门与墙壁的交点等。点线连接的部分表示墙 壁；两个分别与线连接的点之间不相连接的区域表示门( 两点的横坐标大致十1 l 等或者 纵坐标大致相等) ：门的比例较小，判断各点之间的位置时，以门值大小为标准，如果 以上条件相仿，但两点距离大于门宽时，则表示这两点分别位于不l 司的空问i l ! 。通过 判断分析，得到各点、各线之间的关系。房帕j 内部的物体，按照图纸给定的f t 置和大 小比例，川样描述成点线连接的形式，物体的位置信息用小点表示，该连线样表示 不能被穿越，如图2 2 所示。该图既简洁地描述了周围环境又包含了足够的信息量。 2 2 室内位置有限元信息划分处理 室内空间结构信息图建立起来之后，将解决在各个结构之间如何移动的( 即移动 路径的建立) 问题。首先在由障碍物围成的空间中选取路径点，如果没有障碍物的阻 拦，可以任意移动；如果存在障碍物，从空间的一端走到另外一端，需要考虑下一步 移动的方向和位置。本部分研究如何对空间信息进行有效处理。下面介绍有关空间信 息图的有限元处理方法。 2 2 1 有限元法 有限元法作为一种强有力的工程分析方法被广泛地应用于各种研究领域。有限元 法的第一步就是生成分析域的一个恰当的有限元网格，网格划分质量的好坏直接影 响到数值分析的精度，而对于复杂的几何体来说，网格划分极费时间而且容易出错。 有限元网格生成技术按所生成单元类型可分为生成结构化( c o n s t r u c t i o n ) l 网格的方 法和生成非结构化( n o n - - c o n s t r u c t i o n ) 格“8 1 的方法。生成结构化网格的方法是对应 的映射法，而生成非结构化网格的方法“9 1 是按各方法的特点进一步细分。本文介绍的 d e l a u n a y 方法属于生成非结构化网格的方法，这类方法一般都可实现不同程度的自动 化，所以有时也称其为自动网格生成方法，其对于区域边界线和内部媒质分界线形状 不规则的情况以及场的分布变化较大的情况都能较好的适应。 通常，平面网格划分可分为三角形单元划分与四边形单元划分两种，三角形是最 简单的平面形状，由三角形可以近似模拟出各种复杂形状的平面二维舯1 图像。三角形 单元精度比四边形单元低但对边界的适应性强，应用广泛，因此，在有限元单元网格 的划分中，常采用三角形作为基本单元的形状。早期的网格剖分方法通常是先在区域 内布点，然后再将它们联成三角形，在三角化过程中，对所生成的单元形状难于控制。 随着d e l a u n a y ( 狄洛尼) 三角化( 简称为d t ) 方法的出现，逐步成为目前最流行的全自动 网格生成方法之一。 2 2 2 三角剖分 如何把一个散点集合剖分成f i 均匀的三角形网格是散点集的三角剖分问题，散点 集的三角剖分“门对数值分析和图形学都是极为重要的一项预处理技术。 三角剖分定义：假设v 是二维实数域 ：的有限点集，边e 是由点集中的点作为端 点构成的封闭线段，e 为e 的集合。那么该点集v 的一个二角剖分t = ( v ，e ) 是个平面 图g ，该平面图满足条件： 1 ) 除了端点，平面图中的边不包含点集中的任何点； 2 ) 没有相交边； 3 ) 平面图中所有的面都是三角面，且所有三角面的合集是散点集v 的凸包。 1 、d e l a u n a y 三角剖分 d d a u n a y 三角剖分是前苏联数学家d e l a u n a y 在1 9 3 4 年提出的：对于任意给定的 平面点集，只存在着唯一的一种三角剖分方法，满足所谓的“最大最小角 优化 准则，即所有最小内角之和最大，这就是d e l a u n a y 三角剖分。这种剖分方法遵循“最 小角最大和“空外接圆 准则。 d e l a u n a y 三角剖分的定义：在实际中运用最多的三角剖分是d e l a u n a y 三角剖分， 它是一种特殊的三角剖分。 d e l a u n a y 边：假设e 中的一条边e ( 两个端点为a ，b ) ，e 若满足下列条件，则称 之为d e l a u n a y 边，存在一个圆经过a ，b 两点，圆内( 注意是圆内，圆上最多三点共圆) 不含点集v 中任何其他的点，这一特性又称空圆特性。 d e l a u n a y 三角剖分：如果点集v 的一个三角剖分t 只包含d d a u n a y 边，那么该三 角剖分称为d e l a u n a y 三角剖分。 2 、d e l a u n a y 三角剖分的准则 d e l a u n a y 三角剖分方法遵循“最小角最大和“空外接圆”准则。 ( 1 ) 空圆特性：d e l a u n a y 三角网是唯一的( 任意四点不能共圆) ，在d e l a u n a y 三角形网中任一三角形的外接圆范围内不会有其它点存在。如图2 3 所示。 图2 3 空圆性 ( 2 ) 最大化最小角特性：在散点集可能形成的三角剖分中，d e l a u n a y 三角剖分所 形成的三角形的最小角最大。从这个意义上讲，d e l a u n a y 三角网是最接近于规则化的 三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后， 六个内角的最小角不再增大。如图2 4 所示。 a d b b 图2 4 最大化最小角性 “最小角最大 准则是在不出现奇异性的情况下，d e l a u n a y 三角剖分最小角之和 均大于任何非d e l a u n a y 剖分所形成三角形最小角之和，三角形的最小内角之和最大， 从而使得划分的三角形不会出现某个内角过小的情况，比较有利于有限元的后续计算。 “空外接圆 准则是d e l a u n a y 三角剖分中任意三角形的外接圆内不包括其他结点。因 此，在各种二维三角剖分中，只有d e l a u n a y 三角剖分才同时满足全局和局部最优。 3 、d e l a u n a y 三角剖分的特点 ( 1 ) 最接近：以最近临的三点形成三角形，且各线段( - z 角形的边、) 皆不相交。 ( 2 ) 唯一性：不论从区域何处开始构建，最终都将得到一致的结果。 ( 3 ) 最优性：任意两个相邻三角形形成的凸四边形2 2 2 3 的对角线如果可以互 换的话，那么两个三角形六个内角中最小的角度不会变大。 ( 4 ) 最规则：如果将三角网中的每个三角形的最小角进行升序排列，则d e l a u n a y 三角网2 4 1 的排列得到的数值最大。 ( 5 ) 区域性：新增、删除、移动某一个顶点时只会影响临近的三角形。 ( 6 ) 具有凸多边形的外壳：三角网最外层的边界形成一个凸多边形的外壳。 2 2 3 d e i a u n a y 三角法的基本原理 在平面域( 尺：) 上有n 个节点p 只，县，己只) ，将这些节点连接成三角形，那么 在且只存在一种三角形连接，使任何三个节点构成的三角形的外接圆不包含除此三点 之外的任何节点。 对于以e 给定的n 个节点p 组成的平面点集p ，它的d e l a u n a y 三角形划分有一个 几何对偶，我们称之为v o r o n o i 图2 钉，v o r o n o i 图将平面分成n 个凸多边形 s ( 只) ，s ( 只) ，s ( 只) s ( p o ) 。 任一凸多边形内所有的点到节点p 的距离比到其他节点的距离都要短，这样的凸 多边形可用以下数学方式表示： s ( 只) = xe r ：d b ，只) d b ，只j ，f ，j = 1 ，2 ，3 n ，f s ( 只) 实际上是只与其他( n 1 ) 个节点的连线的垂卣平分线所形成的( n 1 ) 个半 平面的交集如图2 5 所示。 9 图2 5v o r o n o i 多边形偶图 由图2 5 可以看出，一般情况下，v o r o n o i 图的一个顶点同时属于三个v o r o n o i 多 边形，每个多边形内仅有一个节点，连接三个共顶点的v o r o n o i 多边形内的节点就可以 形成一个d e l a u n a y 三角形，如图2 6 所示。 图2 6d e l a u n a y 三角形 由上图可知，d e l a u n a y 三角网为相互邻接且互不重叠的三角形的集合，每一个三 角形的外接圆内不包含其他点。d c l a u n a y 三角网由对应v o r o n o i 多边形的点连接而成。 d c 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 三角法最主要的优点之一就是它自动避免了生成小内角的长薄单元，因 为长薄单元使积累误差增加，增大计算量。事实上，l a w s o n 和s i b s i n 根据定义已经表 明d t 是局部等角的，这意味着在d t 中，当每两个相邻三角形形成一凸四边形时，这 两个三角形中的最小内角一定大于交换凸四边形对角线后，所形成的另两个三角形中 的最小内角，据此可见d t 特别适用于有限元分析应用中的网格生成。这使得d e l a u n a y 三角网具有极大的应用价值，即用d e l a u n a y 算法可获得性能优良、形状最佳的三角形 单元，因而颇受欢迎，成为三角形单元自动剖分的主要方法。 2 2 4d ei a u n a y 三角法的分类 长期以来，很多学者都在研究高效、快速地构建d e l a u n a y 三角网的算法，因此出 王见，许多成熟的算法，根据构建二f f j 网的步骤，目前平面区域的三角剖分的方法基本 i ：可以归结为_ 三类：逐点捅入算法、分治算法和三角网生长算法。 l o 1 、逐点插入算法 逐点插入方法是l a w s o n 在1 9 7 7 年提出的。基本思想为：在包含所有数据点的初 始多边形中，将未处理点依次插入到已经存在的d e l a u n a y 三角网格中，并对新边使用 局部优化算法( l o p - - l o c a lo p t i m i z a t i o np r o c e d u r e ) 进行优化，以保证生成d e l a u n a y 三角网。逐点插入算法实现过程如下： ( 1 ) 定义一个包含所有数据点的由两个直角三角形构成的矩形框； ( 2 ) 在矩形区域内建立初始三角网，可以预设一个点作为初始的顶点；然后迭代 以下步骤，直至所有数据点被处理； ( 3 ) 插入一个数据点v ，在三角网中找出包含v 点的三角形，将点v 与三角形 的三个顶点相连，重构三角形；搜索点在三角网中位置的方法很多，可以采用重心法、 中心法、面积法( 利用格林公式计算三角形的面积) 来判断点是否在三角形内，也可 以利用点与直线的关系来确定； ( 4 ) 用l o p 局部优化算法优化三角网：对具有公共边的两个三角形组成的四边 形进行判断，如果其中任意一个三角形的外接圆包含另一三角形除公共顶点外的第三 顶点，则交换公共边。这样就使得满足d e l a u n a y 三角网的两个性质：空外接圆性质和 最大最小角性质。 2 、分治算法 s h a m o s 和h o e y 基于v o r o n o i 图构建，提出了分治算法的思想。l e w i s 和r o b i n s o n 则将分治算法的基本思想应用于d e l a u n a y 三角格网的构建。其思路是采用递归分割点 集直至每个子集中仅含三个离散点而形成三角形的办法，经过自下而上逐级合并生成 最终的三角网。 分治算法的基本步骤： ( 1 ) 首先将点集数据进行排序、分割，递归地把点集划分为足够小、互不相交的 子集，直至所有子集中的点数少于4 个点为止； ( 2 ) 在每一个子集内构建d e l a u n a y 子三角网； ( 3 ) 然后逐步合并相邻子集，最终形成整个点集的d e l a u n a y 三角网。 3 、三角网生长算法 g r e e n 和s i b s o n 首次实现了一个生成d i r i c h l e t 多边形图的生长算法啪1 0 三角网生 长法的基本思想是：任选一点，找到与它距离最近的点相连成为一条初始基线。按 d e l a u n a y 条件寻找与基线构成d e l a u n a y 三角形的第三个顶点。重复进行这一过程直到 所有数据郜被连接进三角网中。 三角网生长算法步骤： ( 1 ) 在所采集的离散点中仔意找一点，然后查找距此点最近的点，连接后作为初 始基线； ( 2 ) 住初始基线右侧运用d e l a u n a y 法则搜寻第三点，具体的做法是：在初始基 线台侧的离散点。1 1 杏找距此基线i f 1 高破短的点。作为第二点： ( 3 ) 生成d e l a u n a y 三角形，再以三角形的两条新边( 从基线起始点到第三点以 及第三点到基线终止点) 作为新的基线； ( 4 ) 重复步骤( 2 ) 、( 3 ) ，直至所有的基线处理完毕。 一般情况下，上述三种算法在时间复杂度对比上，逐点插入算法时间复杂度为 d 【3 心j ，分治算法的时间复杂度为o ( l o g n ) ，三角网生长法的时间复杂度为 o i 3 胆j ，其中n 为生成单元总数。从时间复杂度上看，分治算法最好；逐点插入算法 容易实现，内存空间要求不大，但时间复杂度差，效率较低，当点数较多时，处理过 程非常缓慢。分治算法的优点是构网速度快，时间效率高但需要大量递归运算，因此 占用内存空间较多数据预处理及优化工作量较大，对硬件需求较高三角网生长算法由 于算法复杂度太大，搜索效率低，目前较少人研究，较多的是前两种算法。 4 、改进的d eia u n a y 三角剖分算法 环境信息的描述将图形的一些基本结构信息转变为有限元信息，表达一些可见的 二维多边型房间信息布局，在这些前提条件下，我们要解决剖分这些多边形的问题， 就必须寻找新的解决方法更好的进行信息处理。 通常采用的剖分方法有分治法、数据点渐次插入法和三角网生长方法等，而这些 方法的程序设计较复杂。凸多边形的生成算法是计算几何的基本内容之一。所谓的凸 包“ 是指当多边形由a = ( p 。，p ，p 。) 的顶点按顺时针排列时，满足a 的内部区域总 在边p p 。的同侧的条件。但是，考虑到一般建筑物的空间结构映射成二维平面图之 后基本上均为平行四边形或者长方形、正方形等比较规则的多边形，所以根据凸多边 形的定义和判断准则，可以很清楚地证明映射后的建筑物平面图均为二维凸多边形， 所以可直接应用平面图中的有限元信息来进行三角剖分，不必考虑凸壳的生成问题， 使得算法更加省时有效。 基本解决思路如下： ( 1 ) 已知由已经给出的线段连接成多个多边形，规则的在多边形的各边选几个点， 这里可以规定成取线段的m 分点( 通常选m 2 2 ) ； ( 2 ) 取多边形的顶点； ( 3 ) 在多边形内部，随意抛撒一定数目的点( 数目视实际情况而定) ； ( 4 ) 有效的遍历所有点，进行相应的d e l a u n a y 三角剖分。 经过1 、2 两个步骤之后，选取的各点连接的图形满足形成的均为凸多边形，保证 三角剖分的前提条件成立。而经过以上4 个步骤，可以将只有几个点连接的多边形有 效的划分成几个小区域，选择这些区域的目的就是为以后路径建立做基础。 2 2 5 改进的d e i a u n a y 三角算法流程 首先介绍部分需要强调的概念： ( 1 ) 多边形各边m 等分点的求解方法及步骤 若记多边形各边p o p l ，p 。p 2 ，p 。p o 的m 分点为g g = 0 , 1 2 ，o + 1 ) 肌一1 ) ， 分别设q o = p o ，q 。= a ，q 2 。= p 2 ，q 。= p 。 第一步：求p o p l 边的m 分点吼= p o ，q 。= p l q l ( x ) = g o ( x ) + 1 m p ，( x ) 一q o ( x ) ) ；留1 ( y ) = g o ( y ) + l mx p 。( y ) 一q o ( y ) ) ； q f ( x ) = g o ( x ) + i m x p 。( x ) - q o ( x ) ) ；q f ( y ) = g o ( y ) + i m x p 。( y ) - q o ( y ) ； 第二步：对于取得第_ 条边p ，p m 的m 分点，此时设g 加= p ，q ( m ) 。= p m 。 首先判断q 加与q ( 川扣的大小( 包括两点的横坐标x 和纵坐标y ) 。 如果p ，p ，+ 1 ( 即q 加苫q ( ，+ l 加) 时， q 加以( x ) = p j ( x ) + ( m - 1 ) m p ，( x ) - p j + l ( x ) ) ；q i r a + 1 ( y ) = p j ( y ) + ( m 一1 ) m p j ( y ) 一p j + l ( y ) ； ： q 加“( x ) = p ( x ) + ( m - f ) m p ( x ) 。p j + l ( x ) ) ；g 加“( y ) = p ，( y ) + ( m - f ) m x p ( y ) p ，+ l ( y ) ； 如果p sp j + l ( 即q 加sq ( ，+ 1 ) 卅) 时， g 朋+ l ( x ) = p ，( x ) + l m x p ，+ l ( x ) - p ，( x ) ) ；q 加+ 1 ( y ) - - p ，( y ) + l m p j 1 ( y ) 。p ，( y ) ，； ： q 加+ j ( x ) = p ，( x ) + f m p j + l ( x ) 一p ，( x ) ) ；g 伽+ j ( y ) = p ，( y ) + i m p j + l ( y ) 。p ，( y ) ； 直至求完边p 州p 。的m 分点为止； 第三步：求p 。p 。的m 分点时，由于p 。( x ) p 。( x ) ，必须依照纵坐标进行判断和计 算。 如果p 。( y ) p o ( y ) 时，留。+ ，( x ) = p 。( x ) + ( m f ) m x p 。( x ) 一p 。( x ) 】； q m + f ( y ) = p 。( y ) + ( m f ) m x p 。( y ) - p 。( y ) ； 如果p o ( y ) ； 留。+ f ( y ) = p 。( y ) + i m x p 。( y ) - p o ( y ) ； 直至f = m 为止，即求完边p 。p 。的m 分点为止。 添加多边形各边的m 等分点的流程图如下： 否 取；j 石，比较p o 和p 。的纵坐标的大小。令i = l ，酗 g 艉“( x ) 矾( x ) + f l 只( x ) 只( x ) l g 糠+ i ) 哦( 力+ i l m x 以) 嵋l t 是 t 芑 q m + l ( x ) = 只( x ) + h i ) x 只( i ) 只( x ) g 。“) 专只) + o r - i ) x 只( y ) 一只( y ) l i - i + l ：一：上 ，石 7 古 蔓茎 图2 7 添加多边形各边m 等分点的流程图 ( 2 ) 点与有向线段之间位置关系的判断方法 定义：s = b 一而) ( y ：一y ，) 一b ：一_ ) ( y y 。) 点p ( x ，y ) 在有向线段瓦匹i i 万忑i 习的左、右侧及其线上，分别决定于s 的值 大小。 当s ) o 时，点p 在有向线段p 。p ：及延长线的右边； 当s = o 时，点p 在有向线段p 。p ：及延长线上； 当s ( 0 时，点p 在有向线段p ，p ：及延长线的左边。 改进d e l a u n a y 算法的具体思想及具体实现步骤如下。 ( 1 ) 遍历该多边形的所有顶点，比较各项点横坐标和纵坐标大小，将横坐标最小 并且纵坐标再最小的顶点作为p o ，将多边形的顶点序列( 顺时针) p ( i = o ，1 ，2 ，1 ) 作 为顶点，依次连接成有向线段( 即彩边彤的各边) p o p ，p 。p 二，p 。p 。，并h 标 记该边信息加入剑边链接表巾： 1 4 ( 2 ) 添加各边m 等分点，顺序选取多边形的各边p o p ，p 。p ：，p 。p o 的m 分点( 通常选m = 4 ) ，记为口( f = 0 , 1 , 2 ，o + 1 ) m 一1 ) 。 ( 3 ) 将得到q ( i 一0 , 1 , 2 ，o + 1 ) ，l 一1 ) 总共( n + 1 ) m 个点，且依次顺时针方向排 列为q o ，q l ，口( 州h 1 ，依次连接成有向线段吼q 。，q l q 2 ，日( 榭h l q o ，并且 标记该边信息加入到边链表中； ( 4 ) 在要求的多边形内部分别随机抛撒一定数目的点( 这些点的横坐标和纵坐标 满足均在最小点和最大点的范围之内) ，计为r ( f o 工2 ，k ) 。 ( 5 ) 以q o q 。为初始边，在q o q