三维精确power图的GPU并行计算

power图(加权Voronoi图)的计算是计算机图形学和计算几何等领域的一项基础任务.针对求解三维power图的传统串行方法所需的时间成本较高,且现有并行算法所得结果为近似解,提出一种新颖的GPU并行计算方法.首先给出power图与高一维受限Voronoi图的等价构造方法,将Voronoi图的无网格方法直接推广到power图的计算.因此,给定的加权种子点被置于更高一维空间中的一组方格内,据此快速搜索每个种子点的邻居关系,进而使用各个种子点与其若干个邻居的中垂面对各自的power胞元进行并行裁剪,以快速地获取三维空间中的精确power图.对比不同求解域下和5万个种子点的计算耗时,比现有方法具有超过3倍的加速比.

容量限制Power图快速计算算法（英文）

与Voronoi图不同,Power图有着精确限容的特性,可应用于众多领域.在普通Power图上,通过给每个站点增加权重来添加容量限制约束,即得到容量限制Power图.现有容量限制Power图的生成算法时间复杂度高,速度较慢.本文首先对Power图权值对于容量的单调性进行理论证明,然后提出了一种Power图权值的快速计算方法,相比于现有的试位法,能大幅提升容量限制Power图的生成性能.实验结果表明,文中算法具有速度快,精确度高,便于计算,密度适应性强等优点.

Power图的性质及构造算法研究

点集的 Power图是点集 Voronoi图的推广 ,特别适合用来解决涉及球 (圆 )的几何问题 .文中首先对 Power图的基本性质进行了几何化的证明 ;之后 ,研究了权为负数时对 Power图的影响 ,指出在 Power图的理论中允许权为负数 ,从而 Power图可以应用到具有负权性质的领域 ;最后 ,给出了平面点集的 Power图的构造算法 ,该算法利用 Power图与正则三角化互为对偶的原理 ,在点集的正则三角化的基础上构造 Power图 ,同时给出了实例以说明算法的有效性 .

Power图的离散生成

Power图是一种特殊的加权Voronoi图 ,该图中每个生成元点 pi 都带有权值wi 给出了一种直接构造Power图的算法 以每个生成元点 pi 为圆心 ,Power距离wi为半径画圆 ;然后将这些圆以不同颜色填充 ,并以相同速率向外扩展这些圆的边界 ,直到屏幕上所有像素点都涂上颜色为止 ,环绕 pi 的新边界构成Power图 该算法改进了在Voronoi图基础上构造Power图的传统方法 。

基于Power图求解容量限制P-中值问题

针对稠密需求下连续域上的容量P-中值问题,提出基于质心的容量限制Power图(CCCPD)理论,对连续P-中值问题进行近似建模,并加快计算过程。扩展Balzer试位法构造Power图,施加质心限制满足P-中值要求,施加容量限制满足需求密度下的容量要求。实验结果表明所提算法可快速得到近似可行解,同Alper Murata方法相比,计算效率高;同质心容量限制Voronoi图(CCCVT)相比,具有容量限制精确度高等优点,并能适应各种复杂需求密度函数。

质心Power图下覆盖路径规划算法

覆盖路径规划算法广泛应用于移动传感网络、群机器人系统等领域。研究基于质心容量限制Power图下的覆盖算法,对经典Lloyd方法进行扩展,在生成质心Power图的Lloyd算法基础上,改进后得到可用于路径规划的PD-Lloyd算法,考虑实际场景中个体移动的物理特性,给出两种优化策略,以增强算法效果和可信性。实验证明:该算法稳定性好,具有内在避碰特性,能产生较优的运动路径。

质心容量限制Power图一体化生成算法

Power图是带权重的Voronoi图,对Power图施加容量限制与质心限制,即可得到基于质心的容量限制Power图(Centroidal Capacity Constrained Power Diagram,CCCPD)。为解决现有CCCPD生成算法交替优化权重和站点位置带来的相互干扰、收敛减慢问题,提出对所有变量进行一体化优化的生成算法,采用多目标优化策略,直接优化质心限制和容量限制形成的混合能量。结果表明:所提算法的生成性能比传统方法提高40%。

Power图扫描生成算法研究

在现有Power图理论基础上给出了生成Power图的扫描生成法,该方法通过计算出屏幕上所有像素点与生成元的Power距离,然后对这些距离进行比较并排序,根据到某两生成元的Power距离相等的点一定在Power边上这一特点,画出所有符合条件的点,从而形成Power边,生成Power图。该算法程序设计简单,避免了复杂的数据结构。已用VC++编程实现,并给出了具体应用实例。

Power图的离散生成及应用

文章给出普通Voronoi图,给出Power图的定义,假设生成元点是完全相同的,即每一个生成元点的权值一样。在实际应用中,这种假设是不合适的,因此在动态构造Power图的基础上,给出构造以几家电影院为生成元的Power图应用模型。

基于Power图的高铁建设对城市空间格局研究

Power图的生成元不再是点而是power球,即到给定两power球距离相等的面为超平面。一般图形Power图在地理信息系统及城市规划等方面有着重要应用,如行政区域的划分,边界的管辖区,资源有效利用的划分,交通道路规划、快递服务辐射范围等等。现仅以京沈高铁建设对城市空间格局分区为例,应用离散构造法生成其一般图形Power图,对其控制区域和覆盖状况进行简要分析。

变容量限制质心Power图的计算

Power图作为Voronoi图的拓展,引入“权重”使其有着良好的限容特性。对普通Power图增加容量约束,使得每个站点的容量等于预设的容量值,则可以得到容量限制Power图;在此基础上,再增加质心约束,使每个站点刚好位于对应Power区域的质心,进一步得到质心容量限制Power图。在质心容量限制Power图中,容量限制条件均有明确的值,然而在某些应用中其往往是一个区间。针对区间容量限制问题,提出一种变容量限制质心Power图的计算方法。一方面,该方法通过不断调整各站点的权重以使得站点的容量满足区间限制;另一方面,Lloyd方法被用于优化各站点的位置到对应Power区域的质心;两者交替迭代优化,从而得到满足区间容量限制的质心Power图。在不同的密度和不同容量限制区间下的实验结果表明,该方法适用于不同密度下变容量限制质心Power图的计算,并且具有高效、适应性强等优点。

定点容量限制质心Power图生成

目的 Power图作为Voronoi图的扩展,有着精确的限容特性。在普通Power图上添加容量限制即得到容量限制Power图。考虑站点位置固定情况,对于基于质心的容量限制Power图目前未有较好的计算方法。为了解决该类问题,提出一种新颖的常密度下的定点容量限制质心Power图生成算法。方法通过调整站点的邻居站点的权值,优化该站点Power区域质心;在此基础上,按照相同比例缩放该站点Power区域,以达到优化容量的目的,最终生成所需Power图。结果在综合考虑质心约束与容量限制条件下,对算法在均匀容量限制与非均匀容量限制下生成的Power图进行对比实验,并且分析实验误差。本文算法能够较好地解决容量限制问题,得到当前条件下的最优解。结论本文算法在常密度下能稳定地生成容量限制质心Power图,具有精确度高和适应性强等优点。

异构群体队形光滑变换控制方法

针对现有群体队形控制方法在队形变换异构性、光滑性、条理性等方面的不足,提出一种基于几何约束机制的受限异构群体队形控制方法.首先采用Morphing方法生成由初始形状平滑变换到目标形状的一系列中间约束形状;然后引入基于质心的容量限制Power图对个体在约束形状中的内部布局进行建模,产生所需的异构分布;最后提出面向Power图的Lloyd导航算法,以控制个体进行无碰撞的光滑移动.实验结果表明,该方法稳定可靠,队形变换平滑流畅,非均匀人群分布可用于制作自然的群组动画和仿真真实场景,适用于不同规模、不同队形的异构群体队形控制.

三维限定Voronoi网格剖分细化算法

针对分段线性复合形约束条件下的三维限定Voronoi剖分问题,提出一种细化算法.首先证明了分段线性复合形中的元素在最终生成的三维限定Voronoi网格中可表示为Power图结构;受此启发,提出了对限定线段/平面片分别进行一维/二维Power图细化以实现三维限定Voronoi网格生成的细化算法,并且证明了该算法对于任意分段线性复合形收敛.最后通过实例验证了文中算法的有效性.

圆组填充算法驱动的平面马赛克模拟

为了生成不规则嵌片排列紧凑的马赛克图案,提出一种基于圆组排列的平面马赛克模拟方法.首先借助嵌片多边形的直骨架得到一组逼近嵌片轮廓的圆;然后以圆半径的平方为权值,在平面上生成关于圆组的Power图,使每组圆各自对应一个Power区域;最后采用松弛法,将圆组在其对应Power区域内尽可能增长到最大.通过不断迭代生成Power图和放大圆组,最后得到嵌片紧凑排列的结果.实验结果表明,该方法得到的马赛克图案有较高的覆盖率,能适应不同嵌片,具有较强的鲁棒性和灵活性.

边界约束下的词云拓扑保持算法

词云是一种典型的用于文本分析的可视化形式,更美观的可视化效果和更佳的实用性是研究者们研究的主题.针对边界约束下语义聚集的词云在单词发生改变时的紧凑布局和单词间拓扑结构保持的问题,提出一种适用于元组确定式文本的词云布局方式,在确定元组数目的基础上,用Power图剖分显示界面,利用单词间的属性依赖实现词云的初始布局;然后提出边界约束词云的拓扑保持算法,定义了5种约束规则、单词间相对约束力以及边界约束力,规定了词云在布局过程中的约束条件,以保证词云拓扑保持的同时实现单词在确定边界下的无重叠布局.针对词云的不同边界形状详细定义边界约束力,并分别对不同形状的词云进行局部单词放大、删除、缩小实验,结果显示,文中的拓扑保持算法在词云内单词发生变化时较好地保证视觉效果,同时有效地保持了原有的拓扑结构.

重要性驱动的中轴线

现有的中轴变换理论假定边界上各点具有同等的重要性,因而边界拓扑的微小改变将会产生一个完全不同的中轴骨架.针对该问题,提出重要性驱动的中轴线理论及相应的生成算法,进一步完善了传统的中轴线理论.首先对原始物体的边界进行稠密采样,根据问题的特点设置每个采样点的权重;然后计算带权重的采样点集的Power图,剔除落在边界外部的部分,得到初始的中轴线;最后对初始中轴进行剪枝,消除毛刺,最终生成稳定的中轴线.在医学图像处理和形状聚类中的应用。

基于最优传输理论的高质量点云重采样方法

目前通过3D扫描仪获取的点云仍旧存在一些缺陷:点云含有噪声,点云在不同方向上分布不均匀等.本文针对上述问题开展研究.主要工作为提出一种新的算法用于在点云上进行高质量的重采样,即使用较为稀疏的重采样点集去表达较为密集的原始点云的几何形状,同时重采样点集的分布可以满足用户预先指定的目标分布,并具备一定的蓝噪声性质.在最优传输理论的基础之上,本文方法将传统的点云重采样问题转化为一个最优化问题,并在点云上构建离散网格,使得针对网格的受限制的Power剖分方法能够迁移至点云上.随后利用交叉优化框架对该优化问题进行求解,并对每一个重采样点执行精确的容积约束.大量实验结果表明,本文算法输出的重采样点集可以实现精确自适应控制密度的目标,并且具备较好的蓝噪声性质.

面状LED发光体灯珠分布和组合连接优化算法

面状LED发光体灯珠的分布和分组问题,可建模为多约束优化问题来进行求解。提出了一种将面状LED发光体灯珠照度映射为质心容量限制Power图的容量,从而布局LED灯珠的方法,实现了面状LED发光体照度均匀的目标,进一步提出一种基于贪心策略的LED灯珠组合和连接优化算法,达到节省物料的目的。实例结果证明,所提方法简单、可行,布局和分组效果好,算法收敛速度快,可用于解决实际工程问题。

图犹豫模糊Power Heronian平均算子及其在多属性决策中应用

针对需要同时考虑属性关联性及整体均衡性多属性决策问题,联合图犹豫模糊集对于不确定信息的表达优势,提出一种基于图犹豫模糊Power Heronian平均算子的多属性决策方法。首先,给出图犹豫模糊数的得分函数、精确函数及距离公式;在此基础上,提出图犹豫模糊Power Heronian平均算子和图犹豫模糊Power加权Heronian平均算子;最后,将所提算子应用于多属性决策问题中,验证所提算子的有效性和可行性。