计算几何

摘要： 由中国工业与应用数学学会(CSIAM)主办,几何设计与计算专委会、山东大学承办的第十四届全国几何设计与计算学术会议(GDC 2022)暨全国计算几何协作组四十周年纪念将于2022年8月20日-22日在山东青岛举行。1982年1月,我国著名数学家苏步青先生领导成立全国计算几何协作组,并在7月于青岛成功召开了第一次全国计算几何讨论会。

摘要： 针对网格多边形机器人online探索问题,在分析现有成果的基础上,结合SmartDFS算法,并通过扩大机器人视觉范围,使其范围限定在给定的单位网格内。通过区分不同类型的网格,确定遍历的优先级别以设计出不同的探索策略,提出SmartDFS-OPT算法。该算法将网格多边形online探索问题求解算法的竞争比从5/4降低为7/6,达到了理论分析结果的下界,使机器人的online遍历路径长度达到最短,因而是求解该问题的一个最优算法。该算法将有助于那些基于机器人探索未知环境的智能设备的研发与应用。

摘要： 重力场适配区选取算法是水下重力定位系统的关键技术之一,直接影响重力匹配算法的定位精度和匹配率,为提高适配区选取算法的准确性,提出一种基于分割嵌套三角剖分的重力场适配区选取算法。首先利用墨卡托投影和重力异常空间校正,将传统重力场栅格信息变换为三维高程信息;再利用分割嵌套的思想,不断从重力场最小环形域中分割出最优三角形,从而形成重力场三角网络。之后,对网络中每一个小三角形,选取了坡度、坡向、起伏度和粗糙度作为重力场局部几何特征。最后,采用k-means聚类算法,将重力场分为强适配区、弱适配区和非适配区。仿真对比试验结果表明,在提出的适配区选取算法所选择的强适配区内,重力匹配定位精度与重力场背景图格网分辨率相当,表明利用分割嵌套三角剖分来选取重力场适配区的可行性。

摘要： 为提升平面点集Delaunay三角网的构建效率,提出了一种点集自适应二分与子集并行构建Delaunay三角网的算法。首先根据点集中点的分布,构建点集二分的引导线;接着采用优先点为中心的Delaunay三角网生成算法沿着引导线构建三角形,并根据点与三角形的位置关系将点集划分为2个子集,再分别对各个子集并行二分,直至每个子集中点的数量小于分割阈值;然后并行构建子集的Delaunay三角网;最后将点集二分时生成的三角形与子网构建的三角网直接合并,得到全局的Delaunay三角网。不同点集规模与不同分割阈值的实验表明:所提算法可有效提升Delaunay三角网的构建效率;分割阈值为900时,所提算法的构网时间随点集规模趋近于线性增长;点集规模为3万时,不同分割阈值下的平均提升效率为66.11%。所提算法充分发挥了Delaunay三角网的局部性与全局性的优点,确保了构建的每一个三角形都是最终的三角形,从而有效提升了构网效率,也为构建点集的局部Delaunay三角网提供一个可行方案。

摘要： 智能机器人不同于工业流水线上固定任务的机器人,它们往往需要面对背景、目标物体形状、位置、姿态、尺寸的多种不确定性,这就要求机器人能够像人一样具有极好的手眼协调能力,能基于动态反馈临机调整自己的动作.本文采用基于RGB-D相机的三维深度信息采集手段,构建了一个用于无标定可变场景机器人手眼协调方法,它能够利用几何关系理解三维场景,实时跟踪并准确分割机械臂末端执行器和待抓取的物体,在没有3D模型的条件下计算末端执行器的姿态,通过计算夹持器的姿态以及夹持器和目标对象在相机坐标系中的相对位移向量之后,将该相对位移矢量从相机坐标系转换到夹持器坐标系,估计夹持器位姿变换矩阵,并将齐次变换矩阵输入到机械手逆运动学程序中,求解出机械臂对应的各关节扭角,从而驱动夹持器指向或移动到物体.这一方法硬件资源需求量少、计算速度快、实时性好.

摘要： 针对多机器人在线撤离未知多边形区域展开研究,在原有撤离区域模型(三角形、正方形、圆形)的基础上提出多机器人从正六边形区域在线撤离问题。设置出口在正六边形区域的边界上,2 k(k≥1)个具有无线通信能力的机器人从相同起点出发,协作搜索出口并撤离。使用机器人全部从出口撤离的时间作为算法的开销,分析算法的效率。根据机器人数量和初始位置分情况讨论,k=1时,机器人的初始位置分别位于正六边形区域的边界和内部;k>1时,机器人初始位置在正六边形区域的边界。针对上述几种情况,分别给出了高效的多机器人协作在线撤离算法,并证明在机器人起点相同的情况下,增加机器人数量对减少算法开销具有正向的意义。

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

摘要： 最近点对问题被广泛应用于工程项目之中,近年来,由于大数据计算和人工智能等领域的兴起,许多计算领域对三维最近点对问题的运用更加广泛.分治法求解最近点对是计算几何领域的经典算法.本文通过对传统的二维最近点对问题进行分析并推广到三维空间下,利用分治法的思想和鸽巢原理,设计出两种高效求解三维最近点对的方法,对比朴素做法,在时间复杂度上有显著的优化.

摘要： 最近点对问题被广泛应用于工程项目之中,近年来,由于大数据计算和人工智能等领域的兴起,许多计算领域对三维最近点对问题的运用更加广泛.分治法求解最近点对是计算几何领域的经典算法.本文通过对传统的二维最近点对问题进行分析并推广到三维空间下,利用分治法的思想和鸽巢原理,设计出两种高效求解三维最近点对的方法,对比朴素做法,在时间复杂度上有显著的优化.

摘要： 文章基于VC++编程语言、计算几何知识编制计算软件,按照指定格式导入中泓线节点坐标文件、水面线高程点坐标文件,一键计算水面线测量高程点投影至中泓线的里程数值,输出至指定数据文件.对于S型河道进行了算法处理,自动识别出水面线高程点至多段线的唯一投影位置.不通过CAD绘制辅助线,即可实现里程的自动化计算.

摘要： 针对现有红外式触摸屏图像处理算法进行多点触摸识别时出现伪触摸点概率大、识别精度较低等问题,提出一种基于计算几何的新型红外式触摸屏多点触摸识别算法.通过在实际红外式触摸屏上对算法进行测试,证明优化后的新型算法相较于传统图像处理算法大幅降低了伪触摸点出现的概率,且显著提高了触摸精度.

摘要： 随着物联网的发展,隐私保护的计算几何方法成为SMC一个新的研究领域,其主要内容包括多边形相交、最近点对、凸包问题等。本文基于转角法设计安全点与多边形包含判定协议,解决了点与任意多边形包含的安全判定问题,并给出了正确性与安全性分析。

摘要： 提出了基于布线点阵的线探索优化算法,它继承了计算几何中无网格布线的优点,克服了计算几何算法中当器件排列繁杂时,其效率可能比传统的网格布线还要低的问题。首先采用布线点阵,减少探索的次数;然后运用死点避免方法保证算法的完备性,确保能够找到实际上存在的路径;另外还采用了路径优化方法减少了路径的拐点。最后,利用电路板测试结果展示平台仿真实验,获得了良好的布线结果和展示效果。

摘要： @@ 作为计算几何的基本问题，Delaunay三角剖分及其对偶图Voronoi图广泛应用于曲面重建，分子建模以及网格牛成。在众多的Delaunay三角剖分算法中，逐点插入算法是应用最广，也是目前研究得最多的算法，它具有实现简单，易于推广到高维的优点。逐点插入的Delaunay三角剖分算法主要由两部分组成：一是定位(pointlocation)，即找到新插入点在当前剖分中所在的单元;二是更新(update)，即将剖分更新使得包含新插入点的剖分仍然满足Delaunay性质。逐点插入算法的理论依据是往一个已经满足Delaunay性质的三角剖分中新加入一个点，可以通过有限次数的边转换(Edge flip)使得包含新插入点的剖分仍然满足Delaunay性质。逐点插入算法的效率由定位和更新决定。而点的插入顺序在其中起着关键作用。一个好的插入序一方面能提高定位的效率，另一方面也能有效减少新插入点打破剖分的单元个数。

摘要： 依据同构化凸壳构造基本定理,概述了二维点集凸壳研究的研究意义,综述了二维点集凸壳研究的国内外研究现状,分析了现行二维点集凸壳研究的国内外研究停滞不前成因,并率先提出了国内外计算几何界至今未见研究的"圆集凸壳及其算法研究"重要新问题。

摘要： Delaunay三角剖分是计算几何领域中的经典算法。本文讨论了影响Delaunay三角剖分算法健壮性的一些因素,给出了提高Delaunay三角剖分算法健壮性的一些方法。将欧式距离下的Delaunay剖分推广到Power距离下的带权的Delaunay剖分,通过合理赋权和误差控制等手段提高了Delaunay三角剖分算法的普适性和健壮性。与SOS算法[1]处理退化情况相比,本文的方法不会改变剖分点集和域中点的位置.

摘要： 三角剖分技术作为计算几何的一个重要研究领域一直受到人们的关注。本文首先对传统的三角网生长算法进行了分析和讨论,然后针对其时间复杂度高、效率较差等弱点,提出了一种改进算法,在满足实际应用需求的情况下,在一定程度上提高了三角剖分的效率。实验结果验证了改进算法的有效性。

摘要： 矢量偏移在地理信息系统和工业制造中是一个十分重要的算法，但是这些年来一直没有一个算法既满足速度方面的要求也满足成功率方面的要求，这主要是因为矢量图形的多样性，面对千变万化的矢量图形，偏移的结果也各不相同，很难有个算法能涵盖所有偏移时需要处理的情况。本文避过对这些矢量图形进行归纳总结，而从整体上进行处理，提出了一种基于缓冲区的矢量偏移算法，该算法在速度和成功率上都达到了很高的水平。并在该算法的基础上进行了建筑物综合方面的尝试，也取得了一定成果。

摘要： 矢量偏移在地理信息系统和工业制造中是一个十分重要的算法，但是这些年来一直没有一个算法既满足速度方面的要求也满足成功率方面的要求，这主要是因为矢量图形的多样性，面对千变万化的矢量图形，偏移的结果也各不相同，很难有个算法能涵盖所有偏移时需要处理的情况。本文避过对这些矢量图形进行归纳总结，而从整体上进行处理，提出了一种基于缓冲区的矢量偏移算法，该算法在速度和成功率上都达到了很高的水平。并在该算法的基础上进行了建筑物综合方面的尝试，也取得了一定成果。

摘要： 矢量偏移在地理信息系统和工业制造中是一个十分重要的算法，但是这些年来一直没有一个算法既满足速度方面的要求也满足成功率方面的要求，这主要是因为矢量图形的多样性，面对千变万化的矢量图形，偏移的结果也各不相同，很难有个算法能涵盖所有偏移时需要处理的情况。本文避过对这些矢量图形进行归纳总结，而从整体上进行处理，提出了一种基于缓冲区的矢量偏移算法，该算法在速度和成功率上都达到了很高的水平。并在该算法的基础上进行了建筑物综合方面的尝试，也取得了一定成果。

摘要： 本发明公开了一种基于计算几何学理论的多相混合均匀性的判断方法,具体包括以下步骤：S1、利用高速摄像机对实时气泡群进行图像拍摄，得到实时气泡群图像；S2、对所述实时气泡群图像进行处理，提取所述实时气泡群中每个不规则气泡的质心坐标，并对所述坐标做归一化处理；S3、基于气泡群的空间分布和归一化处理后的质心坐标，利用平均距离法判断所述实时气泡群的气泡混合的均匀性；S4、借助计算几何学理论，利用所述气泡混合的均匀性来判断工质与热源的混合均匀性和混和效率以及搅拌效果。本发明能够有效的判断随机不规则气泡群的混合均匀性，严格考虑了气泡的空间分布，减少了时间的复杂度，并有效的减少局部不均匀和整体不均匀的误差。

摘要： 本发明属于互联网技术领域，特别涉及一种基于计算几何的高效、快速的微博用户间影响力获取算法。本发明的算法首先定义一个空的待访问队列C

摘要： 本发明属于互联网技术领域，特别涉及一种基于计算几何的微博用户间距离的简单模型，首先定义两个空的待访问集合分别为C和F；构建用户的好友向量，根据上一步得到的用户好友集，经过变换，可以得到由用户好友集所构成的用户好友向量。用户间距离的获得，由以上所述两个步骤可以得到用户好友向量，得到用户好友向量的基础上，识别用户的共同好友，并通过向量间运算获得用户间距。本发明的优点在于：此微博用户间距离的简单模型巧妙地运用了空间向量点乘方法，能够更加准确地表示出不同情况下用户节点间的距离值，该模型还可以反映用户的潜在影响，并能进一步衡量节点的重要性，而且精度得到保证。

摘要： 本发明属于轨道交通技术领域，特别涉及一种基于计算几何的高效、快速的地铁裂缝主干提取算法及系统，机器识别连通的裂缝的算法流程，首先定义一个空的待访问队列Cn，以及一个空的存储空间Cxy；裂缝区域凸多边形的构造，根据上一步运算得到的所有裂缝像素点的横纵坐标，经过运算，可以得到由裂缝像素点集所构成的一个凸多边形；采用矩形框标识裂缝主干，由以上所述两个步骤可以得到凸多边形，得到凸多边形的基础上，识别裂缝的主干区域，并使用匹配的矩形框把相应区域标识出来；本发明的益处在于：此裂缝主干提取算法及系统结合了自动检测及人工检测的优势，人工工作量大大降低，而且精度得到保证，是一个较好的裂缝主干提取算法及系统。

摘要： 本发明公开了一种基于计算几何和模拟退火的空域扇区划分方法，该方法通过计算机系统辅助实现，系统中包括一个扇区划分子系统，扇区划分子系统用作区域管制扇区划分方法的实现平台；本发明根据管制空域结构和交通流量空间分布，建立了管制扇区分割的模糊多目标函数和约束条件函数，提出了划设空域的二分策略，并结合模拟退火算法对扇区优化划设问题进行求解,结合二分策略的模拟退火方法满足了全局最优，扇区划设多目标优化的总体满意度比仅考虑均衡扇区平均流量时有所提高，满足最小飞行时间、最小距离和扇区边界与主要交通流的交叉角的约束，保障空域运行安全和减少航班延误。

摘要： 本发明公开了一种框架结构工装刚强度计算几何特征快速前处理方法。为解决框架结构工装刚强度有限元计算时实体网格划分法中，网格多、计算量庞大和中性层法手工提取零组件几何结构、参数效率低下的问题，利用CAD系统提供的API接口进行程序设计开发，拓展原生CAD软件功能，对框架结构工装小体积连接件自动清理去除、零组件类型自动判别、工装零件厚度等参数自动识别归类，并自动分类建立框架结构工装刚强度计算标准接口的曲面模型，通过在ABAQUS中进行曲面模型共节点操作，实现框架结构工装刚强度模型快速前处理，避免了大量重复性手动操作，极大提高了框架结构工装刚强度计算几何特征前处理效率。

摘要： 本发明公开了一种基于计算几何学理论的多相混合均匀性的判断方法,具体包括以下步骤：S1、利用高速摄像机对实时气泡群进行图像拍摄，得到实时气泡群图像；S2、对所述实时气泡群图像进行处理，提取所述实时气泡群中每个不规则气泡的质心坐标，并对所述坐标做归一化处理；S3、基于气泡群的空间分布和归一化处理后的质心坐标，利用平均距离法判断所述实时气泡群的气泡混合的均匀性；S4、借助计算几何学理论，利用所述气泡混合的均匀性来判断工质与热源的混合均匀性和混和效率以及搅拌效果。本发明能够有效的判断随机不规则气泡群的混合均匀性，严格考虑了气泡的空间分布，减少了时间的复杂度，并有效的减少局部不均匀和整体不均匀的误差。

摘要： 本发明属于互联网技术领域，特别涉及一种基于计算几何的高效、快速的微博用户间影响力获取算法。本发明的算法首先定义一个空的待访问队列C

摘要： 本发明属于轨道交通技术领域，特别涉及一种基于计算几何的高效、快速的地铁裂缝主干提取算法及系统，机器识别连通的裂缝的算法流程，首先定义一个空的待访问队列Cn，以及一个空的存储空间Cxy；裂缝区域凸多边形的构造，根据上一步运算得到的所有裂缝像素点的横纵坐标，经过运算，可以得到由裂缝像素点集所构成的一个凸多边形；采用矩形框标识裂缝主干，由以上所述两个步骤可以得到凸多边形，得到凸多边形的基础上，识别裂缝的主干区域，并使用匹配的矩形框把相应区域标识出来；本发明的益处在于：此裂缝主干提取算法及系统结合了自动检测及人工检测的优势，人工工作量大大降低，而且精度得到保证，是一个较好的裂缝主干提取算法及系统。

摘要： 本发明属于互联网技术领域，特别涉及一种基于计算几何的微博用户间距离的简单模型，首先定义两个空的待访问集合分别为C和F；构建用户的好友向量，根据上一步得到的用户好友集，经过变换，可以得到由用户好友集所构成的用户好友向量。用户间距离的获得，由以上所述两个步骤可以得到用户好友向量，得到用户好友向量的基础上，识别用户的共同好友，并通过向量间运算获得用户间距。本发明的优点在于：此微博用户间距离的简单模型巧妙地运用了空间向量点乘方法，能够更加准确地表示出不同情况下用户节点间的距离值，该模型还可以反映用户的潜在影响，并能进一步衡量节点的重要性，而且精度得到保证。