以节点操作确定两任意实心多边形交集的方法

两多边形求交问题在计算几何学、计算机图形学、地理信息系统、地质灾害预测评估及土木工程领域都有涉及.根据多边形节点所处的几何位置为其设置节点状态,基于多边形节点状态提出了以节点操作为核心的求解两多边形交集的方法和算法.该方法概念简单,易于计算机程序实现,避开了多边形求交运算中较难处理的布尔运算的奇异问题,能很好的解决重叠边、边与边相交于多边形顶点等多边形求交的难点问题.对于实心任意多边形的任意相交方式,该方法是准确和通用的.     

任意多边形无叠接靠拢算法的研究与实现

CAD 中常遇到这样一个问题:已知一多边形的位置,如何按指定方向放置另一多边形,使这二多边形以最紧密的方式排放,但不发生叠接现象?以往的方法繁琐,计算时间长。本文介绍一种新型的快速靠拢算法。该算法基于投影法上,再适当使用旋转处理和隐藏区域处理,使判断仅基于有限的多边形顶点,简化了处理过程。本算法可适用于任意多边形,可广泛用于计算机辅助机械落料,集成电路 CAD 中的布局,飞机、汽车制造业中的裁剪,制鞋、制帽和服装中的排料等领域,也为自动排料提供了优化算式的基础。     

计算机辅助排料问题中的快速移动算法

针对排料中涉及到的待排物体快速移动这一关键问题，基于“光照射原理”，提出了一种仅通过“相关线条”求交来确定移动位置的快速移动其法。该算法能解决凸、凹形状物体排料过程中的快速移动问题，从而为提高整个排料算法运算速度打下了基础。     

一种改进的MC算法

MC方法是医学图像三维重建常用方法.传统MC方法在计算中需遍历整个体数据场,而等值面只与部分立方体相交导致计算效率不高,对此已有相应的改进方法.但已改进的方法在计算过程中仍产生冗余多边形,使计算效率下降.笔者针对此问题提出了一种减少冗余多边形的进一步改进的MC方法,并根据该算法对CT数据进行三维重建.实验结果表明本算法与原改进MC算法效率相比有一定提高.     

一种存储复杂多边形包含关系的四叉树索引

地表覆盖/土地利用矢量数据中存在大量包含成千上万个空洞(甚至嵌套空洞)的复杂多边形,现有空间数据索引没有表达复杂多边形及其空洞之间的包含关系,导致空间数据冲突检测与更新等处理存在计算量大、效率低等问题.针对此问题,提出了一种存储多边形包含关系的四叉树索引方法.该方法根据结点中的多边形与四叉树相应象限中轴线相交的方式将多边形对象分为5种类型,即仅与X正轴相交、仅与X负轴相交、仅与Y正轴相交、仅与Y负轴相交以及与XY轴都相交,并将这些多边形对象分别存储在相应层次索引结点中的5个子列表(桶)中,然后在结点多边形对象中存储多边形之间的父子包含关系.最后设计并实现了该索引及相应的查询、插入、删除等算法,并用实际地表覆盖数据验证了本文方法的有效性.实验结果表明,采用本文索引方法的复杂地表覆盖矢量数据增量更新效率数倍于现有四叉树索引方法,且随着数据量的增加效率提高更明显.     

基于软件定义网络的多路径路由算法性能研究

基于不相交多路径的路由方案在负载平衡、容错等方面具有明显优势,但存在计算复杂度高的缺点,故对应的分布式算法难以在网络中大规模部署.通过分析软件定义网络的特点,论证了在其网络中部署不相交路径路由方案的可行性.其次,基于网络流的性质与不相交路径的图论性质,设计并实现了计算不相交路径的算法.最后,通过一系列基于不同网络模型的对比实验,验证所提算法较传统最短单条路径路由算法具有更佳的负载均衡.实验结果表明,该算法的性能与网络中链路能承受的负载极限阈值有关.     

简单多边形裁剪及交并计算的统一算法

研究发现了简单多边形裁剪和交并计算的内在一致性，从工程角度出发，以解决不规则物体布局问题为最终目的，提出了解决简单多边形裁剪和交并计算的统一，切实可行的算法，为不规则物体布局问题的解决奠定了基础。     

面向复杂产品交互虚拟装配操作的并行碰撞检测算法

运动对象间碰撞检测是交互式虚拟装配的一个基本问题,提出一种虚拟环境中运动对象间的并行化碰撞检测方法.该方法使用一种并行的、基于区域分割和快速相交校验排序的分解算法来包围盒层次模型,检测计算时依据用户的操作动态决定碰撞检测对以减少检测计算量,同时基于微机和局域网的并行方法来计算模型间碰撞,两个模型间碰撞检测时使用包围盒层次树动态更新方法.随后,以某型汽车底盘虚拟装配时的实时碰撞检测来验证算法性能.结果表明,该方法可以快速建立包围盒层次树模型,并可在交互操作中完成给定精度的实时碰撞检测.     

不规则多面体相交体积的逐级分解算法

将建筑工程量中沟道、基础扣减量计算等问题,归结为多面体相交交集体积的计算问题,提出了基于计算机图形学的计算不规则多面体相交体积的逐级分解算法.该算法以计算机图形学中的一些基本算法为基础,并改进了其中判断点是否在平面内的交点计数法,导出了计算公式.通过定义分割函数,使该算法无论是对凸多面体还是凹多面体的相交体积计算,都是适用的.以计算机软件实现了该算法,通过实例计算,验证了该算法的正确性.     

一种基于双平面镜的相机标定算法

为了从物体的二维图像得到三维重构模型,需要通过相机内部参数,建立已知物点、像点对应的关系模型.提出一种基于双平面镜的相机标定算法,用两个普通平面镜取得物体5个不同角度的二维图像,通过基于颜色信息和基于区域背景差的方法获取目标轮廓,用多边形动态规划算法获取轮廓的特征点以确定各个物体轮廓的对应点,最后根据特征点得到相机内部参数.多边形动态规划算法将时间复杂度从O(n3)降低到O(n2),算法的效率得到提高.     

基于相交关系的GML空间线对象离群检测算法

提出了一种基于相交关系的GML空间线对象离群检测算法DOL-IR,该算法首先计算GML线对象与其他空间对象的相交关系,定义基于相交关系的相异度,将其作为空间线对象之间距离的度量准则,利用DBSCAN聚类算法检测离群的基于空间相交关系的线对象.实验结果表明,算法DOL-IR能准确地检测出离群的基于空间相交关系的线对象,并具有较高的效率.     

基于动态包围盒树的碰撞检测算法研究

改进了以AABB包围盒为基础的碰撞检测算法.在多物体筛选阶段,利用AABB的构造特性和物体的运动特性,结合一维投影和二维投影来快速排除不可能相交的物体对,为了加快相交测试的速度,在投影测试之前划分坐标轴;在对可能相交的物体对进行进一步检测时,分割物体包围盒寻找可能碰撞的图元,在分割过程中建立动态包围盒树,减少了算法存储空间,有利于物体的更新操作.实现表明,改进后的算法效率有所提高.     

基于分治思想的空间三角面对快速相交检测算法

空间三角面对相交是计算机图形中的基础问题,相关检测算法已广泛研究.现有算法中着重异面时的相交检测,对共面情况研究相对较少,而在空间三角面对相交问题中共面、异面各种情况均较常见,共面相交检测会影响整个相交检测问题的效率和准确性,此外如何高效应用不同情况的检测算法的研究也较少.基于分治思想,考虑空间三角面对检测的各类情况及算法的实用性,将问题分为不相交快速排斥、共面相交检测和异面相交检测3类情况,通过优化算法流程来提高算法效率.实验结果表明,在共面和异面2种情况下,本文算法的计算效率均优于参考算法.     

虚拟数控车削系统中碰撞检测问题的研究

碰撞检测问题是虚拟数控车削系统的不可或缺的部分,有效、精确的碰撞检测对提高数控环境的真实性、增强虚拟环境的沉浸感有着非常重要的意义．碰撞检测问题就是测试物体之间是否存在相交的问题．采用合理的空间分割系统和层次包围盒是减少所需测试的多边形数目、提高碰撞检测的速度的有效方法．实验证明,采用基于空间分割方法的八叉树算法有效地提高了检测的速度,保证了虚拟动态加工环境中碰撞检测的实时性．     

多边形区域内储层建模结点三角剖分算法研究

结合储层建模结点数据的特点 ,提出了一种对多边形区域内建模结点数据进行快速三角剖分的算法 .如果区域边界边与剖分三角形可能相交 ,根据边界边顶点与剖分三角形确定的矩形区域的关系 ,对于不同情况 ,通过计算矢量叉积 ,或最坏情况下通过计算交点 ,来确定边界边与剖分三角形是否真正相交 .同时 ,讨论了在剖分过程中 ,对边界边链表进行实时更新 ,逐步减少边界边的思路 .虽然整个算法的时间复杂度最坏情况为 O( 3× m×n) ( m为多边形区域内结点形成的三角形个数 ,n为边界边个数 ) ,但在实际应用中 ,对大批量的储层建模结点数据进行三角剖分时 ,文中提出的算法具有比较高的处理效率     

一个有效的多边形窗口的线裁剪算法

在已有的一般多边形窗口的线裁剪算法的基础上提出了一个新算法,该算法通过内包围盒的方法,排除大量不与裁剪线段相交的多边形的边,从而降低了求交中复杂度极高的乘除法运算量,保证了算法的快速、高效.     

地块多边形拓扑关系的自动构建算法

针对地籍数据如何快速构建其拓扑关系的问题,根据地籍数据的空间拓扑信息,提出了一种新的地块多边形自动构建算法.在建立多边形拓扑关系时,算法只需要利用图的特征信息,避免了多边形内角计算与比较,以及坐标位置的比较.实例及算法分析表明,新算法减少了多边形的反复搜索和例外情形的处理,显著提高了多边形搜索的效率.     

自动布局问题的进化计算算法

二维不规则形状物体的自动最优布局是属于NP完全的组合优化问题，使用传统的方法很难得到满意解答。文章针对该问题提出了一个基于进化计算的算法，并以服装计算机辅助设计为例表明基于此进化计算计算的算法卓有成效地应用到自动布局问题。为了得到关于问题的自然和有效的编码，将问题变换为一种与之等价的关于多边形的运动规划问题，根据问题的特性设计了算法的3个重要算子，在解的解码和评价过程中则综合地利用了已有的最优算法。     

一种改进的启发式自动排版算法及其应用

提出了一种基于启发式搜索策略的自动排版算法,其基本思想是根据实际情况确定排序次数以提高材料利用率;通过待移动区域确定可能发生碰撞的实体以避免盲目检测;对排料物体先大步长移动,然后微调以提高排版精度.该算法已在服装CAD排版系统中得以实现,实验结果表明在布料利用率和速度方面都比较理想.     

快速高效的碰撞检测算法 

为了提高碰撞检测算法的效率,提出了一种快速高效的碰撞检测方法.利用Morton码存储物体信息,给出一种改进的图层级结构,可快速分割物体空间,减少物体对相交检测;利用图形处理器(GPU)的并行处理特性进行物体包围盒层级树构建、树遍历,不仅可以快速处理碰撞检测中的事务,还可节省存储空间.实验表明,该方法能够快速构建物体层级结构,并能进行高效的碰撞检测计算.