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

作者：孟文龙山东大学

学位级别：博士

在几何学中,曲面上连接两点的最短距离称为测地距离,连接两点的路径称为测地线。测地线是弯曲空间中两点的局部最短路径,被认为是直线在弯曲空间的推广。测地线是曲面上一个非常重要的内蕴量,是计算几何中的经典问题。测地线问题的研究... 详细信息

在几何学中,曲面上连接两点的最短距离称为测地距离,连接两点的路径称为测地线。测地线是弯曲空间中两点的局部最短路径,被认为是直线在弯曲空间的推广。测地线是曲面上一个非常重要的内蕴量,是计算几何中的经典问题。测地线问题的研究在科学和工程领域有着深远意义,在计算机图形学、数字医疗、智能设备的运动规划、工业制造以及深度学习等许多方面有着广泛的应用。随着大数据时代的到来,人们迫切需要数字几何处理算法能够以更高的运行效能、空间效率、鲁棒性应对海量的三维数据。尽管测地线问题从最初引入开始就获得了人们大量的关注并对其进行了不断完善、提升,但是如何在分辨率不断提高的大尺度模型上,快速、准确地解决测地线问题仍然是数字几何处理领域有待解决的关键问题之一。在大数据时代背景下使用精确算法获得测地线的时间代价相对过大,在大多数应用场景下人们往往从实用角度出发,在计算精度满足需求的前提下尽可能高效的获得一条近似的测地线结果。因此当前测地线问题的研究热点从如何精确计算测地线变为如何找到一种能在计算精度,时间以及内存消耗上取得一定平衡的更加灵活、鲁棒的近似测地线算法。本学位论文针对上述热点的曲面近似测地线问题,研究如何在不同表达形式的曲面(连续光滑曲面和离散网格曲面)上高效计算精度可控的、鲁棒的近似测地距离(场)。结合提出的测地线计算方法,进一步重点研究了如何高效构造网格曲面上近似Voronoi图这一与测地度量紧密相关的应用。本文主要创新点和贡献如下:(1)基于改进的图方法快速计算离散网格曲面上的测地距离场基于斯坦纳点插入的图方法作为网格曲面上计算测地距离场的经典方法,由于其执行简单,误差容易控制等特点而受到人们的广泛关注。但是该类方法存在随着插入斯坦纳点数目增加,计算复杂度剧增的固有问题。在本学位论文中,借鉴精确测地线算法中的过滤规则,创新性的提出了图上冗余事件的过滤策略并应用到传统斯坦纳点插入的图方法中去,有效的解决了传统图方法中存在的时间效率问题。同时通过有效整合算法执行过程中获得的“轨道”信息,为测地路径追踪,等值线的计算等提供了更加精确的结果。该框架可以扩展到更加广泛的测地线变种问题,如带密度或各向异性度量的测地线计算等等。(2)三角网格曲面上近似测地Voronoi图的高效构建方法过往研究中,人们一般使用精确测地距离去构造网格曲面上的Voronoi图结构。局限于目前精确测地线算法计算效率相对较低,从而间接导致Voronoi图生成效率不高。为了解决这一问题,在本学位论文中提出了不同以往的测地Voronoi图构造方法。和大多数方法使用精确算法获取测地距离信息不同,本文使用上一工作中改进版本的图方法替代精确算法,高效地获取测地距离信息。这使得测地Voronoi图计算会更节省时间,占用更少的内存。通过控制网格上三角形边插入斯坦纳点的数目可以取得接近精确测地Voronoi图的结果。另外利用带权斯坦纳点构造的阿波罗图划分三角网格,可以提取线段和双曲线用于编码测地Voronoi图复杂的等分线结构。(3)基于优化变分框架计算连续扫掠曲面上的近似测地路径针对连续光滑扫掠曲面提出了一种基于优化策略解决测地线问题的新方法。该方法发扬了曲线渐进缩短的精神,当用户在扫掠曲面上指定了两个目标点后,以两点之间的路径长度的平方和为目标函数,在参数域而非欧氏空间中建立了目标函数。通过将目标函数和梯度输入到L-BFGS求解器中,经过迭代优化最终高效的计算出一条满足精度要求的测地路径。和其他相关方法比较,算法在误差控制,时间效率等方面具有优势。另外本文把该框架扩展应用到测地螺旋线,动画模拟中的路径演化等问题中,取得了不错的效果。

关键词：计算几何计算机图形学近似测地线路径追踪测地Voronoi图

来源：评论

学校读者我要写书评

暂无评论

基于人工蜂群算法的p-center问题求解算法

引用

计算机工程与科学 2020年第6期42卷 1127-1133页

作者：包敏泽胡秀婷谢玉莹蒋波大连海事大学信息科学技术学院辽宁大连116026

平面p-center问题是经典的NP难题,所以寻找高效的近似求解算法是解决实际应用问题时的基本需求。在人工蜂群算法的基础上,通过引入遗传算法的交叉和变异算子,改进局部解的搜索策略与搜索能力,即根据给定概率对当前解做交叉或变异运算,... 详细信息

平面p-center问题是经典的NP难题,所以寻找高效的近似求解算法是解决实际应用问题时的基本需求。在人工蜂群算法的基础上,通过引入遗传算法的交叉和变异算子,改进局部解的搜索策略与搜索能力,即根据给定概率对当前解做交叉或变异运算,以获得更好的局部解,进而提出BeeGenP启发式求解算法,用于求解平面离散型p-center问题。通过构造测试数据,对所设计的算法进行了有效性验证,实验结果表明,BeeGenP算法与现有的M-ABC算法相比,算法的局部解搜索能力得到了提升,增加了搜索空间的多样性,在相同迭代次数约束下所得到的解的质量更高,而趋近收敛于最优解时的迭代次数则有较大幅度的降低。

关键词：计算几何启发式算法人工蜂群算法 p-center问题 M-ABC算法

来源：评论

学校读者我要写书评

暂无评论

基于蚁群算法的超大规模集成电路布线研究

基于蚁群算法的超大规模集成电路布线研究

引用

作者：黄训诚西安电子科技大学

学位级别：博士

当前集成电路产业向深亚微米工艺不断推进，正力图突破100nm大关。现有EDA工具难以应付复杂度呈指数增长的诸多VLSI设计难题，也缺乏对深亚微米工艺下一系列新问题的考虑。另一方面，在计算智能领域，各种优化技术日新月异，为解决非NP... 详细信息

当前集成电路产业向深亚微米工艺不断推进，正力图突破100nm大关。现有EDA工具难以应付复杂度呈指数增长的诸多VLSI设计难题，也缺乏对深亚微米工艺下一系列新问题的考虑。另一方面，在计算智能领域，各种优化技术日新月异，为解决非NP和NP复杂度的大规模、超大规模问题展示了广阔的前景。本文正是在这样的背景下，研究计算智能方法在深亚微米工艺下性能驱动VLSI生产工序中关键环节—物理设计中的应用。随着VLSI的工艺向深亚微米的推进，物理设计中的布线问题(无论是非NP问题、NP完全问题和NP困难问题)，由于问题规模的急剧增大，都迫切需要更有效的优化算法解决方案。蚁群算法作为一种较新的进化类方法，目前已经在若干领域取得了成功的应用，诸如：旅行商问题、二次分配问题、通讯网络中的路由问题以及负载平衡问题、大规模集成电路设计等。本文深入讨论了蚁群算法应用于解决TSP问题，并对其进行了基本功能验证；对开关盒布线，本文也进行了初步尝试，针对较少的线网进行了布线仿真；就物理设计中BBL模式下典型的两端绕障碍布线问题，首先提出了解决不同条件下实际问题的两种理论模型，模型分别基于图论和计算几何学方法，减少了问题的时空复杂度。然后，介绍了一种基于生物仿生特性的蚁群算法，通过选择适当的模型表述，该算法可采用蚁群任务调度策略，模仿蚁群的协同学习机制，来解决两端绕障碍的布局布线问题，并能给出较优的解。本文提出了一种基于蚁群算法的集成电路无网格布线算法。对于给定的布线平面，该算法首先由障碍图形和各个线网的端点生成一个包含最短路径的访问点阵，建立初始信息素矩阵，然后利用蚁群算法所特有的路径寻优功能来找到当前布线路径上的最短路径。同时本文在路径搜索过程中引入了引力的概念，使得蚁群在引力的作用下以较快的速度找到目标端点。粒子群优化算法作为一种较新的进化类方法，目前已经在若干领域取得了成功的应用，本文提出了一种基于粒子群优化算法的集成电路无网格布线算法。对于给定的布线平面，该算法首先由障碍图形和各个线网的端点生成一个包含最短路径的访问点阵，建立初始粒子位置矩阵，然后利用粒子群优化算法的路径寻优功能来找到当前布线路径上的最短路径。

关键词： VLSI物理设计深亚微米工艺计算智能绕障碍布线图论模型蚁群系统粒子群算法计算几何无网格布线最短路径 Prufer数

来源：评论

学校读者我要写书评

暂无评论

110警车配置及巡逻方案

引用

数学的实践与认识 2010年第15期40卷 184-193页

作者：林阳斌陈碧黎苏圳泷厦门大学信息科学与技术学院

针对110警车调度问题，引入了图论中的最短路算法以及计算几何的相关理论，建立了车辆调配模型、巡逻路线模型以及基于模糊数学的评价指标模型．另外，用C＋＋编写了一个可视化的软件，不仅实现了手动描点，自动求出覆盖线段集合的功能... 详细信息

针对110警车调度问题，引入了图论中的最短路算法以及计算几何的相关理论，建立了车辆调配模型、巡逻路线模型以及基于模糊数学的评价指标模型．另外，用C＋＋编写了一个可视化的软件，不仅实现了手动描点，自动求出覆盖线段集合的功能，同时利用计算机模拟警车的巡逻路线，最后通过计算机检验得到结果，其合理性和实用性都令人满意．针对问题一，通过人机结合，配置17辆警车就能实现D1的目标，很好地兼顾了警车巡逻的运行成本，减少公安部门车辆和人员等的投入．针对问题二，采用模糊数学相关理论使评价指标实现了从定性到定量的转变．针对问题三和六，在D1的基础上，兼顾了巡逻效果的显著性，采用最少被巡逻道路优先的贪心算法建立了动态巡逻模型，得到了合理的巡逻方案．在此方案中，我们动用了30辆警车完成了问题一的目标．另外还额外考虑了案发事件概率不均匀分布的情况，建立了改进模型．针对问题四，在完成问题三指标的基础上，为了尽可能提高巡逻车辆的隐蔽性和增强巡逻效果，采用轮盘赌算法来引入随机性．针对问题五，采用最远距离道路优先贪心策略，使模型尽可能满足条件D1，D2．针对问题七，提出了一些额外因素及其解决方案，进一步完善了模型，使模型更贴近现实．

关键词：车辆调度计算几何模糊数学贪心算法

来源：评论

学校读者我要写书评

暂无评论

加权Voronoi区域面积的计算方法

引用

河北师范大学学报（自然科学版） 2010年第5期34卷 524-528,533页

作者：周恩辉刘淑娟张有会河北师范大学数学与信息科学学院河北石家庄050016

加权Voronoi图是Voronoi图定义的扩展.加权Voronoi区域的面积是加权Voronoi图的一个重要的物理属性.给出了加权Voronoi区域面积的计算方法,即对给定的母点坐标和权重,先求出各Voronoi区域边界上相邻两顶点间的Voronoi边的属性数据,并将... 详细信息

加权Voronoi图是Voronoi图定义的扩展.加权Voronoi区域的面积是加权Voronoi图的一个重要的物理属性.给出了加权Voronoi区域面积的计算方法,即对给定的母点坐标和权重,先求出各Voronoi区域边界上相邻两顶点间的Voronoi边的属性数据,并将每个闭合边界上的属性数据存放在一个循环链表中,最后根据各个循环链表中的数据,计算出各加权Voronoi区域的面积.

关键词：计算几何 Voronoi图权重面积链表

来源：评论

学校读者我要写书评

暂无评论

一种利用图形内角的多边形布尔运算新算法

引用

工程图学学报 2011年第2期32卷 10-19页

作者：朱二喜何援军江苏信息职业技术学院计算机工程系江苏无锡214102 上海交通大学计算机科学与工程系上海200240

现有的平面多边形布尔运算在一般情况下可以快速地获得正确结果,但如遇到奇异情况,则会产生错误。因此,采用图形内角概念分析奇异情况,并在原有交点遍历算法框架基础上给出一种全局化的奇异处理算法。与其他的多边形布尔运算算法相比,... 详细信息

现有的平面多边形布尔运算在一般情况下可以快速地获得正确结果,但如遇到奇异情况,则会产生错误。因此,采用图形内角概念分析奇异情况,并在原有交点遍历算法框架基础上给出一种全局化的奇异处理算法。与其他的多边形布尔运算算法相比,该算法对奇异的分析更为简洁有效,且具有高效性和鲁棒性。

关键词：计算几何多边形布尔运算图形内角布尔运算奇异情况

来源：评论

学校读者我要写书评

暂无评论

室内座椅线框图识别

引用

计算机工程与应用 2016年第23期52卷 196-202页

作者：许孝盛靳萍郑稳武汉大学计算机学院武汉430072 武汉大学城市设计学院武汉430072

针对座椅识别归类问题提出一种由单幅线框图生成三维座椅模型的方法。首先对大量座椅的形态和结构进行学习和归纳,根据座椅在固定观察视点下的线框图,提取出能抽象表达座椅的基本图元集合,如线段、四边形和椭圆形等;然后依据集合中元素... 详细信息

针对座椅识别归类问题提出一种由单幅线框图生成三维座椅模型的方法。首先对大量座椅的形态和结构进行学习和归纳,根据座椅在固定观察视点下的线框图,提取出能抽象表达座椅的基本图元集合,如线段、四边形和椭圆形等;然后依据集合中元素的个数和相对位置关系确定椅子的造型特征;最后通过Web GL和PHP技术实现网页上的室内座椅线框图识别系统。实验结果表明,系统可以识别出1 164类座椅线框图,识别正确率为88.72%,具有一定容错率,并能在识别的基础上从数据库中选取对应的三维模型在网页中进行绘制和渲染。

关键词：室内座椅线框模型网页建模计算机辅助设计计算几何

来源：评论

学校读者我要写书评

暂无评论

空间数据中几何拓扑关系的一种快速检查算法

引用

硅谷 2009年第17期 54-54页

作者：吴宇豪香港理工大学地理资讯学系

随着信息技术的发展,空间数据呈几何级数增长,特别是数字地图中常见的矢量数据,如何在海量的矢量数据中快速检测他们之间的拓扑关系,就成为相关的空间分析迫切需要解决的问题之一。根据目前空间数据质量检查的需要,提出一种新的快速几... 详细信息

随着信息技术的发展,空间数据呈几何级数增长,特别是数字地图中常见的矢量数据,如何在海量的矢量数据中快速检测他们之间的拓扑关系,就成为相关的空间分析迫切需要解决的问题之一。根据目前空间数据质量检查的需要,提出一种新的快速几何拓扑关系检查算法——行扫描检测算法。该算法在现有常用的算法基础上,通过提高算法运算效率,有效地减少运算时间。通过实验,将行扫描算法与不同的常用算法进行测试比较,最后证明行扫描算法在大量的矢量数据拓扑检查中效率上的优点。

关键词：空间数据几何拓扑关系计算几何空间分析拓扑检查

来源：评论

学校读者我要写书评

暂无评论

多层薄壳虚拟装配优化算法与仿真

引用

计算机工程与应用 2006年第26期42卷 189-191页

作者：何朝明方黎勇李柏林刘瑞晓西南交通大学机械工程学院成都610031

针对多层薄壳加工变形大、装配方案和涂层厚度由经验确定的现状,提出确定性的多层薄壳回旋结构近似装配定位球心算法;提出壳与壳的虚拟装配方案优化算法,利用组件技术获得涂层体积最小化,实现多层薄壳回旋结构的虚拟装配优化仿真。

关键词：虚拟装配计算几何三维建模多层壳

来源：评论

学校读者我要写书评

暂无评论

一种改进的基于Delaunay三角网的聚类算法

引用

计算机工程与科学 2016年第3期38卷 585-589页

作者：樊广佺马丽平河北经贸大学管理科学与工程学院河北石家庄050061 河北经贸大学计算机中心河北石家庄050061

Mundur等提出了一种基于Delaunay三角网的聚类算法,并将其应用于视频帧的多维特征数据的聚类以生成视频摘要,取得了较好的效果。但是,该算法计算量太大,导致效率不高。为提高该算法的效率,以适合于对大数据集的处理,提出了一种改进的基... 详细信息

Mundur等提出了一种基于Delaunay三角网的聚类算法,并将其应用于视频帧的多维特征数据的聚类以生成视频摘要,取得了较好的效果。但是,该算法计算量太大,导致效率不高。为提高该算法的效率,以适合于对大数据集的处理,提出了一种改进的基于Delaunay三角网的聚类算法。通过在典型数据集上的实验,提出了一种新的确定全局聚类阈值的方法,使得计算量大为减少。实验结果表明,该算法无需用户提供聚类参数,也能得到良好的聚类结果,因此能够实现聚类过程自动化;并且计算速度更快,效率更高,适合于大数据集的处理。

关键词：算法聚类 Delaunay 计算几何数据挖掘

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：