（计算机应用技术专业论文）多边形搜索的几种策略研究.pdf

j1-11 b e ( l a n z h o uu n i v e r s i t yo ft e c h n o l o g y ) 2 0 0 7 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e d n g c o m p u t e ra p p l i c a t i o nt e c h n o l o g y i n t h e g r a d u a t es c h o o l l a n z h o uu n i v e r s i t yo ft e c h n o l o g y s u p e r v i s o r p r o f e s s o rz h a n g y u a n p i n g j u n e ，2 0 1 1 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担 作者签名：鸯确 日期：如，年多月弓日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权兰州理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授 权中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并 通过网络向社会公众提供信息服务。 作者签名： 导师签名： 日期：，年6 月弓日 日期：却r ，年月易日 目录 摘要 i a b s t r a c t 】 i 常用符号 插图目录v 表格目录v i 第1 章绪论1 1 1 课题背景及研究意义1 1 2 基本概念3 1 3 多边形搜索问题的描述5 1 4 多边形搜索问题的研究现状7 i a 1 在线多边形搜索7 1 4 2 离线多边形搜索8 1 5 本文的研究内容与组织结构1 2 第2 章基本概念与引理_ 1 3 2 1 双切线的定义1 3 2 2 可视空间1 5 2 3 可视图1 6 2 4 骨架v 图1 8 2 5 简化骨架v 图1 8 2 6v 图中的搜索路径2 0 2 7 本章小结2 3 第3 章多边形的边界单线搜索特性2 4 3 1 检测特性2 4 3 2 时间复杂度分析2 8 3 3 本章小结2 9 第4 章边界单线搜索算法3 l 4 1 反射点的受限性3 1 4 2 边界单线搜索算法3 3 附录( 攻读学位期间所发表的学术论文目录) 4 5 硕十学位论文 摘要 多边形搜索是计算几何中的一类基本问题，这类问题考虑的是如何利用一个 或多个移动的搜索者( 搜索者有不同的视觉范围) 对一个多边形区域进行搜索以便 检测到移动的入侵者。搜索者和入侵者均可用一个点表示，都可以在多边形区域内 连续、任意地移动，但是后者的移动速度要比前者快。 多边形搜索问题与机器人技术相结合被广泛应用于航海，安全防御，目标探测 和追踪等诸多领域。因此，对于一个给定的多边形，判断其是否可被一个或多个不 同视觉的搜索者搜索，以及如何找出一条有效的搜索路径显得尤为重要。 本文主要研究的是用一个边界单线搜索者( 1 s e a r c h e r ) 对一个含有礼条边的简 单多边形的搜索问题。所谓边界单线搜索者，是指搜索者只能沿多边形的边界移动 且从其位置只能发出一束光。作为一种特殊类型的搜索模型得到了许多学者的研 究，虽然已经提出了一些检测和搜索算法，但各个算法还是存在一些不足。本文在 对多边形边界单线搜索的研究现状和存在的不足进行深入分析的基础上做了以下 工作： 首先，阐述了多边形搜索问题的相关概念，并将双切线与多边形的可视图( y 图) 联系构造了简化骨架y 图。 其次，针对边界单线搜索问题，给出了检测多边形的边界单线可搜索性的充要 条件。利用这些条件判断一个多边形是否可被一个边界单线搜索者搜索只需d ( n ) 的时间和空间，改进了以前的时间复杂度o ( n t o g n ) 。此时间复杂度是检测多边形 边界单线可搜索性的下界，已不可能再优化。同时，对这些特性的正确性用简化骨 架y 图论证，简化了已有的证明过程。 最后，给出了一种新的边界单线搜索算法，并对此算法进行了详细的描述。同 时，证明了用该搜索算法输出一个搜索方案只需o ( m ) 的时间，其中仇( n 2 ) 为搜 索指令的数目，优于以前o ( n l o o n + i ) ( j 3 n 2 ) 时间的算法。此外，还证明了边 界单线搜索者利用此算法搜索多边形所走过的路径最短，最长路径小于2 i a p i ，其 中i 卯i 为多边形边长总和。 关键词：多边形搜索；单线搜索；边界搜索；搜索方案 a n d f r e e l yw i t h i nap o l y g o n a lr e g i o n ，w h e r et h el a t t e rc a n m o v e a r b i t r a r i l yf a s t e rt h a nt h e f o r m e r p o l y g o ns e a r c hp r o b l e mw h i c hc o m b i n e sw i t ht h er o b o tt e c h n o l o g yi sw i d e l yu s e d i nm a n ya r e a s ，s u c ha sn a v i g a t i o n ，s e c u r i t yd e f e n s e ，t a r g e td e t e c t i o na n dt r a c k i n g ，a n ds o o n t h e r e f o r e ，f o rag i v e np o l y g o n ，t od e t e r m i n ew h e t h e ri tc a l lb es e a r c h e db yo n eo r m o r es e a r c h e r sw i t hv a r i o u sl e v e l so fv i s i o n ，a n dh o wt of i n dam o r ee f f e c t i v es e a r c hp a t h i sv e r yi m p o r t a n t i nt h i sp a p e rw ec o n s i d e rt h ep o l y g o ns e a r c hp r o b l e mb yu s i n gab o u n d a r y1 一 s e a r c h e r , w h oh a sas i n g l ef l a s h l i g h ta n di so n l ya l l o w e dt om o v ea l o n gt h eb o u n d a r y o fas i m p l ep o l y g o nw i t hne d g e s a sas p e c i a lc a s eo ft h ep o l y g o ns e a r c hp r o b l e m , i t a t t r a c t e dm u c ha t t e n t i o no fm a n ys c h o l a r s ，a n do b t a i n e ds o m ec h a r a c t e r i z a t i o n sa n dt h e s e a r c ha l g o r i t h m ，b u tt h e r ea r es o m ed e f i c i e n c i e si nt h e m b a s e do ni n d e p t ha n a l y s i so f t h er e s e a r c hs t a t u sa n dt h ed i s a d v a n t a g eo ft h ep r o b l e m , w ec o n c l u d eo u rm a i nr e s u l t sa s f o l l o w s f i r s t ，t h er e l a t e dc o n c e p t so ft h ep o l y g o ns e a r c hp r o b l e mt ob ei n t r o d u c e d m o r e 一 0 v e t h ep m n e ds k e l e t o nyd i a g r a mc a nb ec o n s t r u c t e db yu s i n gan e wm e t h o dw h i c h c o m b i n e st h eb i t a n g e n tw i t ht h ev i s i b i l i t y ( v ) d i a g r a mo ft h ep o l y g o n s e c o n d ，f o rt h ep r o b l e mo fs e a r c h i n gas i m p l ep o l y g o n a lr e g i o nw i t hab o u n d a r y1 - s e a r c h e r t 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 sf o rt e s t i n gt h es e a r c h a b l i t yo fp o l y g o n s a l ep r o p o s e d i ti ss h o w e dt h a tw h e t h e ra p o l y g o n i ss e a r c h a b l eb yab o u n d a r yl - s e a r c h e r c a nb ed e t e c t e di nd ( 他) t i m ea n ds p a c eb yu s i n gt h e s ec o n d i t i o n s t h er e s u l t si m p r o v e t h ep r e v i o u so ( n l o g n ) t i m eb o u n d s t h i si st h eb e s tr e s u l tu n t i ln o w a tt h es a m et i m e ， s o m ek n o w np r o v i n gp r o c e s s e sa r es i m p l i f i e db yu s i n gt h ep r u n e ds k e l e t o ny d i a g r a m t h i r d ，a n o v e ls e a r c ha l g o r i t h mi sp r e s e n t e d ，a n dt h ep e r f o r m a n c eo fi ti sd e s c r i b e d i nd e t a i l m e a n w h i l e ，w ep r o v et h a tt h ea l g o r i t h mc a ng e n e r a t eas e a r c hs c h e d u l ew i t ht h e t i m ec o m p l e x i t y0 ( m ) ，i fi te x i s t s ，w h e r em ( 0 时的位置，且入侵者的信息是无法预知的，即他的最初位置( 0 ) 和移 动路线对于搜索者来说都是未知的，其移动速度也可比搜索者的移动速度快很多。 一个多边形中可以有一个或多个入侵者。 若入侵者所表示的点被搜索者发出的光束照到，则入侵者被发现，搜索完成。 一个搜索方案盯= ( f ，8 ) 在时间t 【0 ，1 】内探测到i ，当且仅当，( t ) 在时刻t 被光 束照到，即i ( t ) s ( t ) ，( ) 。多边形p 是可搜索的当且仅当存在一个搜索方案c l r 能 探测到所有的入侵者。 在时间t ( 【0 ，1 】) 内执行一个搜索方案仃使得多边形p 的部分区域被清理干 净，当且仅当此部分区域内没有未被探测的入侵者。特殊地，一个点p p 是在时 刻t 是被清理干净的，当且仅当每个使得x ( t ) = p 的入侵者j 在某个t 的时间 都被探测到。一个区域是被清理干净的( c l e a r ) ，当且仅当此区域中的每个点都是被 6 硕士学位论文 清理干净的。相反，则称为此区域是被污染的( c o n t a m i n a t e d ) 。如果一个已经清理干 净的局域再次被污染，则称为局域的再次污染( r e , c o n t a m i n a t e d ) 。 解决多边形搜索问题的关键是要找到一种最优的搜索策略。对一个多边形的 搜索策略可以有多种，每种搜索策略都包含了一个或多个搜索者连续搜索路径的详 细说明。下面先介绍几类特殊的多边形，之后，介绍多边形搜索问题的研究现状。 设尹为一个简单多边形，乱和口为p 中两个不同的顶点，三和冗分别表示卯 上从缸到钉的顺时针和逆时针边界链，即l = 卯 伽心，7 3 ，r = 心，7 3 。如果 工和兄相互勉强可见，即l 上每一点从r 上某些点可见，反之亦然；则称p 为 关于点对( 让，口) 的l r 可见多边形( l r - v i s i b i l i t yp o l y g o n ) ，也称为街多边形( s t r e e t p o l y g o n ) 埘。 把预先在o p 上设立一个入点的简单多边形称为房间( r o o m ) ，此入点称为门点 ( d o o r ) n 卿。 上述街和房间都是一类特殊的简单多边形，它们具有一般的简单多边形所没 有的一些特性。因此，对于有些搜索者模型，可以搜索这类特殊的多边形，但却无 法搜索普遍意义上的简单多边形，所以在此加以区分。强调一点，本文中研究的多 边形是普遍意义上的简单多边形，只是在下面研究现状中对它们分别进行了介绍。 1 4 多边形搜索问题的研究现状 多边形搜索问题自1 9 9 2 年由s u z u k i 和y a m a s h i m 提出以来u 1 ，在近年内得到 了很多学者的关注，也取得了一些成果。以下分在线( o n 1 i n e ) 和离线( o f f - l i n e ) 两 种情况对多边形搜索问题的研究现状进行分析。( 如无特殊说明均指搜索目标是移 动的) 1 4 1 在线多边形搜索 在很多应用中，机器人必须在搜索环境( 被搜索区域的形状) 和目标点所在位 置未知的情况下完成其搜索任务。因为机器人必须在其仅掌握局部可视环境信息 的基础上做出搜索的下一步决定，所以可认为未知区域内的目标搜索问题为一在 线问题，称这种搜索为在线搜索( o n 1 i n es e a r c h i n g ) 。 在线多边形搜索最早是在2 0 0 1 年由l a v a l l e 等人在文献【2 0 ，2 l 】中提出的，主 要是对一些未知简单区域的在线搜索问题。l a v a l l e 等人考虑用一个全视觉搜索者 配备一个间距检测器来检测边界区域可视部分的不连续点。但这种方法首先必须 在线创建一个搜索区域的全图，然后再利用指数时间的离线算法对其进行搜索以 产生一个搜索方案。若对一个有n 条边的多边形，在线构造该多边形的全图需要 o ( n ：3 ) 的时间瞄1 。所以，总的时间和空间开销都是他的指数。 7 多边形搜索的几种策略研究 之后，p a r k 等人在文献【2 3 】中将l a v a l l e 等人提出的在线算法的时间复杂度降 低到了o ( n 2 1 。 2 0 0 3 年，k a m e d a 等人在文献【2 4 】中提出了用一个边界单线搜索者在线搜索 一个未知的多边形区域的算法。此算法无需构造多边形的全图，而是利用了贪心策 略不断的扩大当前已经被清理干净的子多边形区域。这个算法可用一种具有六种 状态( s i x s t a t e ) 的在线自动搜索机来进行检测。如果一个多边形是可搜索的，则此 在线自动搜索机环绕多边形边界移动不到2 - - 3 周便可搜索完整个多边形。但如果 此多边形不可搜索，则在线自动搜索机会一直循环检测下去而无法停止，因为它意 识不到此多边形是不可搜索的。 2 0 0 6 年，k a m e d a 等人在文献【1 5 】中将上述算法进行改进，用一种具有七种状 态( s e v e n - s t a t e ) 的在线自动搜索机来进行检测。 1 4 2 离线多边形搜索 在实际中，用现有的一些工具很容易确定所需研究多边形的一些信息，比如 多边形的形状等，因而只需研究出一条更优的搜索路径或者一种更有效的搜索方 案来搜索整个区域，使得移动的入侵者最终被发现。这种搜索为离线搜索( o f f - l i n e s e a r c h i n g ) 。下面对离线多边形搜索根据不同的模型分别进行介绍。首先给出了一 些离线多边形搜索问题的研究总结，如下表所示。 表1 1 离线多边形搜索问题研究总结 i 搜索者的类型街房间多边形含一个洞的多边形 一个全视觉搜索者可行( a ，c )可行( a ，c )可行( a ，c ) 不可行 一个边界单线搜索者 可行( a ，c )可行( a ，c ) 可行( a ，c ) 不可行 一个非边界单线搜索者不可行不可行不可行不可行 两个搜索者可行( a ，c )可行( a ，c )可行( a ) 不可行 两个边界单线搜索者可行( a )可行( a )可行( a )可行( a ) 两个非边界单线搜索者 可行( a )可行( a )可行( a ) 不可行 在表1 1 中，每一行代表了一种搜索模型，每一列代表一种类型的多边形搜索 硕士学位论文 索多边形的一些特性已经获得。下面就表1 1 中所示的各类问题做一些具体的研究 现状介绍。 1 一个全视觉搜索者( o o s e a r c h e r ) 模型 全视觉搜索者的视觉范围为3 6 0 。，就是从搜索者的位置可以发出无穷多束 光。在许多文献中已经证明了一个全视觉搜索者的搜索能力与一个二线搜索者( 2 s e a r c h e r ) 的搜索能力是等价的1 。也有文献已证明如果一个多边形可被一个全 视觉搜索者搜索，则它肯定能被一个边界单线搜索者搜索网。 c r a s s 等人在文献【2 9 】中研究了用全视觉搜索者来搜索一个街( s t r e e 0 的问题， 在此文章中提出了检测街可搜索性的一些必要条件，并由此得到一个搜索方案。 l e e 等人讨论了对一个房间( r o o m ) 的搜索问题，也获得了相应的检测特性和 搜索算法噼1 。 用全视觉搜索者对一个简单多边形的搜索，p a r k 等人首次进行了研究，并提出 了可搜索多边形的检测算法和其具备的一些特性冽。g u i b a s 等人在文献【3 0 】中提 出了另一种新的基于图的算法来检测多边形的可搜索性，但是没有给出相应的特 性。2 0 0 9 年，t a n 在文献【1 7 】中提出了几种不能被全视觉搜索者搜索的多边形情 形，并对其进行了证明。 针对多边形中含有一个洞的情形，如何用一个全视觉搜索者对其进行搜索，截 至目前还没有文献给出相应的特性。 2 一个非边界的单线搜索者模型 在这种模型中，搜索者可以在多边形的内部自由的移动，不一定一直保持在多 边形的边界上移动。对于含有一个洞的多边形，不论单线搜索者沿不沿边界搜索， 也不论按什么方案搜索，入侵者都可以移动到他已经搜索过的区域中，造成区域的 再次污染。而对于街、房间和一般多边形的搜索问题，在一般意义上它们都是无法 被一个非边界单线搜索者搜索的。所以，表1 1 单元格中都显示不可行。但根据两 点之间相互可见性的定义不同，或许在一些特殊情形下它们是可以被搜索的，但目 前还没有关于这方面的研究文献。 3 两个边界单线搜索者模型 关于两个边界单线搜索者对街和房间等方面的搜索，还没有很多的研究结果。 只有在文献【3 1 - 3 3 】中，s i m o v 等人讨论了用两个单线搜索者对简单多边形的搜索 问题，并给出了相应的搜索算法。但是在这些算法中并不要求搜索者必须保持在多 边形的边界上移动，也不要求搜索者在搜索过程中始终保持相互可见。 在2 0 0 5 年z h a n g 在文献【3 4 】中用两个边界单线搜索者搜索含有一个洞的多 边形。此文中也是利用了基于图的思想，并且z h a n g 推测死锁序列可以确定含一个 洞多边形的可搜索性，但没给出相应的特性。 9 多边形搜索的几种策略研究 4 两个非边界的单线搜索者模型 对于两个非边界的单线搜索者模型，最初是由s i m o v 等人提出了一种基于图的 算法检测多边形的可搜索性，但只是提出了搜索算法，却没有给出相应的特性口k 埘。 对于其它一些特殊类型的多边形搜索问题，如街，房间，含一个洞的多边形，至今 没有给出任何的研究结果。 5 两个搜索者模型 在两个搜索者模型中，两个搜索者始终在多边形的边界上移动，并且要保证搜 索过程中两者的相互可见性。因此，他们的可视范围只能限制在两个搜索者之间所 连的线段。在这一模型中，两个搜索者从多边形的一个入口( 顶点) 进入，然后沿多 边形的左右边界链l 和r 分别搜索，两者之间可以看成是有一条光束，如果入侵 者被光束照到，则搜索完成，在出口处两者汇合。 i e k i n g 和k l e i n 首次讨论了用两个搜索者对街的搜索，针对许多不同的情形进 行了分析，并给出了一个o ( n l o g n ) 时间的算法来检测一个街是否能被两个搜索者 搜索网。之后，h e f f e m a n 将上述时间复杂度降低到线性时间阁。在文献【1 6 ，3 7 】中 对其它的一些方面做了更深层次的研究。 p a r k 等人在文献【3 8 ，3 9 中讨论了用两个搜索者对一个房间的搜索，提出了一 个o ( n l o g n ) 时间的算法来检测一个房间的可搜索性，并给出了可搜索房间所满足 的一些特性。 后来，z h a n g 在文献【3 4 中利用基于图的思想研究了房间搜索问题。将l a v a u e 等人提出的可视障碍图( v i s i b i l i t yo b s t r u c t i o nd i a g r a m ) 陬舢1 进行了简化，因而可 以从简化图上方便的找到一条房间的搜索路径，并将房间搜索的时间复杂度降到 d ( n ) 。而且z h a n g 还讨论了对于一个房间如何找到所有可以作为搜索入点的顶点， 即哪些点可以作为房间的门。在此文章中，z h a n g 证明了可以在o ( n ) 的时间内找 到所有的门点。对此问题后来还有更进一步的研究，可参考文献【1 9 ，4 3 ，4 4 。 2 0 0 7 年，b a h u n 等人在文献【4 5 】中提出了一种新的算法来找到一个最优的房 间搜索方案，这个算法也利用了可视障碍图的思想，但是要求两个搜索者必须相互 可见。在这篇文章中，证明了找到一条最短路径的搜索方案需要o ( n 2 1 的时间，找 到一个最快的搜索方案需o ( n 4 ) 的时间。 用两个搜索者对一个多边形的搜索是一个边界单线搜索者搜索问题的子集h ， 即一个多边形能被一个边界单线搜索者搜索，则它肯定能被两个搜索者搜索，反之 则不一定成立。因为在搜索中必须保持两个搜索者的相互可见性，且两搜索者的移 动路线都是连续的，不像单线搜索者的光束可以发生转跳。反映在骨架y 图上就 是搜索路径不能穿过图中任意的线段，而对单线搜索者而言，搜索路径可以从右到 左穿过一条垂直线段，这将在第2 章进行详细介绍。 1 0 硕十学位论文 2 0 0 8 年，t a n 等人在文献 4 6 】中提出了多边形可被两个搜索者搜索的一些特 性，解决了文献【3 8 】中提出的公开问题，并证明只需o ( n ) 的时间便可检测出一个给 定多边形的可搜索性。若多边形是可搜索的，找到一个搜索方案只需o ( n l o g n + m ) 的时间，其中几为多边形的顶点数，m ( n 2 ) 为搜索指令的数目。之后，在文献【4 7 】 中，z h a n g 通过提出了几种禁止模式，给出了哪些类型的多边形是不可被两个搜索 者搜索的。 由于两个搜索者模型在搜索中必须保持两者的相互可见性，因此无法对一个 含洞的多边形进行搜索。 6 一个边界单线搜索者模型 用一个边界单线搜索者对街的搜索问题可以参考文献【4 8 】。对房间的搜索问 题，在文献 4 8 ，4 9 】中用不同的方法给出了相应的房间可搜索性检测算法，并获得 了一些可搜索房间的特性。而对含有一个洞的多边形，无法用一个边界单线搜索者 对其进行搜索。 用一个边界单线搜索者对多边形的搜索问题最初是由s u z u k i 和y a m a s h i t a 在 文献【l 】中提出的。在其中讨论了各种不同搜索者的情形，并提出了一些检测多边 形可搜索性的必要条件。而且证明了当多边形中存在三点使得任意两点之间的最 短路径从第三点不可见时，此多边形就不可被一个边界单线搜索者搜索。 之后，l a v a u e 等人在文献【4 0 ，4 l 】中提出了一种新的方法来解决多边形搜索问 题，它主要采用了基于图的思想。在此文章中首次提出了可视障碍图，并提出了与 可视障碍图拓扑等价的图一骨架障碍图( s k e l e t a lo b s t r u c t i o nd i a g r a m ) ，用此图可以 更明确地表示多边形的基本信息。对于一个有n 个顶点的简单多边形p ，l a v a u e 等 人提出了一个搜索算法，用此算法检测p 的可搜索性并输出一个搜索方案需o ( n 2 ) 的时间和空间。 与此同时，p a r k 等人和t a n 分别在文献【5 0 ，5 1 】中用不同的方法研究了多边形 的边界单线搜索问题，也得到了各自不同的检测多边形可搜索性的算法和一些特 征，但是没有证明说明他们的结论是等价的。 2 0 0 3 年，t a n 在文献【5 2 】中给出了三个充分必要条件来检测一个简单多边形 的边界单线可搜索性，根据这些条件判断一个多边形是否可被一个边界单线搜索 者搜索只需o ( n l o g n ) 的时间和o ( n ) 的空间。此外，若多边形是可搜索的，他还给 出了一个线性时间的搜索方案，但总的时间复杂度还是多项式时间。 2 0 0 6 年，k a m e d a 等人提出了三种不可被边界单线搜索者搜索的模式，类似于 文献 5 2 】中的特性，但利用扫描骨架y 图的思想对其证明，简化了文献【5 2 】的证 明过程。遗憾的是，用此特性检测多边形的边界单线可搜索性仍然需要o ( n l o g n ) 的时间，而且相应的搜索算法也未给出田。 多边形搜索的几种策略研究 2 0 0 9 年，t a n 在文献【1 7 】中利用了多边形中反射点的顺时针组成、逆时针组 成以及它们之间的一些关系。提出了多边形不可被一个边界单线搜索者搜索的一 些特性，并且利用这些特性可在o ( n ) 的时间和空间内检测出一个给定多边形的边 界单线可搜索性，改进了l a v a u e 等人m 4 1 1 的结果，但是证明过程比较复杂。而且 t a n 给出了一个搜索算法，若此多边形是可搜索的，则可在o ( n l o g n + i ) 的时间内 输出一个搜索方案，其中i ( 。 图2 4 可视空间 d 对于任意的z ，y r ，可视空间，简称y 空间，记为yf i $ , 2 4 | 它包含了直线y = z ( 开始线s ) 和y = z 1 0 7 i ( 目标线g ) 中间所夹的无限区域，如图2 4 所示，图 中d = l 印i 。因此我们有( z ，y ) y 当且仅当 z 1 0 p i y z 多边形搜索的几种策略研究 假设( a ，b ) y ，且( c ，国v 。如果b d ，则称点( a ，b ) 在点( c ，d ) 的北边，或 者( c ，d ) 在( a ，b ) 的南边。类似的，如果a c ，则称点( a ，b ) 在点( c ，d ) 的东边，或 者( c ，d ) 在( a ，b ) 的西边。 对于任意点( a ，b ) y ，观察其关于直线y = z 的对称点( b ，a ) ，因为a 与a d 在0 1 上表示同一个点，且b 与6 + d 在卯上也表示同一个点，所以( b ，a - d ) y 和( b + d ，a ) y 两点是对称的。特殊的，s 上的点( a ，a ) 与g 上的点( a ，a d ) 和( a + d ，a ) 也是对称的。 2 3 可视图 多边形的可视图( 简称y 图) 刚，是在v 空间中将部分区域用灰色表示且满足： 如果一个点( x ，y ) y 是灰色的，当且仅当z 和y 不能相互可见。我们用z 代表搜 索者的位置，用y 表示它所发出的光束终点所处的位置。由对称性可知，( 口，y 是灰色的当且仅当( b ，a d ) y 和( b + d ，a ) 1 夕也是灰色的。 以下说明怎样将一个简单多边形用y 图表示，多边形中的不可见区域都是由 反射点形成的，因此在y 图中只考虑反射点的信息，从而简化操作。首先在多边形 边界o p 上标识出每个反射点r 的向前扩展点f o r w ( r ) 和向后扩展点b a c k ( r ) 。然 后从任意一个边界点开始，将其作为始点，标识为0 ，并按顺时针计算每个反射点 以及它们的向前和向后扩