三维实体布局仿真中干涉检验的八叉树方法

本文提出了一种利用八叉树结构表示三维实体布局状态空间的方法，并在此基础上设计了一个三维实体布局仿真中干涉检验的算法，首次提出了利用二进制整数的“位”记录状态信息的方法，使状态空间数据量压缩至传统算法的１／１６；理论分析及实验结果证明了该算法的高效性。     

一种基于八叉树结构表达的三维实体布局启发式算法

本文在利用八叉树结构表达三维实体布局块及布局空间的基础上,根据八叉树同构节点匹配的思想设计了一个三维实体布局的启发式算法,并提出了三环图方法,解决了八叉树节点的同构识别问题．理论分析及计算的结果表明了该算法对于具有任意形状和大小的布局对象的三维布局问题来说效果理想．     

三维实体布局的八叉树语言及优化算法

本文设计了一个八叉树操作语言，并利用该语言实现了三维实体布局的优化算法，该算法能从任一初始布局可行解迅速收敛到一个局部最优解上，从而明显改善初始布局方案。文章最后给出了一个简单的应用实例。     

三维实体布局中实体初始合理摆放位置的研究

本文基于二叉树结构表示三维实体布局问题，证明了若干定理。根据这些定理设计了一个求得实体初始合理摆放位置的算法。实体初始合理位置的求得对以后的实际布局过程非常有利，否则，可能会有麻烦或得不到合理的布局。     

三维布局中八叉树节点的快速分解算法

本文在对八叉树子节点的顶点类型及构成三维实体精确ＣＳＧ模型的半空间的类型进行系统地分类的基础上，结合不同类型半空间的性质给出了一个三维实体的精确ＣＳＧ模型转换到八叉树模型的综合算法。通过对若干个不同的实体进行实际计算，结果表明该算法能够满足三维实体自动化布局的需要。     

三维实体布局中改进局部最优解的冲突决策方法

利用博弈论中冲突决策的思想实现了三维实体布局从一个局部最优解向另一个更好的局部最优解跳跃的算法，部分克服了传统算法的主要瓶－局部最优陷井的问题。理论分析及实例计算表明，当布局问题陷入某－局部最优解时，该算法利用冲突决策策略能有效地春跳入另一个更好的局部最优点上。通过一系列这样的跳跃，最终使布局问题获得一个高质量的解。     

一种基于二叉树结构表达的二维实体布局算法

利用二叉树表达二维实体布局问题,得到一个完全自动的二维实体布局算法,算法的复杂性为Ｏ（ｎ）,其中ｎ是区域树的结点数,提出了区域树面积因子等新概念,给出一个精美的旋转区域树的方法,证明了若干基本定理。     

用全剖视图帮助重建三维实体算法的探索

本文提出一种算法,先把含有全剖视图的视图转化成相应子实体的视图,由此构造出三维子实体,再把三维子实体合并,提供了一种利用全剖图帮助重建三维实体的途径。并在AutoCAD平台上验证了算法的有效性。本算法主要适用于剖切平面在实体对称位置的全剖视图,对于利用其它类型的全剖图帮助三维重建的算法也做了初步探讨。     

基于二叉树表示的三维实体树的生成及其应用

给出三维实体树的生成算法和凸体生成算法，这些算法是基于二叉树表示的三维图形处理的基本算法，可广泛用于三维布局，三维图形识别，三维长方体网格生成等各类不同的问题；容易个性算法使之适合扫描仪进行输入；由规定的一组函数或不等式作为输入，由规定的一组点人作为输入。     

基于细分曲面的三维服装柔性实体模拟

提出一种基于细分曲面的三维服装柔性实体模拟算法，该算法将整个模拟过程分为两个阶段：首先利用四点细分曲面造型方法生成三维服装刚性曲面，然后在刚性曲面基础上通过引入织物的物理模型来模拟三维服装柔性曲面，通过物理和几何模拟方法有机结合，算法有效解决了复杂衣片间的缝合问题，较大地提高了模拟的计算效率，同时，也提出了一种基于细分曲面层次数据结构的碰撞检测算法，有效提高了模拟速度，提出的算法已全部在所开发的三维虚拟服装试衣系统中得以实现，实验结果表明：该算法具有模拟效率高、交互性强和易于计算机实现等优点。     

基于群论的柏拉图立体着色方案三维模型构造

提出用柏拉图立体的空间旋转群来完成柏拉图立体着色方案三维模型构造的思想,解决与对称性直接相关的着色方案三维模型的构造问题;提出一种柏拉图立体旋转群群元新的分类方法;提出群元抽象对称性、局部色数和饱和色数3个新概念;提出对抽象对象进行抽象着色方案的构造,然后再将抽象着色方案映射到具体的轮换上,最后映射到三维模型空间去的构造方法,设计了实现该方法的算法,并用Visual C++6.0和Direct 3D实现了算法及三维模型可视化.软件运行结果验证了所提出的方法及算法的正确性.     

Efficient Minimum Distance Computation for Solids of Revolution

We present a highly efficient algorithm for computing the minimum distance between two solids of revolution, each of which is defined by a planar cross-section region and a rotation axis. The boundary profile curve for the cross-section is first approximated by a bounding volume hierarchy (BVH) of fat arcs. By rotating the fat arcs around the axis, we generate the BVH of fat tori that bounds the surface of revolution. The minimum distance between two solids of revolution is then computed very efficiently using the distance between fat tori, which can be boiled down to the minimum distance computation for circles in the three-dimensional space. Our circle-based approach to the solids of revolution has distinctive features of geometric simplification. The main advantage is in the effectiveness of our approach in handling the complex cases where the minimum distance is obtained in non-convex regions of the solids under consideration. Though we are dealing with a geometric problem for solids, the algorithm actually works in a computational style similar to that of handling planar curves. Compared with conventional BVH-based methods, our algorithm demonstrates outperformance in computing speed, often 10–100 times faster. Moreover, the minimum distance can be computed very efficiently for the solids of revolution under deformation, where the dynamic reconstruction of fat arcs dominates the overall computation time and takes a few milliseconds.     

基于可用性度量的分布式文件系统节点失效恢复算法

现有分布式文件系统中处理节点失效时采用的恢复策略耗费较多的带宽与磁盘空间资源,且影响系统的稳定性。通过研究分布式文件系统HDFS集群结构、数据块存储机制、节点与数据块状态之间的关系,定义了集群节点矩阵、节点状态矩阵、文件分块矩阵、数据块存储矩阵与数据块状态矩阵为度量数据块可用性建立了基础数据模型。在实现数据块可用性度量基础上,设计了基于可用性度量的节点失效恢复算法并分析了算法的性能。实验结果表明:新算法在保证系统中所有数据块可用性的前提下比原恢复策略减少了恢复所需带宽与磁盘资源,缩短了节点恢复时间,提高了系统稳定性。     

加入跳跃连接的深度嵌入K-means聚类

现有的深度聚类算法大多采用对称的自编码器来提取高维数据的低维特征,但随着自编码器训练次数的不断增加,数据的低维特征空间在一定程度上发生了扭曲,这样得到的数据低维特征空间无法反映原始数据空间中潜在的聚类结构信息.为了解决上述问题,本文提出了一种新的深度嵌入K-means算法(SDEKC).首先,在低维特征提取阶段,在对称的卷积自编码器中相对应的编码器与解码器之间以一定的权重加入两个跳跃连接,以减弱解码器对编码器的编码要求同时突出卷积自编码器的编码能力,这样可以更好地保留原始数据空间中蕴含的聚类结构信息;其次,在聚类阶段,通过一个标准正交变换矩阵将低维数据空间转换为一个新的揭示聚类结构信息的空间;最后,本文以端到端的方式采用贪婪算法迭代优化数据的低维表示及其聚类,在6个真实数据集上验证了本文提出新算法的有效性.     

Robust Computation of Intersection Graph between Two Solids

We propose a new robust algorithm for Boolean operations on solid models. The algorithm produces a consistent intersection graph between two input solids whose geometrical data are represented in floating point numbers. In order to prevent numerical calculation errors and inaccuracy of input data from causing inconsistency of the output, we put higher priority on symbolical connectivity of the edge-face intersection points than their numerical nearness. Each edge-face intersection point is symbolically represented using face names, which generate connectivity relations between the intersection points and the intersection line segments. The symbols with the same connectivity are made into clusters. The intersection line segments connected together at their end clusters form the intersection graph of two solids. Inconsistency of the connectivity of the clusters is detected and the intersection graph is corrected automatically. We describe the algorithm in detail for polyhedral solids, discuss extension to curves solids, and show its effectiveness by some examples of Boolean operations for two solids whose faces intersect at a very small angle.     

基于搜索空间划分的概念生成算法

概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用.概念格的构造在其应用过程中是一个主要问题.提出了一种基于搜索空间划分的概念生成算法SSPCG(search space partition based concepts generation),它将属性集合的幂集看作初始闭包搜索空间,迭代地将每个搜索空间划分为一些子搜索空间,并引入了子搜索空间的有效性判断,只搜索那些能生成正规闭包的子搜索空间,有效地提高了搜索效率;同时,在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度.由于所有子搜索空间是独立的,所以该算法可以很容易地扩展为并行算法.在随机生成的数据集和真实数据集上进行的实验测试表明,本算法的时间性能要优于Ganter提出的NextClosure算法.     

Pairwise Matching of 3D Fragments Using Cluster Trees

We propose a novel and efficient surface matching approach for reassembling broken solids as well as for matching assembly components using cluster trees of oriented points. The method rapidly scans through the space of all possible contact poses of the fragments to be (re)assembled using a tree search strategy, which neither relies on any surface features nor requires an initial solution. The new method first decomposes each point set into a binary tree structure using a hierarchical clustering algorithm. Subsequently the fragments are matched pairwise by descending the cluster trees simultaneously in a depth-first fashion. In contrast to the reassemblage of pottery and thin walled artifacts, this paper addresses the problem of matching broken 3D solids on the basis of their 2.5D fracture surfaces, which are assumed to be reasonable large. Our proposed contact area maximization is a powerful common basis for most surface matching tasks, which can be adapted to numerous special applications. The suggested approach is very robust and offers an outstanding efficiency.     

基于相空间的云计算仿真系统研究与设计

提出并实现了一种基于热力学相空间的云计算集群仿真系统设计方法。将云计算集群节点信息投影到相空间,构建云计算系统的相空间分析模型,将云计算集群节点的参数变化转变为其在相空间投影点的运动,并通过相空间的宏观热力学参数反映云计算集群的整体状态,为云计算核心调度算法的研究和云计算数据中心的运行测试提供了仿真测试平台和衡量标准。实验结果表明,全新构建的云计算仿真系统的仿真实验环境搭建简单,仿真结果能够直观、全面地反映出云计算集群的整体状态和调度算法性能等。     

基于聚类的空间数据多比例尺索引树

针对现有空间对象多尺度索引结构聚簇性不高的问题,在R树索引的基础上提出一种基于聚类的空间数据多比例尺索引结构。利用树的层次结构反映空间数据的多比例尺特性,用k-means算法对相同等级的空间对象进行聚类分组,减少空间区域覆盖和重叠。实验结果表明,该方法与基于四叉树的多比例尺索引相比,能有效提高空间数据多比例尺显示的性能。     

基于搜索空间划分的并行概念生成算法

概念格作为形式概念分析理论中的核心数据结构,在机器学习、数据挖掘和知识发现、信息检索等领域得到了广泛的应用。概念格的构造在其应用过程中是一个主要问题。本文提出了一种基于搜索空间划分的并行概念生成算法,它对整个闭包搜索空间进行划分,并引入一种有效的测试方法,只搜索那些能生成正规闭包的子搜索空间,从而有效提高搜索效率;同时,在计算闭包过程中保存一些必要的中间结果,用来提高闭包运算速度;由于所有子搜索空间相对独立,因此很容易得到一个井行的概念生成算法。