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

来源 :大连海事大学 | 被引量 : 0次 | 上传用户:kmyzchenpeng
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
LR可视性问题是计算几何领域的重要研究课题之一。通过对LR可视多边形特性的研究,能够得到求解计算几何经典问题的有效算法。因此,对于LR可视多边形的研究,不仅具有重大的理论研究意义,而且也有非常重要的实际应用价值。本文在论述简单多边形分割的相关理论的基础上,对简单多边形的LR可视性的判别问题进行了深入的研究,给出了判别一个简单多边形是否为LR可视多边形的充分必要条件,并加以严格证明。通过将LR可视多边形上的非冗余组件架构映射成一组圆上的弦,给出了LR可视多边形所具有的简单特性。通过这些特性,本文提出了一个时间复杂度为O(n)的计算LR可视多边形内部非冗余组件数目的算法,通过该算法以及判别一个简单多边形是否为LR可视多边形的充分必要条件,可以在线性时间内判断一个简单多边形是否具有LR可视性。这大大简化了利用找出多边形内的点对来判断多边形是否具有LR可视性的这一已知算法。为了验证算法的可行性和有效性,本文针对测试数据求解出了简单多边形内部非冗余组件,并判断该多边形是否具有LR可视性,并对算法运行结果进行了分析显示。结果表明,本文所给出的算法,不仅是高效的,而且切实可行。
其他文献
在网络环境日益复杂的今天,如何确保通信双方的会话安全成为人们日益关注的问题之一。密钥建立协议是指两个或多个参与者在公开的网络上建立临时的秘密会话密钥的过程。密钥
随着无线传感器网络的不断发展,其应用范围也越来越广泛。由于无线传感器网络节点通常部署在缺乏物理保护或者敌对的环境中,因此当传送敏感数据时尤其需要考虑其安全性。但是由
椭圆曲线密码(ECC, Elliptic Curve Cryptography)是一种杰出的公钥密码体制。它具有众所周知的优势,在智能卡、无线网络和嵌入式系统等资源受限的设备中有广泛的应用。在ECC
社会关系网络承载着人们在生产生活中形成的各种关系,随着互联网的发展,这种社会关系逐渐渗入到网络系统中,形成了复杂网络。复杂网络是人们的各种社会关系在网络中的体现,是复杂
随着网络通信技术的发展,以太网在控制领域的应用越来越广泛。传统的监控设备大多采用符合RS-232标准的串行接口,面临着RS-232转换10BaseT联网数据集中、接入、控制和二次开发
随着电子商务和企业信息化的迅猛发展,企业积累了多种异构信息系统。为了适应经济全球化进程,便于企业之间的信息交流和业务往来,企业不仅需要集成内部的遗留系统,而且需要构
装箱问题简单地说就是按一定规则将若干物体互不重叠地放入有一定容量的容器中,并达到某种最佳目标的问题。装箱问题无处不在,被广泛地应用于计算机科学、工业领域和管理科学
随着信息技术的发展和普及,越来越多的业务应用系统在计算机网络中投入运行,给人们的数据处理和管理工作带来了便捷。但是由于信息技术发展的历史性原因和应用的差异性等因素,导
由于硬件设备和环境等因素的限制,很多情况下,我们采集到的图像分辨率并不理想。如果通过改进硬件设备或改善图像的采集环境来提高图像的分辨率,代价可能比较高甚至是不现实
无线传感器网络(wireless sensor network,简称WSN)是计算机科学一个重要的研究领域。由于无线传感器网络布散节点数量庞大、监测区域环境限制及节点自身构造等因素,布散后节点