简单多边形内LR可视问题的求解算法研究.pdf

《简单多边形内LR可视问题的求解算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、分类号UDC密级单位代码!Q151简单多边形内LR可视问题的求解算法研究韩冰指导教师蒋波职称学位授予单位教授大连海事大学申请学位级别工学硕士学科(专业)计算机科学与技术论文完成日期2011年5月答辩日期2011年7月答辩委员会主席舢。缎theSimplePolygonAthesisSubmittedtoDalianMaritimeUniversityemlnInpartialfulfillmentofrequirementsfordegreeofMasterofEngineeringHanBing(ComputerSoftwareandTheory)The

2、sisSupervisor：ProfessorJiangBoMay，2011大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成博／硕士学位论文．==筵望多垫形凼堡亘塑闷墅的壅鲤簋洼婴究：。除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明的法律责任由本人承担。学位论文作者签名：．学位论文版权使用授权书本学位论文作者及指导教师完全了解大连海事大学有关保留、

3、使用研究生学位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本学位论文收录到《中国优秀博硕士学位论文全文数据库》(中国学术期刊(光盘版)电子杂志社)、《中国学位论文全文数据库》(中国科学技术信息研究所)等数据库中，并以电子出版物形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。本学位论文属于：保密口在——年解密后适用本授权书。不保密口(请在以上方框内打

4、“√")论文作者签名：微导师签名：日期：M中文摘要摘要LR可视性问题是计算几何领域的重要研究课题之～。通过对LR可视多边形特性的研究，能够得到求解计算几何经典问题的有效算法。因此，对于LR可视多边形的研究，不仅具有重大的理论研究意义，而且也有非常重要的实际应用价值。本文在论述简单多边形分割的相关理论的基础上，对简单多边形的LR可视性的判别问题进行了深入的研究，给出了判别一个简单多边形是否为LR可视多边形的充分必要条件，并加以严格证明。通过将LR可视多边形上的非冗余组件架构映射成一组圆上的弦，给出了LR可视多边形所具有的简单特性。通过这些特性，本文提出了一个

5、时间复杂度为O(n)的计算LI之可视多边形内部非冗余组件数目的算法，通过该算法以及判别一个简单多边形是否为LR可视多边形的充分必要条件，可以在线性时间内判断一个简单多边形是否具有ut可视性。这大大简化了利用找出多边形内的点对来判断多边形是否具有LR可视性的这一已知算法。为了验证算法的可行性和有效性，本文针对测试数据求解出了简单多边形内部非冗余组件，并判断该多边形是否具有LR可视性，并对算法运行结果进行了分析显示。结果表明，本文所给出的算法，不仅是高效的，而且切实可行。关键词：简单多边形；LR可视性；可视多边形；非冗余组件LR-visibilityprobl

6、emisoneofthemostimportantproblemsofcomputationalgeometry．ResearchingonthecharacterofLR—visibilitypolygon，itcanhelppeopledeveloptheeffectivealgorithmoftheseclassicproblems．Therefore，theresearchonthepolygonshasnotonlythetheoreticalsignificance，butalsothepracticalvalue．Basedonthechar

7、acteristicsofthesimplepolygons，thispapermainlyresearchthecharacterofLR—visibilitypolygonandwhetherthesimplepolygonisornot．Then，wegivethenecessaryandsufficientconditionstodeterminewhetherasimplepolygonisLR-visibility，andstrictlyproveit．Inthispaper，wegiveasimple，explicitcharacteriza

8、tionofpolygons．Itisobtainedbymapp