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

作者：杨承磊山东大学

学位级别：博士

该论文对多边形的内部和外部Voronoi图的相关性质进行了较为深入的研究,并以此为基础研究解决在图形图像、虚拟现实等方面的研究工作中遇到的可见性计算、距离计算以及骨架计算等问题.该论文的贡献主要有:1、分析了***给出的关于多边形... 详细信息

该论文对多边形的内部和外部Voronoi图的相关性质进行了较为深入的研究,并以此为基础研究解决在图形图像、虚拟现实等方面的研究工作中遇到的可见性计算、距离计算以及骨架计算等问题.该论文的贡献主要有:1、分析了***给出的关于多边形内部Voronoi图顶点和边数的上界所存在的局限性.2、提出了一种基于Voronoi图的计算多边形可见性的算法.我们用多边形的Voronoi图建立多边形的骨架,利用Voronoi图的邻近属性和最近特性等性质,沿着骨架在局部范围内确定可能产生遮挡的对象,从而确定多边形内任意一点的可见边.3、给出了基于Voronoi图快速计算两个分离凸多边形距离的算法.算法利用两个分离凸多边形P和Q的外部Voronoi图的性质及其相互间的位置关系,采用二分法逐渐缩小搜索范围来快速查找最短距离对象对.4、提出了基于多边形划分的带状图像及其骨架表示模型,并分别以一般的多边形划分和多边形的约束Delaunay三角化为基础,设计并实现了两种骨架化算法.基于该论文的工作,可以把Voronoi图理论扩展到场景的表示、光线跟踪、阴影生成等方面,为系统化地解决三维虚拟场景快速绘制问题提供了一定的理论基础.

关键词：计算几何多边形 Voronoi图可见性计算距离计算骨架 Delaunay三角化

来源：评论

学校读者我要写书评

暂无评论

时间序列挖掘中索引与查询技术的研究

时间序列挖掘中索引与查询技术的研究

引用

作者：曲吉林天津大学

学位级别：博士

索引和查询是数据挖掘中各项任务的基础和关键问题。本文对时间序列挖掘中的索引和查询技术进行了研究,比较系统地研究了时间序列的查询方式、表示与索引和相似性度量等问题;提出了计算几何应用到时间序列挖掘的方法,实现了时间序列全... 详细信息

索引和查询是数据挖掘中各项任务的基础和关键问题。本文对时间序列挖掘中的索引和查询技术进行了研究,比较系统地研究了时间序列的查询方式、表示与索引和相似性度量等问题;提出了计算几何应用到时间序列挖掘的方法,实现了时间序列全序列匹配查询、模式查询、反向查询和异常检测,查询效率和准确性都有了比较大的提高。主要研究成果如下: 1.时间序列查询方式利用计算几何中邻近问题的原理和方法,根据时间序列的构成要素,对时间序列的查询方式进行了系统地分类。按查询对象将时间序列查询分为点查询、模式查询和序列查询;按查询方式将时间序列查询分为范围查询、邻近查询和点对查询,拓宽了时间序列查询的方式,为序列挖掘提供了更加有力的工具。 2.时间序列表示与索引在基于重要点分段的基础上,主要研究了时间序列的KL表示方法。利用Voronoi图对数据进行组织和管理,为时间序列查询提供了一种新的索引方法。同时,针对时间序列原始数据的反向查询,提出了一种新的时间序列索引方法—IC-索引。 3.时间序列相似性查询系统地研究了时间序列各种查询方式的实现算法。提出了KL相似性度量,实现了全序列匹配查询;利用计算几何方法,实现了线性模式的邻近查询、最近模式对查询和最远模式对查询,算法在时间上都是最优的;提出了一种新的时间序列反向查询方法,查询效率和准确性都有比较大的提高。 4.时间序列异常检测利用Voronoi图的基本原理,提出了一种基于密度的异常检测方法VOD,并应用到时间序列的线性模式异常检测,将现有算法的复杂性从O(n2)降低到O(nlogn),检测效率和性能都有了很大的提高。

关键词：数据挖掘时间序列索引查询异常检测计算几何 Voronoi图

来源：评论

学校读者我要写书评

暂无评论

平面点集Delaunay三角剖分的分治算法

引用

计算机工程与设计 2012年第7期33卷 2652-2658页

作者：谢增广华北计算技术研究所北京100083

为发展图形网格化技术,研究了平面点集的三角剖分算法。根据经典算法中在实际应用中遇到的共性问题,提炼了3个工具算法;为了更好地表示平面区域划分的拓扑信息,引入了双链接边表(DCEL)的数据结构。在此基础上,设计并实现了平面集Delauna... 详细信息

为发展图形网格化技术,研究了平面点集的三角剖分算法。根据经典算法中在实际应用中遇到的共性问题,提炼了3个工具算法;为了更好地表示平面区域划分的拓扑信息,引入了双链接边表(DCEL)的数据结构。在此基础上,设计并实现了平面集Delaunay三角剖分分治算法,并对特殊退化情况进行了处理,通过计算表明了该算法时间复杂度为O(N*logN)。实验数据结果验证了该算法的正确性、健壮性。

关键词：平面点集Delaunay三角剖分双链接边表分治策略计算几何

来源：评论

学校读者我要写书评

暂无评论

一种基于局部平均法向变形的网格参数化方法

引用

吉林大学学报（理学版） 2021年第4期59卷 867-876页

作者：焦冲苏科华吴博文任术波辛宁武汉大学计算机学院武汉430072 中国空间技术研究院通信与导航卫星总体部北京100094

针对有边界无边界的网格参数化问题,提出一种局部平均法向变形的网格参数化方法,以平均曲率流的方式为参考,将顶点推向其邻居的平均位置,使网格变形至平面或球面.首先,计算每个三角形邻居面的平均法向,并以该法向为目标,计算每个面法向... 详细信息

针对有边界无边界的网格参数化问题,提出一种局部平均法向变形的网格参数化方法,以平均曲率流的方式为参考,将顶点推向其邻居的平均位置,使网格变形至平面或球面.首先,计算每个三角形邻居面的平均法向,并以该法向为目标,计算每个面法向变化的旋转矩阵;其次,基于Poisson方程将整个网格重新“缝合”,通过优化拉伸能量,计算顶点的新坐标.交替迭代上述两个步骤,将网格变形至常平均曲率曲面.该算法与一般的基于能量优化的方法不同,每次迭代只需求解稀疏线性方程,因此可以快速处理大型数据集.通过在形变过程中加入惩罚函数动态地调整全局平均法向量的权重,避免了变形过程中三角形退化或翻转的问题.实验结果表明,与其他参数化方法相比,该方法具有实用可靠、计算效率高等优点,并能在同一框架下计算低扭曲的平面参数化和球面参数化.

关键词：网格参数化计算几何约束变形

来源：评论

学校读者我要写书评

暂无评论

平面线段集三角剖分的算法

引用

计算机工程与科学 2003年第1期25卷 20-22页

作者：周培德北京理工大学计算机科学与工程系北京100081

本文提出了计算平面线段集三角剖分的两种算法。第一个算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分。当扫描线达到最左边的事件点时,处理该事件点,就完... 详细信息

本文提出了计算平面线段集三角剖分的两种算法。第一个算法是利用平面扫描的思想,当扫描线达到事件点时,处理事件点,即将事件点与已被扫描的某些点连接,这样便将已扫描的区域三角剖分。当扫描线达到最左边的事件点时,处理该事件点,就完成了平面线段集的三角剖分。第二个算法基于逐层计算凸壳,并将凸壳改变为多边形,这样便形成嵌套的多边形层,这些多边形覆盖线段集凸壳内的区域,然后三角剖分每个多边形,即完成平面线段集的三角剖分。两个算法的时间复杂性分别为O(nlogn)、O(mnlogn),其中n为线段集中线段的数目,m为凸壳的层数。

关键词：平面线段集三角剖分算法凸壳时间复杂性计算几何

来源：评论

学校读者我要写书评

暂无评论

从边界未知的危险区域中快速撤离的算法研究

从边界未知的危险区域中快速撤离的算法研究

引用

作者：张浩大连海事大学

学位级别：硕士

从边界未知的危险区域中快速撤离问题的研究,是从很多实际应用问题中抽象出来的一个理论课题,在一定的约定条件下,研究受灾人员如何从边界未知的危险区域中快速撤离的撤离策略,可为解决一些实际应用问题提供技术支撑。因此,本课题的研究... 详细信息

从边界未知的危险区域中快速撤离问题的研究,是从很多实际应用问题中抽象出来的一个理论课题,在一定的约定条件下,研究受灾人员如何从边界未知的危险区域中快速撤离的撤离策略,可为解决一些实际应用问题提供技术支撑。因此,本课题的研究,不仅具有重要的理论意义,而且还具有较高的实用价值。本文针对从边界未知的危险区域中快速撤离的策略进行研究,包括单源点问题和多源点问题。为此,首先论述了问题求解过程中所涉及的计算几何学的相关基础知识,如判断某点是否在线段上、构造平面点集的凸包等,并对竞争比、凸包,以及构造凸包的格雷厄姆方法等,作了较为详细的论述。在此基础上,论述了单源点问题及其相关撤离策略,并对等角策略的基本原理、执行过程以及竞争比等,做了较为详细的分析,提出了改进的单源点问题撤离策略。对比分析了多源点问题与单源点问题的问题特征,基于单源点问题的等角撤离策略,结合多源点问题的问题特征,进一步提出了多源点问题的等角撤离策略,并对撤离策略的竞争比做了较为详尽的理论分析,给出了竞争比不超过4(?)2的研究结果。最后,针对所设计的算法,构造测试数据并运行所实现的程序,验证了算法的可行性与有效性。实验结果表明,本文提出的针对单源点问题和多源点问题的撤离策略,能够有效地解决单源点问题和多源点问题,关于竞争比的实验结果与理论分析结果比较一致,且可保障所有受灾人员安全地撤离出危险区域。因此,本文所提出的解决单源点问题和多源点问题的算法是切实可行、有效的。

关键词：计算几何 Online问题撤离策略竞争比

来源：评论

学校读者我要写书评

暂无评论

基于非耦合区域分解的海量Delaunay三角网并行构建算法研究

基于非耦合区域分解的海量Delaunay三角网并行构建算法研究

引用

作者：张英南京师范大学

学位级别：硕士

Delaunay三角网所具备的优良特性，使其在地形建模、地图综合、模式识别、有限元计算、GIS等诸多领域中有着极为重要的作用。关于Delaunay三角网的构建方法也一直是计算几何中的重点内容，特别是随着LIDAR、SAR等新技术的发展，海量的... 详细信息

Delaunay三角网所具备的优良特性，使其在地形建模、地图综合、模式识别、有限元计算、GIS等诸多领域中有着极为重要的作用。关于Delaunay三角网的构建方法也一直是计算几何中的重点内容，特别是随着LIDAR、SAR等新技术的发展，海量的点集数据可以快捷方便地获得，如何利用这些海量的点集数据快速高效地生成Delaunay三角网成为当前研究的热点。　　本文以拓扑数学、计算几何为理论基础，针对Delaunay三角网高效、准确和稳定的构网需求，在充分分析国内外学者所采用的各种D-TIN构建方法的基础上，采用对比分析、系统开发、案例验证等方法，研究基于非耦合区域分解的D-TIN并行算法和面向海量点集数据的并行D-TIN生成方法，并基于本文提出的Delaunay三角网的生成算法，设计了海量点集数据构建D-TIN的原型系统，对典型区域的海量点集数据生成D-TIN进行测试和验证。所取得的主要研究成果如下:　　(1)对比分析了分治法、逐点插入法和三角网生长法等常用Delaunay三角网的构建算法后，选取时空复杂度较为平衡且易于实现的逐点插入法作为基础构网算法，并根据逐点插入法的实现特点，在半边结构的基础上，构建一种特殊的双向循环链表数据结构，实现了构网过程中的快速拓扑重构，从而进一步提高了逐点插入算法的执行效率。　　(2)对比耦合式区域分解方法和非耦合式区域分解方法实现D-TIN并行构建的优缺点，利用Delaunay三角网的空圆特性，提出基于稳定三角形条带进行非耦合区域分解的并行Delaunay三角网构建算法，既避免了处理器之间的频繁通信，又不需要复杂的缝合操作，具有较优的并行程度和运行效率。　　(3)研究针对海量数据进行构网的流计算模式，结合基于稳定三角形条带分割的并行Delaunay三角网构建算法，实现面向海量点集进行Delaunay三角网并行构建的算法，解决采用传统构网算法时效率较低和内存不足的两个难题。　　本文的研究内容立足于三维遥测技术的高速发展和主流的多核架构的计算机体系结构，为海量D-TIN快速构建提供新的方案，从而更好地支持地理信息系统、空间数据基础设施等的发展和建设。

关键词：计算几何德洛内三角网并行构建算法非耦合区域分解法

来源：评论

学校读者我要写书评

暂无评论

基于巡视员路径问题的online搜索算法研究

基于巡视员路径问题的online搜索算法研究

引用

作者：姚鹏飞大连海事大学

学位级别：硕士

未知多边形遍历问题不仅涉及算法设计与分析、计算几何、路径规划等基础理论问题,也是解决游戏产业、未知区域搜救等领域实际问题的基础。因此,本课题的研究,兼具理论意义和实用价值。本文针对未知多边形遍历问题以及网格撤离问题进行... 详细信息

未知多边形遍历问题不仅涉及算法设计与分析、计算几何、路径规划等基础理论问题,也是解决游戏产业、未知区域搜救等领域实际问题的基础。因此,本课题的研究,兼具理论意义和实用价值。本文针对未知多边形遍历问题以及网格撤离问题进行了研究,首先研究了与求解问题相关的基础知识,如点与多边形位置关系的判定、求解给定两点界定的圆弧、竞争比的分析方法等,然后分析了与课题相关的已有算法,如直线搜索问题的双倍策略、√2倍巡逻员路径近似算法、竞争比为26.5的未知多边形遍历算法,以及竞争比为21的网格单组撤离策略等,并指出部分算法的不足之处。在此基础上,详细研究了竞争比为6.7的未知多边形遍历算法并对其进行了编程实现,通过比较实验结果和理论结果,验证了算法的有效性。同时,提出了解决单源点两组撤离问题与多源点撤离问题的撤离算法,证明了单源点两组撤离策略以及多源点撤离策略不仅适用于危险区域是凸多边形的情形,而且也适用于受灾区域是非凸多边形的情形,并分别计算出了每个算法的竞争比。

关键词：计算几何遍历多边形 online搜索算法网格撤离问题竞争比

来源：评论

学校读者我要写书评

暂无评论

空间分析算法与实现

空间分析算法与实现

引用

作者：万丰武汉大学

学位级别：硕士

该文先简要介绍GIS相关知识、空间数据模型与数据结构,然后重点讨论空间分析中的空间拓朴关系分析和叠加分析.系统阐述了点、线、面三类几何物体之间的拓朴关系,提出了分解复杂线段为简单线段,通过判断简单线段与线、简单线段与多边形... 详细信息

该文先简要介绍GIS相关知识、空间数据模型与数据结构,然后重点讨论空间分析中的空间拓朴关系分析和叠加分析.系统阐述了点、线、面三类几何物体之间的拓朴关系,提出了分解复杂线段为简单线段,通过判断简单线段与线、简单线段与多边形的关系,进而确定线与线,线与多边形,多边形与多边形拓朴关系的新思路.

关键词：计算几何空间分析空间关系多边形多边形交并差

来源：评论

学校读者我要写书评

暂无评论

平面散乱点集凸包并行算法

引用

浙江大学学报（自然科学版） 1999年第4期33卷 432-435,440页

作者：张三元马利庄浙江大学计算机科学与工程学系浙江杭州310027 浙江大学CAD&CG国家重点实验室浙江杭州310027

提出一种构造平面散乱点集凸包的线性算法，它所需的乘法次数不超过Ｏ（ｌｏｇ３ｎ）。

关键词：点集凸包并行算法平面点集计算几何

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：