划分树性能分析及其在数据选择中的应用

划分树是一种基于线段树的树形数据结构,主要用于对区间查询,如求区间第K大数。本文简单介绍了划分树以及对一些常用区间查询算法的性能进行了比较,体现出划分树在其中的效率优势。阐述了划分树在数据选择中的应用,用以加强用户体验。     

直线剖分平面算法的实现和应用

本文引入一种称为“区域树”的二叉树结构来表示若干直线由于相交而形成的对平面的剖分,并以之实现了一个“增加构造”方式的直线剖分平面算法。算法可用于解决许多与平面直线图形有关的问题,本文给出了如下应用实例：点定位问题,半平面公共交问题,简单多边形凸分解问题,简单多边形求交问题。     

面向交互的场景外存调度和空间剖分算法

提出了一个新的面向交互操作的三维模型数据外存调度算法,该算法解决了基于外存三维模型数据难以进行添加、删除、平移等交互操作的问题.同时,文中还提出了双层的BSP空间剖分结构,在交互操作的过程中,保持每个物体的BSP树不变,自适应地更新整个BSP场景绘制加速结构,使得交互操作不会降低场景的绘制加速空间削分结构的使用效率.     

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

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

一种含断层数据的变尺度加密三角剖分算法

由于传统无约束三角网在面对断层数据时无法处理,提出一种包含断层数据的变尺度加密三角剖分算法,主要用来解决如何将断层线段合理高效地嵌入无约束网格的问题。在传统逐点插入法的基础上提出"边界收缩"算法,得到高精细度凸包;采用变尺度方法整体网格进行合理加密,即设定剖分尺度,逐步细化断层数据;将细化后的断层数据嵌入原三角网信息中,利用生长法生成新的约束三角网。实验表明,对比其他三角剖分算法,经过变尺度加密后生成的三角网更加均匀,更容易实现断层线段的嵌入,提高了构网效率。     

Petri网仿真和自动化分析中的存储结构及算法研究

存储结构及算法是Petri网仿真和自动化分析研究中的重要内容，Petri网是一种特殊的有向图，通过对图的存储问题进行研究，提出了一种有向图的存储结构-树链式结构，给出了其构造算法，与其它有向图存储结构相比，它既可提高算法速度又能降低算法复杂性，树链式结构在Petri网仿真和自动化分析中应用优势明显，着重讨论了Petri网的树逻式存储结构，提出了基于该存储结构的可达树生成算法，所生成的可达树的树链结构形式，利于展开Petri网的各种分析算法。     

程序设计竞赛中线段树的四类典型应用场景

线段树是程序设计竞赛的重要知识点，应用场景复杂多变且不单独作为模板考察。现有教材和文献仅对线段树的基本理论与模板实现做了解析，而未对其在竞赛中的应用场景进行归类总结。学生只能依靠大量的习题训练和竞赛经验积累，才能摸清门路。对此，本文归纳出了关于线段树在程序设计竞赛中的四类典型应用场景：“扫描线算法的优化”、“树形结构信息的维护”、“带修改的结合律信息的维护”和“动态规划算法的优化”，并针对每类场景进行举例与解析。以期帮助学生对线段树的应用建立系统性的认识，从而降低学习难度，缩短学习周期，提升学习效率。     

面向并行负载平衡的数据剖分技术*

对传统的数据剖分技术和负载平衡对大规模并行计算性能的影响进行了综述,介绍了目前典型的几何剖分方法和图剖分方法的特点,并分析比较各种剖分算法及常用剖分软件包(ParMETIS、Zoltan、JOSTLE等)在实际应用中的优缺点,深入探讨了数据剖分技术是如何对超大规模数值模拟计算任务进行高效划分以解决负载平衡问题的,以期为开展并行计算研究和并行性能优化的研究人员提供参考。     

任意多功形单调链剖分算法

通过扩展计算几何中的“单调链”概念，提出了一种新的任意多边形剖分算法。首先利用新的概念将任意多边形分解为单调链，其后对单调链尖点排序，最后在相邻单调链间进行分割，从而完成任意多边形的剖分。算法的时间复杂度为Ｏ（ＮｌｏｇＮ）。本文最后给出了算法在用ＧＬ对实体模型进行光照中的应用。     

基于剖分理论的遥感影像模板数据模型

随着数据量的增加和应用需求的扩大,遥感数据的高效组织管理和快捷处理速度已经成为制约遥感技术应用的瓶颈,地球剖分理论和高性能计算为上述问题解决提供了一种可能途径。针对上述问题,结合地球剖分模型,在遥感影像剖分面片的研究基础上,提出了剖分面片模板的概念模型及数据模型,设计了基于剖分面片模板的计算模式,构建了一个小型化剖分遥感影像模板数据库,并通过一个模板化应用的具体实例对上述模型进行了部分验证。实验结果验证了模型的可行性,提高了目标检索的效率。     

一种基于MPI和OpenMP的剖分遥感影像并行分割方法

随着遥感数据量的快速增长,组织效率和处理速率成为其快捷应用的瓶颈,地球剖分理论和高性能计算为该问题解决提供了一种可能途径。基于上述思路,设计一种基于MPI和OpenMP的剖分遥感影像并行分割方法。该方法在地球剖分组织理论的研究基础上,针对遥感影像数据进行剖分化处理,依据应用需求确定剖分层级,形成有利于并行处理的影像数据剖分面片集合;在MPI集群计算和OpenMP多核任务处理环境下,对上述剖分面片集进行相应操作的并行化处理,最后把处理后的面片整合为所需要的结果数据。通过一个遥感影像数据K-Means分割的例子对上述方法进行验证。结果表明,该方法能在分割结果保持一致的情况下,有效提高遥感影像的组织效率和处理速度,达到了一定的加速比,实用性较强。     

基于中剖面kd-树的光线跟踪加速算法

kd-树算法是光线跟踪加速技术中效果最突出、应用最广泛的算法之一。在深入讨论该算法的基础上,提出了中剖面kd-树算法。该算法通过在预处理阶段加入一个场景层次信息索引表,将剖分平面固定为中剖面,并利用栈存储下一结点所需信息,节约了一半的存储空间;此外,将剖分轴按照最大轴向进行剖分,从而减少了光线同时穿过两个子结点的可能性,减少了访问时间,提高了算法效率。     

任意多边形单调链剖分算法

通过扩展计算几何中的“单调链”概念，提出了一种新的任意多边形剖分算法．首先利用新的概念将任意多边形分解为单调链，其后对单调链尖点排序，最后在相邻单调链间进行分割，从而完成任意多边形的剖分．算法的时间复杂度为Ｏ（ＮｌｏｇＮ）．本文最后给出了算法在用ＧＬ对实体模型进行光照中的应用．     

改进的统一于NIP的多边形三角剖分算法

本文引入非自交多边形的概念，将任意多边形转化为统一的非自交多边形ＮＩＰ，从而对任意多边形实现三角剖分．本文作者在应用原统一于ＮＩＰ的三角剖分算法过程中，针对剖分过程中原算法不能解决的情况，对原算法进行了改进．文章首先介绍该改进算法，然后对改进算法与原算法进行比较，最后给出改进算法在真实感图形生成中的应用．     

不平衡油耗数据的区间预测方法

对油耗数据进行区间预测时,数据的不平衡性会导致一般的区间预测方法得到的预测区间质量较低.针对上述问题,提出了基于SMOTE-XGBoost算法的区间预测模型.采用SMOTE算法增加训练集中少数类样本的数量,消除了训练集数据的不平衡性;对XGBoost算法的分位数损失函数进行改进,平滑其一阶导数原点周围的小区域,解决了分位数损失函数对树分裂的影响;通过训练区间预测模型,得到预测区间的上下界.最后基于QAR数据集进行对比实验,结果表明,该方法使预测区间具有较高的区间覆盖率和较窄的区间宽度,提高了预测区间的质量.     

一种优化的T-tree索引算法

分布武内存数据库已经成为了当今数据库的研究热点,而索引能够极大地提高数据库操作的性能.T-树索引是数据库系统中广泛使用索引技术之一.在T-树的基础上设计一种新的索引结构,在处理区间查询操作时其效率有明显的提高,也能够很好地解决数据插入、删除操作所造成的数据溢出问题.     

基于线段树的高效内存管理算法及其空间优化

现有的内存管理的工作多集中在内存分配的效率上,实时性较好,但易产生内存碎片。为此,提出基于线段树的高效内存管理方法。该方法将内存地址空间划分为内存段,建立内存管理线段树,基于所建立的内存管理线段树,进行高效灵活的内存分配和回收管理,减少了内存碎片的产生。另外,针对线段树空间开销大的问题,提出了线段树空间优化的方法。实验结果表明,所提出的内存管理方法,具有效率高、产生的内存碎片少、内存管理空间开销小等优势。     

一种顾及多义性的等深线快速生成算法

为了快速从海量水深数据中提取等深线,提出一种基于线段结点排序的等深线快速生成算法.首先对三角网生成等深线过程中由剖分方式引起等深线连接的多义性问题进行分析,并在确保航行安全的原则下提出改进的剖分规则优化三角网;然后遍历每个三角单元并提取等深线段,将提取的等深线段与已生成的等深线段根据结点位置关系进行排序;最后根据排序结果将等深点按顺序连接成等深线.实验结果表明,该算法提取的等深线能够正确表达海底地形,且具有较高的效率,可应用于海量水深数据的等深线生成.     

虚拟现实场景中基于八叉树的网格简化方法

在基于顶点聚类的网格简化算法中,通常对网格模型进行八叉剖分来建立一棵顶点树以表示整个网格模型的数据结构;但顶点在空间上分布的不均匀导致了顶点树的不平衡,增加了顶点树的深度。针对上述问题,论文提出了基于紧凑八叉树的剖分方法。该方法在虚拟现实场景中表现了较好的效果。     

一种基于八叉树与流水线技术的快速碰撞检测算法

针对存在大量运动物体的虚拟环境,提出一种基于空间八叉树剖分与流水线技术的并行碰撞检测算法.通过八叉树剖分,把虚拟空间剖分成一系列的子空间,然后只对同一空间中的结点进行碰撞检测.对空间内的每个物体构建包围盒树,同一空间中的任意两棵包围盒树遍历构成任务树,把任务树中的任务分配给不同的进程进行碰撞检测,并采用流水线与多线程技...