检索结果-内蒙古大学图书馆

作者：王茂林大连海事大学

学位级别：硕士

Voronoi图是一个关于空间划分的基础数据结构。作为计算几何的一个重要分支,它的应用越来越为人们所关注。100年来,它被应用在与几何信息相关的各个领域。随着计算机技术的普及和发展,Voronoi图的应用范围也在不断扩大。由于Voronoi图... 详细信息

Voronoi图是一个关于空间划分的基础数据结构。作为计算几何的一个重要分支,它的应用越来越为人们所关注。100年来,它被应用在与几何信息相关的各个领域。随着计算机技术的普及和发展,Voronoi图的应用范围也在不断扩大。由于 Voronoi图与一些自然结构十分相像,并具有惊人的数学特性,因此,它是解决相关几何问题强有力的工具,在气象、地质、测绘、考古、分子化学、生态学和计算机科学等领域中都对Voronoi图进行了广泛而深入的研究。通常意义下的Voronoi图是以欧氏距离为度量,对平面区域施行的一种分割, 这是一种不考虑障碍物的理想模式。然而,在现实世界中存在着许多自然或人为的障碍,使得两个目标物间无法直线通行。为了扩大Voronoi图的应用领域,本文对传统的Voronoi图进行了扩充,给出了一般图形障碍Voronoi图的定义。对于生成元为任意图形的线段障碍Voronoi图,由于其生成元形状的任意性, 使得构造算法比较复杂。本文运用图像处理的知识,先对给定的生成元进行边缘提取和边界跟踪,在此基础上,给出了一种基于生成元边界离散化的作图法,即先在各生成元边界上选取母点,利用点为生成元的线段障碍Voronoi图的离散作图法进行构造,从而得到生成元为任意平面几何图形的线段障碍Voronoi图。与其它算法相比,这种算法的实现不必考虑生成元的几何形状,无需复杂计算,无需考虑误差控制,因而更加实用,效率也更高。实验结果表明,该算法简单易行,具有较高的理论价值和应用价值。

关键词：计算几何离散构造一般图形线段障碍 Voronoi图

来源：评论

学校读者我要写书评

暂无评论

无线传感器网络中覆盖空洞的检测

无线传感器网络中覆盖空洞的检测

引用

作者：高昊太原理工大学

学位级别：硕士

无线传感器网络是由大量的、微小的传感器节点而构成,这些传感器节点是随机部署在监控区域中,通过自组织和无线通信的方式组成的分布式网络。无线传感器网络是随着传感器技术、无线通信、微电子机械系统的发展与相互融合而产生的。无线... 详细信息

无线传感器网络是由大量的、微小的传感器节点而构成,这些传感器节点是随机部署在监控区域中,通过自组织和无线通信的方式组成的分布式网络。无线传感器网络是随着传感器技术、无线通信、微电子机械系统的发展与相互融合而产生的。无线传感器网络也成为了近年来学术界的研究热点。无线传感器网络越来越多地被应用于各个领域,其中包括森林防火、智能建筑设施、目标监控和数据采集、智能交通运输等领域。无线传感器网络中的覆盖问题是无线传感器网络的一个基本问题,它反映的是无线传感器网络的感知能力和对目标区域的监测监控和数据采集的效果。无线传感器网络的传感器节点覆盖度是衡量无线传感器网络服务质量的一个重要评价标准。为了使得目标区域及其相关数据能够顺利地被无线传感器网络监测和采集,那么就需要保证网络中的传感器节点可以有效地覆盖被监测的目标区域。无线传感器网络覆盖空洞的检测是无线传感器网络覆盖问题的一个研究热点。由于传感器节点的随机部署未能够完全地覆盖监测区域,或者传感器节点的故障、能量耗尽等原因都可能导致节点失效,进而造成传感器节点不能完全覆盖监测区域,这些未被传感器节点覆盖的监控区域是覆盖空洞。无线传感器网络中覆盖空洞会造成监测数据的不完整,从而可能会对最后的决策产生影响。因此应当尽量避免在目标区域中产生这样的覆盖空洞,即使当无线传感器网络中出现覆盖空洞时,也应当立即检测和寻找,以保持无线传感器网络的感知和通信等服务质量。针对无线传感器网络中覆盖空洞的检测,虽然目前国内外学者已经提出了一些无线传感器网络覆盖空洞的检测算法,但是这些算法都存在一些不足,因此本文提出了一种改进的基于几何图形的分布式覆盖空洞检测算法,并且从理论上证明了该算法能够有效地检测无线传感器网络的覆盖空洞。算法的基本思想是以任意一个传感器节点和它的两个邻居节点构成三角形,计算三角形的外接圆半径和外接圆圆心,根据几何图形学的相关理论判断节点附近是否存在覆盖空洞。为了验证本文算法的有效性和检测准确率,对本文的算法在模拟软件MATLAB上进行了实际的实验仿真。仿真实验结果表明,算法不仅能够有效地检测出覆盖空洞和边界节点,而且也具有更高的检测准确率。

关键词：无线传感器网络覆盖空洞空洞检测分布式算法计算几何

来源：评论

学校读者我要写书评

暂无评论

曲面三角网格表示的数据结构优化研究

曲面三角网格表示的数据结构优化研究

引用

作者：张岩大连理工大学

学位级别：硕士

计算几何是一门重要的边沿学科,与计算数学,微分几何,代数几何等紧密相关,其理论成果在CAD/CAM/CAE,图像处理,计算机图形学,科学可视化等许多科学和工程领域都有重要的应用。本文首先介绍了计算几何的定义和其中的经典问题Voronoi图... 详细信息

计算几何是一门重要的边沿学科,与计算数学,微分几何,代数几何等紧密相关,其理论成果在CAD/CAM/CAE,图像处理,计算机图形学,科学可视化等许多科学和工程领域都有重要的应用。本文首先介绍了计算几何的定义和其中的经典问题Voronoi图和Delaunay三角剖分。包括Delaunay三角剖分的优化准则,发展现状及相关的算法。在此基础之上对曲面重建中的三角网格曲面模型生成的算法零集法,α-shape法和Crust算法进行了详细的讨论和比较。网格曲面模型的表示即它所采用的数据结构是曲面问题研究的基础,比如曲面细分问题的研究和特征检测问题的研究都与数据结构紧密相关。本文介绍了网格,网格曲面的定义,对已有的网格曲面模型数据结构包括Winged-Edge,Half—Edge,Quad-Edge,Comer Table等数据结构进行综述。最后,本文提出了一种新的基于邻接表存储的网格模型数据结构,给出了它的数据结构和基本的运算。这种数据结构具有创建快速的特点,可以方便地获取网格中邻接顶点、边和面的连接信息并且有较高的时间和空间效率并进行了算法复杂度的理论分析和比较。

关键词：计算几何曲面重建网格数据结构邻接表

来源：评论

学校读者我要写书评

暂无评论

无光能损失的透镜设计算法与实现

无光能损失的透镜设计算法与实现

引用

作者：姚远大连理工大学

学位级别：硕士

近年来,随着生活的极大丰富,人们对透镜成像有了更高的要求,除了照明外,我们也希望能赋予其传递信息的能力,即成像。但目前成像方式大多靠遮挡光源实现,这种方法会造成大量的光能损失。鉴于这些问题,本文设计了透镜成像算法,使光线重新... 详细信息

近年来,随着生活的极大丰富,人们对透镜成像有了更高的要求,除了照明外,我们也希望能赋予其传递信息的能力,即成像。但目前成像方式大多靠遮挡光源实现,这种方法会造成大量的光能损失。鉴于这些问题,本文设计了透镜成像算法,使光线重新分配,达到无光能损失的透镜成像方式。为了解决透镜问题,本文创新性地将平面最优传输理论拓展到二次曲面上,构造了数学模型,并设计了算法将数学模型求解。文章将椭球面及双曲面纳入到球面最优传输理论的计算过程中,并提出一个计算模拟透镜的网格胞腔的算法。首先通过图像初始化一个虚构的单位球冠网格上每个顶点的目标测度,接着使用球面最优传输理论利用几何算法或蒙特卡洛采样法估算出虚拟的胞腔面积,得到球面的胞腔分解及球面的加权图,并使用球面最优传输理论迭代计算出每个网格顶点的权重,通过权重最后得到由球面参数化形成的每个胞腔对应的椭球面或双曲面,对这些曲面求包络即可得到最终透镜。本文设计的算法,通过成功实现给定图像的灰度图成像,证明了算法的可行性,并为后续彩色图的成像打下了基础。目前主流透镜是通过人为减少成像所使用的光强进行精确成像,这种方式会造成大量的光能损失,而本文设计的透镜是通过控制光的折射方向进行成像,在成同等亮度图像的时候需要的光能较少,因此本设计在对光能损失较为敏感的大规模成像上有着十分重要的意义。

关键词：三维网格球面最优传输理论计算几何

来源：评论

学校读者我要写书评

暂无评论

寻求简单多边形凸壳的线性时间算法

引用

计算机工程与科学 2002年第3期24卷 1-2,44页

作者：周培德付梦印北京理工大学计算机系北京100081

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选 ,使剩余顶点的角的大小排成递增序 ,然后用Graham扫描方法删去非凸壳顶点 ,最后得到多边形凸壳的顶点序列。第二个算... 详细信息

本文提出在线性时间内构造简单多边形顶点凸壳的两种算法。第一个算法的基本思想是利用一种技巧对多边形顶点进行筛选 ,使剩余顶点的角的大小排成递增序 ,然后用Graham扫描方法删去非凸壳顶点 ,最后得到多边形凸壳的顶点序列。第二个算法不断删去多边形的凹点及新产生的凹点 ,最后得到凸壳顶点序列。这两种算法简单 ,易于实现 ,时间复杂性都是O(n)

关键词：简易多边形凸壳线性时间算法复杂性计算几何

来源：评论

学校读者我要写书评

暂无评论

基于凸链存储的不相交线段序列的最优遍历算法

基于凸链存储的不相交线段序列的最优遍历算法

引用

作者：罗娅大连海事大学

学位级别：硕士

本文针对平面上不相交线段序列的最优遍历问题进行研究,目标是要寻找一条从给定起点出发,依次遍历每一条线段,最终到达给定终点的最优遍历路径。该问题也是一个欧几里德最短路径(ESP)问题,是计算几何领域的一个理论问题,也是很多实际应... 详细信息

本文针对平面上不相交线段序列的最优遍历问题进行研究,目标是要寻找一条从给定起点出发,依次遍历每一条线段,最终到达给定终点的最优遍历路径。该问题也是一个欧几里德最短路径(ESP)问题,是计算几何领域的一个理论问题,也是很多实际应用问题的抽象模型。研究高效的求解该问题的方法,不仅具有重要的理论意义,而且也具有很高的实际应用价值。本文在综述本领域相关研究成果的基础上,指出了运用Rubber-band算法求解该问题时可能产生振荡现象,导致算法时间复杂度较高等问题。为解决这些问题,本文首先研究了与线段遍历问题相关的一些经典问题,以及问题求解过程中需要用到的基础知识与基本算法,如确定点与线段的位置关系、直线与直线的位置关系、反射点与完美反射等。在此基础上,提出了采用凸链存储技术,结合Rubber-band算法,给出不相交线段序列最优遍历问题的求解思路,即利用凸链存储局部最优路径,并利用二分检索树实现路径点的更新,防止振荡现象的产生,减少迭代次数,提升算法效率的整体解决方案。为此,本文详细论述了凸链存储技术以及基于二分检索树的路径点更新技术,以及通过组合优化技术优化算法的迭代过程等,最终提出了一个时间复杂度为O(n*logn*logn)的平面内不相交线段序列最短遍历问题的求解算法,解决了Rubber-band算法的振荡现象以及算法时间性能差方面的问题。最后,针对本文所提出的算法,构造相应的测试数据,设计相应的数据结构并编程加以实现,分析算法的可视化运行结果,验证了算法的正确性和有效性。

关键词：计算几何欧几里德最短路径 Rubber-band算法凸链二分检索树

来源：评论

学校读者我要写书评

暂无评论

三维空间内多面体Minkowski和求和算法的研究

三维空间内多面体Minkowski和求和算法的研究

引用

作者：谢蕾燕山大学

学位级别：硕士

计算几何是计算机理论科学的一个较新的极有生命力的子领域,而Minkowski和算法作为计算几何研究领域中的一个分支,在理论和应用上都有着重要的意义,其研究成果已在图形学、机器人技术、地理数据库等领域中得到了广泛的应用。首先,本文... 详细信息

计算几何是计算机理论科学的一个较新的极有生命力的子领域,而Minkowski和算法作为计算几何研究领域中的一个分支,在理论和应用上都有着重要的意义,其研究成果已在图形学、机器人技术、地理数据库等领域中得到了广泛的应用。首先,本文在对国内外研究现状进行综合分析的基础上,进一步研究了计算两个凸多面体Minkowski和求和算法。为进一步提高求和算法的执行效率,本文优化了基于正四面体中心投影的计算凸多面体精确Minkowski和求和算法,提出基于正四面体高斯映射的凸多面体精确Minkowski和求和算法。同时对算法的时间复杂度进行了对比分析。其次,为有效的计算凹多面体Minkowski和,在研究了许多凸剖分算法后,提出按照三维几何造型的不同,对凹多面体进行四面体分解或者面分解的分而治之的剖分策略。同时对剖分算法的时间复杂度进行了分析。然后,为提高合并算法的计算效率,本文利用改进的Enhanced Marching Cubes算法,提出了优化的合并子凸多面体的Minkowski和多面体边界面的算法。同时,本文研究了计算任意简单多面体Minkowski和的求和算法步骤,为进一步提高算法的效率和精确度,本文给出了新的计算任意简单多面体Minkowski和的求和算法步骤。最后,通过实验验证了计算任意简单多面体Minkowski和的算法的可行性和有效性,并将结果与传统算法进行了对比分析。

关键词：计算几何高斯映射凹多面体 Enhanced Marching Cubes Minkowski和

来源：评论

学校读者我要写书评

暂无评论

可解析曲线的可见性相关问题研究

可解析曲线的可见性相关问题研究

引用

作者：王纬臻山东大学

学位级别：硕士

本文讨论了二维平面下曲线的可见性问题。我们研究的两个主要内容是：曲线的弱可见多边形算法,沿曲线移动的点的实时可见多边形算法。曲线与直线不同,可能具有复杂的形状与性质。本文研究的对象是可解析曲线,即像多项式函数曲线、三角... 详细信息

本文讨论了二维平面下曲线的可见性问题。我们研究的两个主要内容是：曲线的弱可见多边形算法,沿曲线移动的点的实时可见多边形算法。曲线与直线不同,可能具有复杂的形状与性质。本文研究的对象是可解析曲线,即像多项式函数曲线、三角函数曲线等各种具有参数方程的曲线。由于利用了可解析曲线的性质及相关数值算法,我们的算法具有高精确度与高灵敏性。我们将一部分可解析曲线定义为CCTH,并提出了internal CCTH与non-internal CCTH的概念。我们给出了CCTH的弱可见多边形算法,此算法对于internal CCTH能够达到O(n)的时间与空间复杂度,与线段的弱可见多边形算法相同。对于non-internal CCTH,我们给出了将其分割为多段internal CCTH的算法,然后每段均可调用internal CCTH的弱可见多边形算法。在非极端情况下分段数一般远小于O(n)；在极端情况下,算法的时间复杂度为O(n2),并且我们证明了这个时间复杂度已无法再优化。对于曲线轨迹上移动点的可见多边形问题,我们给出了轨迹预处理和场景预处理两种方法。我们借鉴了文献[10]给出了CCTH轨迹预处理算法,其复杂度与直线轨迹预处理算法相同。而后我们以三角剖分为例,给出了CCTH场景预处理算法,算法的预处理过程耗费O(n2)的时间与空间,能够在轨迹穿过的每个分块上依次计算关键点,假设曲线轨迹在单个分块上的关键点规模数为O(m),则在每个分块上定位关键点所用的时空复杂度均为O(m),生成持久化数据结构的时间复杂度O(mlogm)。在非极端情况下O(m)<计算关键点的时空复杂度均为线性,生成持久化数据结构的时间复杂度为O(nlogn),空间复杂度为O(n)。non-internal CCTH轨迹预处理算法计算关键点的时间复杂度在极端情况下为O(n2),但一般远小于这个规模。 5)我们以三角剖分为例,给出了CCTH场景预处理算法,算法的预处理过程耗费O(n2)的时间与空间,能够在轨迹穿过的每个分块上依次计算关键点,假设曲线轨迹在单个分块上的关键点规模数为O(m),则在每个分块上定位关键点所用的时空复杂度均为O(m),生成持久化数据结构的时间复杂度O(mlogm)。在非极端情况下O(m)<计算几何与虚拟现实问题领域,在路径规划,虚拟博物馆之类实际应用中有一定价值。

关键词：计算几何可见性可解析曲线持久化数据结构

来源：评论

学校读者我要写书评

暂无评论

计算三维空间凸多面体的精确Minkowski和的算法研究

计算三维空间凸多面体的精确Minkowski和的算法研究

引用

作者：高艳丽燕山大学

学位级别：硕士

计算几何是理论计算机科学领域中一个新的极有生命力的子领域,而Minkowski和算法作为计算几何研究领域中的一个分支,在理论和应用上都有着重要的意义,其研究成果已在机器人学、计算机图形学、CAD等许多领域中发挥了重要的作用。如何为... 详细信息

计算几何是理论计算机科学领域中一个新的极有生命力的子领域,而Minkowski和算法作为计算几何研究领域中的一个分支,在理论和应用上都有着重要的意义,其研究成果已在机器人学、计算机图形学、CAD等许多领域中发挥了重要的作用。如何为各种应用提供有效的基础算法以及理论依据,一直是国内外学者研究的方向。叠置算法是计算两个凸多面体Minkowski和的重要步骤,本文首先为克服现有叠置算法的缺陷,从一个全新的角度对平面划分的叠置算法进行了研究,提出了三角形内简单平面凸划分的叠置算法。整个算法分为计算交点、拓扑重组和创建双向链接边表记录三步,文章同时对算法的正确性和复杂度进行了分析。其次,以减少计算平面划分叠置的次数,提高算法的执行效率为目标,提出了正四面体中心投影的概念。通过计算凸多面体的正四面体中心投影,按照给定坐标系下的坐标转换关系,把三维空间的问题转换到二维空间进行解决。然后,提出了基于正四面体中心投影的凸多面体的精确Minkowski和求和算法。采用三角形内简单平面凸划分的叠置算法求四对平面划分的叠置,并根据求和的需要及特征完成了属性分配过程,由此得到Minkowski和多面体的正四面体中心投影,求它的逆映射得到Minkowski和多面体。文章同时对算法的时间复杂度进行了分析。最后,对上述的研究内容进行了实验验证并给出实验结果。

关键词：计算几何平面划分叠置算法正四面体中心投影双向链接边表 Minkowski和

来源：评论

学校读者我要写书评

暂无评论

基于flip的Delaunay三角剖分算法研究

基于flip的Delaunay三角剖分算法研究

引用

作者：徐丽丽大连海事大学

学位级别：硕士

三角剖分是计算几何、CAD、曲面重构以及计算机图形学等领域的重要研究内容。基于三角剖分的实际应用极为广泛,本文选择三角剖分的剖分算法进行研究,其目的是要设计出一个简单高效的三角剖分算法,以便在计算机图形学等领域加以应用。因... 详细信息

三角剖分是计算几何、CAD、曲面重构以及计算机图形学等领域的重要研究内容。基于三角剖分的实际应用极为广泛,本文选择三角剖分的剖分算法进行研究,其目的是要设计出一个简单高效的三角剖分算法,以便在计算机图形学等领域加以应用。因此本次研究,不仅具有一定的理论意义,而且还有很大的实际应用价值。本文针对平面点集的三角剖分进行研究。通过对经典算法的研究可以发现,目前常见的平面点集的三角剖分算法,普遍存在着执行效率低,候选节点可能出现“位置违约”等缺陷,由于这些缺陷的存在,常常可能导致所得到的三角剖分结果不是最优的。为了解决这一问题,本文提出了一种新的Delaunay三角剖分算法,其基本思想是：基于Graham扫描法并对之进行改进,在求出平面点集的凸包的同时,生成初期的Delaunay三角剖分,在此基础上,采用Delaunay flip方法对之进行优化,使得剖分后得到的三角形的最小角最大化,从而得到性能最优的Delaunay三角剖分。该算法很好地避免了病态三角形的出现,提高了算法的健壮性及执行效率,且算法简洁通用。为了验证算法的有效性,本文对所设计的算法采用C语言进行了程序实现,并与经典算法的实现结果进行了分析比较。实现结果表明,本文所提出的算法是简单有效的且时间性能较好,能避免病态三角形的出现,得到性能最优的Delaunay三角剖分。

关键词：计算几何 Delaunay三角剖分算法曲面重构

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：