（计算机科学与技术专业论文）简单多边形内lr可视问题的求解算法研究.pdf

t h es i m p l ep o l y g o n at h e s i ss u b m i t t e dt o d a l i a nm a r i t i m eu n i v e r s i t y e ml n i np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t sf o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g h a nb i n g ( c o m p u t e r s o f t w a r ea n dt h e o r y ) t h e s i ss u p e r v i s o r ：p r o f e s s o rj i a n gb o m a y ，2 0 1 1 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成博硕士学位论文= = 筵望多垫形凼堡亘塑闷墅的壅鲤簋洼婴究：。除论 文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经 公开发表或未公开发表的成果。本声明的法律责任由本人承担。 学位论文作者签名： 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、 中国学位论文全文 数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式出版发行和 提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密口( 请在以上方框内打“ ) 论文作者签名：微 导师签名： 日期：m 中文摘要 摘要 l r 可视性问题是计算几何领域的重要研究课题之。通过对l r 可视多边形 特性的研究，能够得到求解计算几何经典问题的有效算法。因此，对于l r 可视多 边形的研究，不仅具有重大的理论研究意义，而且也有非常重要的实际应用价值。 本文在论述简单多边形分割的相关理论的基础上，对简单多边形的l r 可视性 的判别问题进行了深入的研究，给出了判别一个简单多边形是否为l r 可视多边形 的充分必要条件，并加以严格证明。通过将l r 可视多边形上的非冗余组件架构映 射成一组圆上的弦，给出了l r 可视多边形所具有的简单特性。通过这些特性，本 文提出了一个时间复杂度为o ( n ) 的计算l i 之可视多边形内部非冗余组件数目的算 法，通过该算法以及判别一个简单多边形是否为l r 可视多边形的充分必要条件， 可以在线性时间内判断一个简单多边形是否具有u t 可视性。这大大简化了利用找 出多边形内的点对来判断多边形是否具有l r 可视性的这一已知算法。 为了验证算法的可行性和有效性，本文针对测试数据求解出了简单多边形内 部非冗余组件，并判断该多边形是否具有l r 可视性，并对算法运行结果进行了分 析显示。结果表明，本文所给出的算法，不仅是高效的，而且切实可行。 关键词：简单多边形；l r 可视性；可视多边形；非冗余组件 l r - v i s i b i l i t yp r o b l e mi so n eo ft h em o s ti m p o r t a n tp r o b l e m so fc o m p u t a t i o n a l g e o m e t r y r e s e a r c h i n go nt h ec h a r a c t e ro fl r v i s i b i l i t yp o l y g o n ，i tc a nh e l pp e o p l e d e v e l o pt h ee f f e c t i v ea l g o r i t h mo f t h e s ec l a s s i cp r o b l e m s t h e r e f o r e ，t h er e s e a r c ho nt h e l r - v i s i b i l i t yp o l y g o n sh a sn o to n l yt h et h e o r e t i c a ls i g n i f i c a n c e ，b u ta l s ot h ep r a c t i c a l v a l u e b a s e do nt h ec h a r a c t e r i s t i c so ft h es i m p l ep o l y g o n s ，t h i sp a p e rm a i n l yr e s e a r c ht h e c h a r a c t e ro fl r v i s i b i l i t yp o l y g o na n dw h e t h e rt h es i m p l ep o l y g o ni sl r - v i s i b i l i t yo r n o t t h e n ，w eg i v et h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n st od e t e r m i n ew h e t h e r a s i m p l e p o l y g o ni sl r - v i s i b i l i t y ，a n ds t r i c t l yp r o v ei t i nt h i sp a p e r ，w eg i v eas i m p l e ，e x p l i c i t c h a r a c t e r i z a t i o no fl r - v i s i b i l i t yp o l y g o n s i ti so b t a i n e db ym a p p i n gss t r u c t u r eo f n o n r e d u n d a n tc o m p o n e n t su s e di nd e t e r m i n i n gl r - v i s i b i l i t yi n t oas e to fd i r e c t e d c h o r d sf o rac i r c l e u s i n go u rc h a r a c t e r i z a t i o n ，w ef u r t h e rd e v e l o pas i m p l eo ( n ) t i m e a l g o r i t h mf o rc o m p u t i n g t h en u m b e ro fn o n - r e d u n d a n tc o m p o n e n t u s i n gt h i sa l g o r i t h m a n dt h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n st od e t e r m i n ew h e t h e ras i m p l ep o l y g o ni s l r - v i s i b i l i t y ，w ec a n d e t e r m i n ew h e t h e rag i v e np o l y g o ni sl r - v i s i b l ei nt h el i n e rt i m e t h i sg r e a t l ys i m p l i f i e st h ee x i s t e da l g o r i t h m sf o rd e t e r m i n i n gw h e t h e ras i m p l ep o l y g o n i sl r v i s i b l ea n df o rr e p o r t i n ga l lp a i r ssa n dtw h i c ha d m i tl r - v i s i b i l i t ya sw e l l i no r d e rt o v e r i f yt h ef e a s i b i l i t ya n de f f e c t i v e n e s so ft h ea l g o r i t h m ，t h i sp a p e r c o m p u t et h en o n r e d u n d a n tc o m p o n e n to ft h e t e s td a t e ，a n dd e t e r m i n et h el r - v i s i b l eo f t h es i m p l ep o l y g o n ，a n ds h o wa n da n a l y z et h er u n n i n gr e s u l to ft h ea l g o r i t h m t h e r e s u l t ss h o wt h a tt h ea l g o r i t h mi se f f e c t i v ea n dp r a c t i c a b l e k e yw o r d s ：s i m p l ep o l y g o n ；l r - v i s i b i l i t y ；v i s i b i l i t yp o l y g o n s ；n o n - r e d u n d a n t c o m p o n e n t 目录 目录 第1 章绪论1 1 - 1 研究背景与意义1 1 2 国内外研究现状。1 1 3 研究内容3 1 4 论文的组织结构3 第2 章l r 可视多边形的相关基础_ 5 2 1 计算几何基础5 2 2l i 己可视问题描述6 2 2 1 简单多边形6 2 2 2 简单多边形的分割8 2 2 3 多边形组件1 0 第3 章l r 可视多边形的特性1 3 3 1l r 可视多边形的特性及其描述1 3 3 2 相关定理及证明1 6 第4 章非冗余组件数的求解算法。2 8 4 1 最短路径及其最短路径树2 8 4 2 组件数的求解算法3 5 4 2 1 非冗余组件内部反射点的处理3 6 4 2 2 在多边形内部找到一个非冗余组件3 9 4 3 算法描述4 1 4 4 数据结构。4 2 第5 章l r 可视多边形的判别及应用4 5 5 1l r 可视多边形的判别。4 5 5 2 测试结果4 5 5 3l r 可视多边形的应用4 8 5 3 1 画廊问题4 8 5 3 1 最短巡视员路径问题4 9 第6 章总结与展望。5 2 6 1 论文工作总结5 2 6 2 进一步研究工作5 2 目录 参考文献5 4 致谢5 8 研究生履历5 9 简单多边形内l r 可视问题的求解算法研究 第1 章绪论 1 1 研究背景与意义 计算几何中许多问题的研究都是基于l r 可视问题的相关研究结果而展开的， 因此，针对各种标准的可视问题研究在计算几何及其相关应用领域中一直都是学 术界的研究热点问题。多边形内的可视概念是随着a v i s 和t o u s s a i n t 研究的艺术画 廊问题( a r tg a l l e r yp r o b l e m ，a g p ) 而产生的【1 1 。艺术画廊问题也称为画廊问题，是 一种有关可视的最优化问题。画廊问题可简单描述为：在画廊内要求放置数量最 少的守y - ( 守卫是静止的) ，使得整个画廊均被监视到。在针对该问题的研究中，可 将画廊抽象为一个简单多边形，并在多边形内的某些点上放置守卫，使得这些守 卫能观察到多边形内的每个位置且守卫数量达到最少。画廊问题是一种设备定位 问题，即怎样使得监视这个画廊的守卫( 摄像头或灯等监视设备) 的数量达到最小， 以达到保护、监视或照明的目的。这里的可视表示标准的不受限的直线，最优化 则表示使满足问题要求的设备单元数量达到最小，以便最大限度地节约成本。在 现实生活中，针对这样一类问题的研究，很有应用价值。 随着社会的不断进步，人们对安全性的要求也在不断提高，各种监控活动也 是在类似环境下产生的。比如，在一些公共场所( 如银行、邮局、医院等) 安装监控 系统【2 1 ，其最优化问题也可以归于画廊问题的研究。在日常生活中，如安装照明设 置，设置监控录像等，都存在寻优问题，所有这些问题，都可在多边形监视问题 中找到相关模型，即可利用多边形监视问题进行求解。例如，在会场内设置多少 个监控摄像头能够达到最优覆盖? 这类问题可根据计算几何中l r 可视问题的研究 成果来解决，因此，对简单多边形监视问题范畴下l r 可视问题的研究，是很有意 义的，并且充满前景的。 1 2 国内外研究现状 以艺术画廊问题的研究为基础，众多学者展开了针对一些特殊多边形，如直 角多边形、带洞的多边形以及巡视员位置、守卫的放置( 如边守卫、顶点守卫、移 第1 章绪论 动守卫、l 等问题的研究，并得到了一些有意义的研究结果。典型的一些研究成果包 括守卫路径问题【3 训、c h v a t a l 和f i s h 提出的最少巡视员问题( m i n i m u mw a t c h m e n p r o b l e m ) t 5 - 6 1 、最短巡视员路径问题( s h o r t e s tw a t c h m a nr o u t ep r o b l e m ，s w r p ) 、 j o s e p hm i t c h e l l 提出的目击者问题( w i t n e s sp r o b l e m ) 等，所有这些问题，都可以看 做是l r 可视问题的应用研究。 本文针对简单多边形的l r 可视问题进行研究。设p 代表一个简单封闭多边形， 其边上的两个点s 和t 将多边形尸分为两个子链，分别称为工链和尺链，即左子 链和右子链。如果l 链上的任意一点都能被r 链上的某一个点看到，而r 链上的 任意一点也都能被l 链上的某一个点看到，那么就称该简单多边形p 关于点s 和t 是l r 可视的。l r 可视问题的研究可以放宽到弱可视领域。两个点集合是弱可视 的，是指其中一个集合上的某个点可以看到另一个集合上的每个点。 弱可视问题已经受到众多学者的关注，该术语是由a v i s 和t o u s s a i n t l 7 弓 入的。 他们提出了一种关于多边形的可视问题，即多边形的弱可视性。关于弱可视的一 个比较一般的概念是：允许从多边形内部的一条线段而不必是多边形上的一条边 看多边形是可视的。一个多边形必须有这样的一条内部线段，才能被称为弱可视 多边形。a v i s 和t o u s s a i n t 给出了一个能在线性时间内判断一个简单多边形对于给 定边是否具有弱可视性的算法。s a c k 和s u r i l 8 】给出了一个在线性时间内计算出给定 简单多边形所有弱可视边的算法，c h e n 9 j 对相同问题给出了一个最优并行算法，同 时解决了在弱可视多边形中计算最短子边的问题。k e l l o l 和c h w a l l l 】则给出了时间 复杂度为o ( n l o s n ) l 拘算法，该算法可判断一个多边形是否有弱可视弦，而k e 的算 法能同时返回最短弦。d a s 等人【1 2 】提出了一个在o ( n ) 时间内构造出所有弱可视弦 的算法。 h e 脏m a n 【1 3 】给出了一个判断简单多边形p 对于给定点s 和t 是否具有l r 可视 性的线性时间复杂度算法，t s e n g 和l e e 1 4 】刚给出了可以计算出所有u 己可视性点对 的时间复杂度为o ( n l o g n ) 篚j 算法。在这两篇论文中，作者实际阐述了一个称为两个 守卫问题的关于多边形可视性的问题，l r 可视问题只是其一个子问题。g a u t a m 等 人给出了一个能够在线性时间内对于给定的l r 可视多边形找出其所有可视点对 简单多边形内l r 可视问题的求解算法研究 的算法。p j h e f f e 珊a n 【1 5 】等人则在1 9 9 7 年对u 乇可视多边形的特征做了如下说明， 即：l r 可视多边形内部的各个非冗余c o m p o n e n t ( 组件) 必须包含点s 或t 。但是， 由于组件数目众多，s 和t 的位置又不确定，这些研究成果又大多停留在理论阶段， 很难用来解决实际问题。在这种情况下，本课题结合l r 可视多边形的相关理论知 识，提出一个可以计算任意简单多边形内非冗余组件数目的有效算法，并根据该 算法的运行结果，判断给定的简单多边形是否具有l r 可视性。 1 3 研究内容 本文针对简单多边形的l r 可视问题进行研究，对简单多边形的特性进行分 析，设计一个算法用于计算出一个给定简单多边形中非冗余组件的数目，并根据 所计算的非冗余组件的数目以及判别一个简单多边形是否为l r 可视多边形的充 分必要条件，确定给定的一个简单多边形是否具有l r 可视性。 本文的主要研究内容包括如下几个方面： ( 1 ) 从简单多边形的结构出发，研究u 乇可视多边形及其相关特性。 通过对简单多边形的相关概念与特性的描述，给出l r 可视多边形的相关概 念，如可视多边形、弱可视多边形以及角的凸凹特性等。 ( 2 ) 结合简单多边形中角的特性与组件之间的关系，研究简单多边形中组件的 构成及其相关特性。 ( 3 ) 对简单多边形的l r 可视性进行研究，分析简单多边形中非冗余组件数目 与l r 可视性之间的关系，设计一个算法计算简单多边形中非冗余组件的数目并进 行验证。 ( 4 ) 对判别一个简单多边形是否为l r 可视多边形的充分必要条件进行研究， 并应用算法判别给定简单多边形是否是l r 可视的。 1 4 论文的组织结构 本文循序渐进地对所要研究的内容进行论述，首先论述相关概念及其理论基 础，然后就本文的中心研究内容进行论述并对本文所提出的算法做较为详细的论 第1 章绪论 述。最后，总结本文的研究结果，给出相关的研究结论以及今后需要进一步研究 的问题。具体而言，本文将分成以下6 个章节，其结构如下： 第1 章绪论。本章主要论述l r 可视多边形的特性及应用，以及本课题的研 究背景及其研究意义，并且对本文的论文组织结构加以概述。 第2 章l r 可视多边形的相关基础。本章在论述简单多边形及其相关概念的 基础上，对l r 可视多边形问题中的有关定义做较为详细的描述，着重论述简单多 边形中非冗余组件的结构，为进一步研究l r 可视多边形问题奠定理论基础。 第3 章l r 可视多边形的特性。本章主要针对l r 可视多边形的一些特性以及 判别一个简单多边形是否为l r 可视多边形的充分必要条件进行研究，给出相关的 定理及证明，分析构造简单多边形内所有非冗余组件的技术方法。 第4 章非冗余组件数的求解算法。本章通过构造简单多边形内所有非冗余组 件，给出求解其数目的具体算法，并对算法的运行结果及复杂度进行分析，构造 测试数据以验证本文所提出的算法的有效性。 第5 章l r 可视多边形的判别及应用。本章论述如何使用本文所提出的计算 简单多边形内部非冗余组件数目的算法来判别一个多边形是否具有l r 可视性，并 论述l r 可视多边形在画廊问题和最短巡视员路径问题等计算几何学应用领域中 的应用问题。 第6 章总结与展望。本章对论文的工作进行总结，并对今后的进一步研究进 行展望。 。 简单多边形内l r 可视问题的求解算法研究 第2 章l r 可视多边形的相关基础 l r 可视问题在计算几何领域中占有相当重要的地位，在解决该问题的过程中 必然会涉及到一些计算几何学中的基础问题，因此，在研究l r 可视问题之前，有 必要对计算几何学中的一些基本概念及简单多边形的相关知识等，做一般性的论 述。 2 1 计算几何基础 由于计算机的出现，使得很多原本十分复杂的工作得到简化，如数值计算。 但是，对于有些问题，人们却经常会将它们复杂化，并给出一套复杂的解决方案， 如几何问题。计算几何学是在上世纪7 0 年代未期从算法设计与分析领域独立出来 的，作为计算机理论科学的一个分支，主要用于解决几何图形问题( 包括点、线、 多边形等) 的相关算法，包括凸包研究、多边形、几何体的排列等。 几何基元、查找以及优化等问题是计算几何学的基本问题。几何基元中的 v o r o n o i 图、多边形三角剖分、区域划分与线段求交、可视性图，以及几何查找中 的点定位、正交区域查找等【阚，这些基础知识在计算机图形学、g i s 、模式识别等 领域中有着广泛的应用。此外，计算几何也是动画设计、q 如制作等学科的基础【1 刀。 计算几何学解泱问题的方法包含很多不同的算法，并且伴有退化及鲁棒性的 问题，其研究内容包括凸多边形( c o n v e xh u l l ) 、交点问题( i n t e r s e c t i o np r o b l e m ) 、线 段交点( l i n es e g m e n ti n t e r s e c t i o n ) 、机器人问题( r o b o t i c sp r o b l e m ) 、艺术画廊问题 ( a r tg a l l e r yp r o b l e m ) 、最短路径问题( s h o a e s tp a t h s ) 等诸多方面。 从某种程度上说，计算几何学也是- f - j 对基本算法进行比较研究的科学，它 与许多其他科学之间的关系密不可分，尤其与数学有着密切的联系。在研究计算 几何学的过程中，经常会使用到数学中的一些理论与思想，如对算法复杂性的分 析、数学模型的建立问题等，这些联系使得它们在社会科学不断进步中得以共同 发展。如图2 1 表示“计算几何学”这一概念的由来。 第2 章l r 可视多边形的相关基础 计算机科学 实践理论 算法与数据结构 计算几何 图2 1 计算几何学的形成 f i g 2 1t h ef o r m i n go fc o m p u t a t i o n a lg e o m e t r y 今天，随着研究工作的不断进步，计算几何学科得到了飞速发展，产生了一 系列重要的研究成果，并在求解实际问题的过程当中得到了广泛应用。计算几何 学已经成长为一个被广泛认同的学科，拥有自己的学术刊物和学术会议，并形成 了一个由众多研究人员所组成的学术群体。作为一门新兴学科，计算几何学已经 在众多应用领域，如计算机图形学、删c a m 、机器人学、地理信息系统、模式 识别等领域，发挥着重要的作用，对人们的现实生活有深刻的影响。 2 2l r 可视问题描述 本文主要针对简单多边形的l r 可视问题进行研究。本文中所涉及的简单多边 形实际上是某些实际应用问题的抽象模型，例如，画廊问题就是将艺术画廊抽象 为一个简单多边形，人们通过分析这些简单多边形的特性来寻找求解实际应用问 题的思路或解决方案。由于简单多边形在l r 可视问题研究中占据着重要地位，因 此，有必要对简单多边形及其相关概念与特性等，做出较为详细的分析。 2 2 1 简单多边形 为了规范本文的论述，让我们首先来定义本文中所用到的一些概念与符号。 定义2 1 ：简单多边形是指由单个不自交的、封闭的线段链所围成的区域【1 7 1 。 若p 为简单多边形，则p 中既不包含自交线段，其内部也不允许出现任何空 洞。设简单多边形p 具有n 个顶点，分别记为p l 、p 2 、p 。，见，用p 一( p 。，p 2 ，p 。) 简单多边形内l r 可视问题的求解算法研究 来表示多边形，用e l p 。p ：，e 2 一p ：p 3 ，巳一见a 分别表示p 上的线段。则， ( 1 ) 简单多边形上相邻线段对之间的交是它们的公共点： e iie l + 。= b + 。；( 2 ) 简单 多边形中不相邻的线段之间不相交：e i i 巳一f 2 j ，f + 1 ；i 一1 * w9 刀，巳+ 。= q ， 见+ 。一p l ；( 3 ) 简单多边形中，任意三点不共线，即任意三条直线不会交于一点。 图2 2 给出了简单多边形与非简单多边形的一个例子。 a 简单多边形b 非简单多边形 图2 2 简单多边形与非简单多边形 f i g 2 2as i m p l ep o l y g o na n dn o n s i m p l ep o l y g o n s 由图2 2 可以看出，简单多边形的边界将平面分割为两个互不相交的区域， 分别是有界的内部区域和无界的外部区域。如果p 中含有空洞或存在线段相交的 情况，则p 被称为是多连通的，否则是单连通的。本文中所论述的多边形通常是 指单连通的简单多边形，且泛指p 的内部区域。 定义2 2 ：若一个多边形的所有内角的角度均小于石，则称此多边形为凸多边 形【1 8 。1 9 1 ，否则称为凹多边形。 由于凸多边形中每个内角的角度都小于石，其内部任意两个顶点之间的连线均 位于多边形边界，或者在其内部，显然，这样的多边形是可视多边形，因为从多 边形中的任意一点出发，都可以方便地看到多边形上的所有其它的点。本文所研 究的是凹多边形的l r 可视问题。 第2 章l r 可视多边形的相关基础 2 2 2 简单多边形的分割 定义2 3 ：在平面多边形中，内角角度大于1 8 0 度的顶点被称为反射顶点。 图2 3 中，r j 和厂2 分别为两个反射顶点。在研究可视化问题时，多边形内部 的反射顶点是一个非常重要的特性，因反射顶点会使图形两边的视线被遮挡住， 这就需要对多边形进行可视化分割。 图2 3 多边形内反射顶点 f i g 2 3r e f l e xv e r t e xo fp o l y g o n 定义2 4 ：可视性是指当对多边形内的任意区间进行分割时，会把多边形分成 两个不相交的区域，从其中一侧的区域边界上的某一点出发，到另一侧边界上的 任意点之间都可以进行直线连接( 即互相可见) 。 可视性问题可以分成三种类型，分别是强可视、弱可视与不可视。将对多边 形p 进行分割后所形成的两个区域边界，其中一条记为三，另一条记为尺。强可视 指的是在尺上存在一点，从该点到三上的所有点之间的连线，都不与上的其它 任何线段相交。弱可视则是指在工上存在一点，从该点出发与r 上的任意一点间 的连线，最多只能经过尺上的某一个顶点，但不与r 上的其它任何线段相交。不 可视是指在l 上存在一点p ，p 与r 上任意点之间的连线，都会经过l 上除p 点之 外的其它点，也就是说会与三上的其他线段相交。可视性问题的分类可如图2 4 所示。 简单多边形内l r 可视问题的求解算法研究 斗 一。- 一p l p k b ，鼢 ” k e a 强可视 b 弱可视c 不可视 图2 4 可视性问题的分类 f i g 2 4t h et y p eo ft h ev i s i b i l i t yc a s e s 设简单多边形p 的边上的两个不同点将p 分割成两个不相交的子链，分别称 为左子链l 和右子链r 。l r 可视问题中要研究的问题是多边形p 上是否存在这样 的两个点s 和t ，使得r 子链上的每一点都能被l 子链上的某一点看到；反之亦然。 如果存在，则称该简单多边形p 关于点s 和t 是l r 可视的，p 也被认为是l r 可 视多边形。如图2 5 所示。 s 一 图2 5l r 可视多边形 f i g 2 5l rv i s i b i l i t yp o l y g o n 定义2 5 ：简单多边形p 中存在两个不同的点x 、y ，若石与y 之间的连线砂完 全包含在多边形尸内，则称z 与y 互相可视，如图2 6 所示。 设多边形中存在两 简单多边形内l r 可视问题的求解算法研究 前向交点及后向交点的实例如图2 8 所示。 口) 图2 8 反射结点射线与多边形交点 f i g 2 8f o r w a r d ，b a c k w a r dr a ys h o t s 上述由反射顶点所引的和射线将多边形分成两个部分，分割的结果可能会产 生一个凸子多边形，这种情况下可以将其称为对多边形的可视化分割。如果简单 多边形尸内不存在可视化分割即多边形不存在反射顶点的情况，则在多边形上的 任意一点都能直接看到p 内的所有点。 用u ，y 分别表示简单多边形p 边上的两个异点，则用p 阻， ，】( e ( u ，v ) ) 来表示 沿着尸的边界从u 顺时针遍历到 ，所形成的闭合( 开) 线段链。 定义2 7 ：若，是简单多边形p 上的反射顶点，用线段链e r ，口( 厂) 】表示多边形 上关于点，的逆时针组件。同理，线段链p 【f ( 厂) ，】表示对于反射顶点，的顺时针 组件。 关于组件的分布见图2 9 。反射顶点，也被称为是相关组件的定义点。 图2 9 顺时针和逆时针c o m p o n e n t f i g 2 9c l o c k w i s ea n dc o u n tc l o c k w i s ec o m p o n e n t 第2 章l r 可视多边形的相关基础 简单多边形内部通过反射顶点所构造出的组件又可分为冗余组件和非冗余组 件两类。非冗余组件指的是不包含其他任何组件( 无论是顺时针还是逆时针) 的组 件。例如，在图2 9 中，组件研，化) ，y ：】和e f 0 3 ) ，v 3 1 就是非冗余组件，而尸( h ，b 0 i ) ) 因为包含e ( f 以) ，屹) ，是冗余组件。 如果简单多边形尸上的组件c 与c 有一部分边界是相互重叠的，则称组件c 与c 是相交的，否则成为不相交的。 另外，由于通过每个反射顶点都可以引出两条射线，构成两个组件，但通过 对简单多边形几何特性的分析可以得知，在这两个组件中，其中一个会将另外一 个覆盖，也就是形成了冗余组件。可以不考虑这些冗余的组件，这样，通过一个 反射顶点，就只能构成一个组件。还有一点需要说明，就是一个多边形中的组件、 有些是顺时针方向的，有些则是逆时针方向的。本文中，将忽略组件的方向，因 为它不影响本文所关心的相关结论。 定义2 8 ：简单多边形p 上存在一个组件c ，从一个不包含在c 内的点出发， 沿顺时针方向对多边形尸的边进行遍历，所遇到的c 的第一个端点称为c 的左端 点，则第二个端点为右端点。显然，如果组件c 是逆时针组件，它的左端点同时 是它的定义点，若c 是顺时针组件，它的左端点就是f p ) 。 至此，本文已经介绍了有关l r 可视多边形的相关基础知识，对于l r 可视多 边形的概念及用途也有了基本的了解，接下来会在此基础上，对l r 可视多边形的 一些特性进行研究，论述一个多边形在怎样的情况下才是l r 可视多边形，或者说 在什么条件下它一定不是l r 可视多边形，利用这些特性来寻求解决实际问题的可 行方案。 简单多边形内l r 可视问题的求解算法研究 第3 章l r 可视多边形的特性 本章将研究l r 可视多边形所具有的一些独特性质，并给出一些相关的定理及 其证明，为设计一个在多边形中构造非冗余组件并计算其数目的求解算法奠定基 础。 3 1 l r 可视多边形的特性及其描述 关于l r 可视多边形的特性，g a u t a md a s ，h e f f e r m a n 等人在1 9 9 7 年最先给出 了一个如下定理【2 0 1 ： 定理3 1 ：若一个简单多边形关于点s 和t 是l r 可视的，那么，该多边形中 的任何一个非冗余组件都必然包含点s 或t ；反之，如果多边形内部存在一个既不 包含点s ，也不包含点t 的非冗余组件，则该简单多边形必然是非l r 可视的【2 0 - 2 5 1 。 由于组件之间可能存在重叠部分，所以只需判断那些非冗余组件中是否能够 包含点s 或点t 即可。也就是说，简单多边形p 是l r 可视多边形，当且仅当p 的 每个非冗余组件必须包含点s 或点t 。为对该定理进行准确理解，下文将给出一个 简单例子进行分析。 假设简单多边形尸内有5 个组件，且多边形p 内的每一个组件都与其它2 个 不相同的组件相交。通过对点s 和点t 在多边形p 的位置来分析其l r 可视性。 ( 1 ) 若点s 在组件1 内，点f 在组件3 内，那么组件2 和组件4 中既不包含s ， 也不包含t ，所以多边形p 是非l r 可视多边形，如图3 1 所示，其中粗线部分标 记了可能成为“盲区 的组件，下同。 第3 章l r 可视多边形的特性 图3 1 点s 和t 的位置情形1 f i g 3 1t h ec a s e1o fp o i n tsa n dts i t u a t i o n 由于s 和t 是可以在边界上移动的点，那么可以对点s 和点t 的不同位置进行 分析。若点t 在组件2 与组件3 的重叠位置上，这时，组件4 中既不包含点s ，也 不包含点t ，所以仍存在盲区，如图3 2 所示。假如点t 移动到组件3 与组件4 的 重叠位置上，这时，组件2 中既不包含点s ，又不包含点t ，所以也有盲区( 图例从 略) 。 图3 2 点t 在两个组件的重合位置 f i g 3 2t h ep o i n t ti nt h ec o i n c i d e n c eo ft w oc o m p o n e n t s ( 2 ) 若点s 在组件1 中，点t 在组件2 中，那么组件3 与组件4 中既不包含点 5 ，又不包含点t ，所以多边形p 是非l r 可视多边形，如图3 3 所示。在这种情况 简单多边形内l r 可视问题的求解算法研究 下，如果t 移至组件2 和组件3 的重叠位置上，那么组件4 仍然是盲区，也不能使 多边形p 成为l r 可视多边形。 图3 3 点s 和t 的位置情形3 f i g 3 3t h ec a s e3o fp o i n t sa n dts i t u a t i o n ( 3 ) 若点s 在组件1 中，点t 在组件4 中，那么组件2 中既不包含点s ，又不 包含点t ，所以多边形p 是非u 己可视多边形，如图3 4 所示。 图3 4 点s 和t 的位置情形4 f i g 3 4t h ec a s e4o fp o i n tsa n dts i t u a t i o n 第3 章l r 可视多边形的特性 ( 4 ) 若点s 在组件1 中，点t 在组件5 中，那么组件2 和组件3 中既不包含点 s ，又不包含点t ，所以多边形p 是非l r 可视多边形，如图3 5 所示。 图3 5 点s 和t 的位置情形5 f i g 3 5t h ec a s e5o fp o i n tsa n dts i t u a t i o n 以上讨论了简单多边形p 内存在5 个组件，且多边形尸内无论哪个组件都与 其余2 个组件相交，其中点s 在组件1 中的情形，对于点s 在其他组件中的情形与 此类似，本文不再赘述。 定理3 1 明确给出了l r 可视多边形与其内部非冗余组件之间的关系，但是， 事实上，由于不能确定简单多边形p 中存在的组件数目，而且点s 和点t 的位置又 不确定，所以，很难运用这个定理来判断一个简单多边形是否为l r 可视多边形。 通过研究l r 可视多边形的一些特性，可以发现，多边形p 中的组件的构成及其数 量，对确定多边形p 是否为l r 可视多边形有着紧密的关系，作为一个研究结果， 本文给出了一些定理及其证明。 3 2 相关定理及证明 本文接下来论述给定多边形p 是非l r 可视多边形的必要条件。 简单多边形p 中若存在下列两种情况之一，则该多边形是非l r 可视多边形。 n 1 ：p 中存在三个互不相交的组件； 简单多边形内l r 可视问题的求解算法研究 n 2 ：p 中有放+ 1 2 ) 个非冗余组件存在，每个组件都和其它2 k e ( e 是大 于o 的偶数) 个组件相交。 引理3 1 ：若多边形尸满足条件n 1 ，即其内部有三个互不相交的组件存在， 则p 是非l r 可视多边形。 证明：若一个多边形内部含有三个互不相交的组件a 、b 、c ，可分为三各情 形加以论证：若点s 在a 中，点t 在b 中，由于三个组件互不相交，则c 既不 包含点s ，也不包含点t ，则该多边形为非l r 可视多边形。若点s 在b 中，点 t 在c 中，由于三个组件互不相交，则a 既不包含点s ，也不包含点t ，则该多边 形为非l r 可视多边形。若点s 在a 中，点t 在c 中，由于三个组件互不相交， 则b 既不包含点s ，也不包含点t ，则该多边形为非l r 可视多边形。上述情形如 图3 1 所示，其中每一个组件都被其左端点标出。证毕。 图3 1 满足条件n 1 情况 f i g 3 1t h ec o n d i t i o n sn 1 引理3 2 ：若多边形尸中有孔+ 1 似2 ) 个非冗余组件存在，且每个组件都和 其它2 k e ( e 是大于0 的偶数) 个组件相交( n 2 ) ，则p 是非l r 可视多边形。 证明：多边形p 边上存在两个点s 和t ，当且仅当p 上的每一个非冗余组件都 包含点s 或t 时，多边形p 才是l r 可视多边形。 设多边形p 有2 k + l 满足条件n 2 的非冗余组件，分别以其左端点为标记，记 为c l ，c 2 ，c 2 k + l ( k 苫2 ) 。首先考虑e = 2 的情况，如图3 2 所示，该多边形有5 第3 章l r 可视多边形的特性 个满足条件n 2 的非冗余组件。对于每一个组件c i ( 1s fs 放+ 1 ) ，分别用和吒来 表示其左端点和右端点，则c i 可表示为c i = p 【t ，】。现在将多边形尸上的2 七+ 1 个 组件映射为圆r 上相同数目的定向弦( 这里要求弦的两个端点都落在圆的边界上) ， 其中每个组件都用一条相应的定向弦来表示，并使所有弦上的端点在p 上的相对 位置与组件的端点在p 上的位置的顺序完全相同，每条弦的方向都由其相应组件 所决定，从其左端点t 指向右端点。图3 3 ( a ) 是图3 2 根据以上规则映射到圆r 上的效果图。 图3 2 满足条件n 2 的情况 f i g 3 2t h ec o n d i t i o n sn 2 由图3 3 ( a ) 可以看出，每个非冗余组件都精确地与另外2 ( k 1 ) 个组件相交，圆 r 上与p 中组件相对应的2 k + 1 条弦的所有端点也可以看作是一个规则的( 4 k + 2 ) 角 形的顶点。从圆r ( 多边形p ) 上的这2 k + l 条弦( 组件) 的对称性可看到另一个特别的 现象，即每个组件p 【f f ，】都包含包括其本身端点和在内的k 个左端点和k 个右 端点，并且这些组件( 弦) 的左右端点是交替出现的，一个左( 右) 端点的后面跟着的 一定是一个右( 左) 端点。因此，研，】中的任何一个点p 至多被包含在k 个非冗余 组件中。( 若除了组件研，】本身以外，有忍个端点( 无论左端点还是右端点) 被包 含在p 【，】内的组件包含点p ，则同样也有咒个端点( 无论左端点还是右端点) 被包 含在p 【，】内的组件不包含点p 。) 以上分析可以看出，两个不同点s 和t 最多只能 被包含在2 k 个组件中。于是，可得出该多边形存在一个组件既不包含点s ，也不 包含点t 。因此，依据定理3 1 可以知，多边形p 是非l r 可视多边形。 简单多边形内l r 可视问题的求解算法研究 r 2 l s f 2 啦 图3 3 多边形上组件到圆上弦的映射 f i g 3 3m a p p i n gt h ec o m p o n e n t so npi n t od i r e c t e dc h o r d so fac i r c l e 对于e 4 的情况，如同上面所描述的状况，对于多边形边上的任意点对