制造单元设计中心半边图与拆分重组算法

提出了半边自组图理论,半边附属于顶点,一对半边可结合为边。用半边图来描述复杂优化问题可能解,在此基础上设计了针对图的拆分重组算法,用此算法求解了一个典型的复杂组合优化问题,制造单元设计问题。示例表明,半边图语言能够准确地表达可能解中的复杂结构和各种约束,20台机器50种零件分组实验证明,7次迭代计算即可达到优化目标。     

机器可选制造单元设计的半边图划分模型

机器可选制造单元设计问题是一类含有多种局部约束的复杂组合优化问题,用图划分算法解决此类问题将会面临指数级个图的划分。论文提出半边图理论,半边附属于顶点,一对半边可结合为边。用半边及其结合性表示各种局部约束,将机器可选制造单元设计问题转化为基于半边图的组合优化问题,即计划路径可选的半边图划分问题。     

机器可选制造单元设计的半边图挤出吸入算法

计划路径可选的半边图划分问题是一类含有多种局部约束的复杂组合优化问题。设计了针对半边图划分问题的半边图挤出吸入算法,用此算法求解了机器可选制造单元成组设计问题。示例表明,半边图语言能够准确地表达可能解中的复杂结构和各种约束。20台机器20种零件分组实验证明,平均12.4次迭代计算即可达到优化目标。     

Internet资源属性关系的新拓扑模型——时变半边图

引入半边概念描述Internet资源的特征属性，为网络环境下各类资源特征属性建立一个统一描述框架；扩展一般情况下的资源关系表示图，提出了资源属性关系的时变半边图模型；以网络的无尺度特性作为资源关联关系的演化规律的理论依据，给出时变半边图的一个具体生成算法。时变半边图能更方便地反映资源属性之间的动态拓扑关系，具有很好的可扩充性，可望再现真实网络的无尺度特性。     

一种基于散列函数与半边数据结构的TIN拓扑重构算法*

TIN拓扑重构是数字化露天矿软件诸多应用中重要的基础算法之一。顶点聚合与边合并是TIN拓扑重构算法中两个关键内容,用散列函数根据顶点坐标计算顶点散列地址,并用链地址法辅以AVL树解决顶点散列地址冲突,以提高顶点查询效率;采用改进的半边结构存储TIN,在顶点聚合的同时,通过为每个顶点建立入射半边表,完成半边的快速合并。实验及应用表明,算法时间复杂度近线性,能够满足大数据量条件下TIN拓扑快速重构的需求。     

保持视觉外观特征的网格简化

针对附有纹理属性的网格模型,提出并实现了一种保持模型基本外观和形状特征的多分辨率网格简化算法.采用半边折叠操作,综合考虑了网格模型半边的几何重要性和纹理属性重要性,将其作为各半边的折叠代价来确定模型中所有边的折叠顺序.预先对网格模型中的边界边和纹理边进行标记,并在简化过程中进行加权处理.实验结果表明,即使在急剧的模型简化后,该方法仍能很好地保持原有模型的视觉外观和形状特征.     

基于半边图模型的蛋白质建模研究

适合大中型蛋白质的建模方法目前尚属于空白。设计出一种新预测模型,称为“半边图模型”。利用半边图模型描述底层数据结构,进行底层计算,确立蛋白质的立体结构。新模型适于表现原子之间和原子团之间的相互结合作用,能够模拟大分子相互作用的蛋白质真实折叠环境,即大分子相互作用的环境。     

基于半边结构的STL文件快速拓扑算法

针对三维模型转换为STL文件后会丢失三角面间的拓扑关系,在对STL格式文件进行读取和分析时,提出了一种基于半边结构和哈希表的快速拓扑重构算法。在读取数据过程中,通过哈希表建立无重复位置信息的点表,并在其中维护一个未添加邻接面的半边集合。依据该集合和拓扑算法完善面的拓扑关系,实现在读取数据的过程中快速建立面的拓扑关系。     

支持外观属性保持的三维网格模型简化

对已有的三维网格简化技术进行分析,利用半边折叠操作对QEM(quadric error metric)算法进行改进,提出了一种基于二次误差测度(QEM)的网格简化算法,解决了非连续外观属性在简化过程中的畸变问题.通过分析顶点与非连续外观接缝的关系,得出了一个新的边折叠代价公式,使得外观畸变在简化过程中尽可能地推迟;并且在执行半边折叠时给受影响的三角形找到了合适的替换wedge,避免外观畸变的发生.实验结果表明,该算法保持了QEM 算法的高效性,同时在几何属性和外观属性上都取得了令人满意的简化效果.     

面向Web的机械产品三维模型简化算法研究

对机械产品三维模型数据量大不利于网络传输和Web显示的问题,提出了基于半边折叠的三维模型简化算法.通过引入顶点领域三角形平均面积、顶点领域三角形的法向量变化以及折叠边的边长,计算折叠代价,通过对折叠代价排序与预先设定好的阙值,对机械产品三维模型进行简化处理.实验结果表明,该算法有效减少了机械产品三维模型的数据量,提升了Web环境下机械产品三维模型数据传递和浏览器显示的流畅性,对机械产品分布式设计和制造技术的发展起到了促进作用.     

半边图模型之构造演算

提出一个动态可增殖的多层次自组织认知系统,每个层次具有形式上一致的知识表示方法,各层的自组关联、自组聚合、归约和样本表达四个知识处理模型是实现系统自组织层次增殖的核心模型。指出若要实现层次可自组织增殖的系统,其关键是要设计一个合理的聚合归约演算系统;提出一个适用于各个层次的基于可结合半边的自组图知识表示法,先给出自组图形式化的静态定义和动态定义,然后以自组关联模型为背景给出对应的自组图构造算法。     

随机图的均匀边染色算法

图的均匀边染色是指图中任意两条相邻的边都分配到不同的颜色,且任意两个色类的颜色个数最大相差1。对图 进行均匀边染色所需的最少颜色数叫做 的均匀边色数。本文提出了一种启发式算法,能够求解图的最小均匀边色数。该算法根据均匀边染色条件,设计了两个子目标函数和一个总目标函数,借助染色矩阵的色补矩阵迭代交换,逐步寻优,直到找到最优解时结束。本文给出了详细的算法设计流程,并且进行了大量的测试和分析,实验结果表明,该算法可以高效地求出给定点数的图的最小均匀边色数,算法时间复杂度不超过 。     

半直觉模糊图与应用

将对象作顶点集,用直觉模糊数刻画对象间的相关性和不相关性表示成直觉模糊边;建立了半直觉模糊图模型。定义了半直觉模糊图的生成子图、度、路径、相关截图、序关系、最大生成树等概念。给出基于半直觉模糊图的聚类分析算法,分析了算法的复杂度。结合经典实例作了基于半直觉模糊图的聚类分析,结果显示基于半直觉模糊图的聚类分析算法复杂度低于一般直觉模糊聚类算法。高效实用且自动化程度高。     

Convergence analysis using the edge Laplacian: Robust consensus of nonlinear multi‐agent systems via ISS method

This study develops an original and innovative matrix representation with respect to the information flow for networked multi‐agent system. To begin with, the general concepts of the edge Laplacian of digraph are proposed with its algebraic properties. Benefit from this novel graph‐theoretic tool, we can build a bridge between the consensus problem and the edge agreement problem, we also show that the edge Laplacian sheds a new light on solving the leaderless consensus problem. Based on the edge agreement framework, the technical challenges caused by unknown but bounded disturbances and inherently nonlinear dynamics can be well handled. In particular, we design an integrated procedure for a new robust consensus protocol that is based on a blend of algebraic graph theory and the newly developed cyclic‐small‐gain theorem. Besides, to highlight the intricate relationship between the original graph and cyclic‐small‐gain theorem, the concept of edge‐interconnection graph is introduced for the first time. Finally, simulation results are provided to verify the theoretical analysis. Copyright © 2015 John Wiley & Sons, Ltd.     

基于凸包特征的细分曲面求交研究

主要针对具有凸包特征的细分曲面提出了一种有效的求交的方法,该方法适用于任意具有凸包特征的细分曲面中.该方法主要是利用二部图跟踪两个细分曲面中可能相交的面.在应用二部图的基础上,选择半边数据结构,应用轴向包围盒法进行相交检测,使得具有凸包特征的细分曲面的求交得以实现.     

基于交互式图论的目标边缘检测算法

针对传统边缘检测算法无法准确提取目标及其边缘的问题,基于交互式图论的最大流/最小割理论提出了一种新的边缘检测算法,设计了一种新的代价函数OE_COST 目标边缘代价函数;通过建立图割模型,能够在分割出目标的同时提取出目标边缘。算法通过交互式选择背景及目标像素集合作为硬性约束,通过图像特征（如灰度级、空间信息等）建立代价函数作为软性约束,同时施加软硬约束达到提取目标边缘的目的。实验结果表明,本算法可以准确提取出目标及其边缘轮廓。     

基于三角片拼合的STL网格模型重建算法

采用三角片拼合的方法递增建立网格模型,新增三角片被归纳为5种类型.首先通过半边匹配确定新增三角片的类型;然后针对每一种类型使用不同的方法去除冗余顶点,并同时建立拓扑关系;最后通过顶点数组紧缩消除顶点空隙,将半边hash表转化为半边数组,完成网格模型的重建.该模型为改进的半边结构,具有完整的形状和拓扑信息,可以表示非流形边,是法矢调整、网格分块等后续处理的理想起点.实验结果表明,文中算法高效、鲁棒、可扩展.     

绣花缝针轨迹问题

运用几何计算和图论理论提出了一个绣花缝针轨迹自动生成算法：先对轮廓走向进行定义，通过轮廓铅垂方向的局部极值点的分割线将图案从上向下进行分割，采用交点的特征值比较彻底地解决了分割时的重点问题，将图案区域准确地划分成缝针能一次完成的若干个节点，在此基础上根据节点的邻接关系建立节点的邻接“图”，通过图论中半哈密尔顿路径或深度遍历方法找到节点的遍历(缝制)序列和每个节点的缝制方向，最后可对设定的起点、终点和缝针间隔的条件自动提供缝针的走向轨迹。