基于有向弧的改进多边形拓扑关系生成算法

文章提出了一种基于有向弧段的多边形拓扑关系生成算法,改进了传统算法.算法对每个结点的关联孤段按方位角排序并对这种有序性进行了补充定义,同时为弧段增加两个方向相关的字段,分别表示弧段的方向和是否被遍历过,搜索多边形的同时对遍历过的有向孤段加以标记.本算法避免了多边形的反复搜索和内角的计算,提高了建立多边形拓扑关系的效率.最后,时该算法进行了分析和实例计算.     

基于有向弧的多边形拓扑关系生成算法

本文提出了一种基于结点弧段邻接关系自动生成多边形拓扑关系的算法,对每个结点的关联弧段按方位角排序并对这种排序进行了补充定义,对弧段的方向也作了相关规定。以此为基础,本算法避免了多边形内角的重复计算和反复搜索,提高了建立多边形拓扑关系的效率。最后,对该算法进行了分析和实例计算。     

基于夹角变化趋势的多边形自动搜索和生成算法

利用左转算法生成多边形是GIS中面域组织和拓扑关系建立的常用算法。根据算法规则,对于由顺时针方向和逆时针方向建立的多边形都可以生成多边形文件,这就会产生一些重复多边形和无效的多边形。为此,提出了基于夹角变化趋势判断多边形搜索方向的算法,根据左转或右转算法得到的点组顺序,分别计算由起始点出发的弧段的方位角,根据相邻弧段夹角的和来判断多边形的搜索方向,实现了每一多边形都是由左转算法生成,完成了多边形的自动建立。该算法有效地判断了多边形的搜索方向,避免了无效多边形的生成。     

具有拓扑关系的任意多边形裁剪算法

多边形－弧段－结点之间的联系是描述多边形空间拓扑关系的重要方法,为了维护裁剪前后这种拓扑关系的正确与继承性,本文在Ｗｄｉｌｅｒ－Ａｔｈｅｒｔｏｎ算法的基础上提出了一种新的算法。新算法中主要特点是将原算法中的交点表改为交点、弧段混合表,沿用原算法的追踪方式,但追踪目标由顶点序列改为弧段序列,使之适应具有空间拓扑关系的任意多边形的裁剪要求。     

拓扑多边形自动构建的一种改进算法

多边形的构建是地理数据拓扑关系建立的难点之一,其算法的自动化、速度和复杂性一直是GIS界研究的一个重点。在分析文献犤6犦算法局限性的基础上,根据解析几何的原理,提出了一种基于方位角计算的拓扑多边形自动构建的改进算法,较好地解决了多边形构建中弧段断开处理和多边形拓扑关系确定的问题。所提算法结构清晰、简单易懂,且程序容易实现。     

GIS缓冲区重叠合并的快速算法

为了解决地理信息系统（ＧＩＳ）缓冲区多边形间重叠合并问题，本文对正负缓冲区多边形边界相交后结点上弧段的方向规律进行了分析，提出了结点上有向弧段的删除规则。基于这一规则，形成了缓冲区多边形重叠合并的算法。该算法避免了通过多边形与曲线包容关系的判断来决定弧段取舍的复杂计算，因而具有简捷、高效的特性。     

一个基于图的多边形拓扑关系生成算法

本文提出了一种基于图的多边形拓扑关系自动生成算法和实例。该算法只需利用图中弧与多边的拓扑信息,避免了多边形内角的计算与比较,算法中根据图的拓扑特征采有效的策略,加快了多边形自动生成的速度。     

GIS中孤岛和内点快速归属算法

针对GIS拓扑数据结构的建立,该文提出了一种快速进行内点和孤岛归属的算法．算法首先利用“面积法”实现外多边形的识别并获得外多边形左极点,然后利用“改进的射线法”将识别后的外多边形左极点和内点向左侧引出射线,并获得与弧段的交点,最后利用弧段的特征获得外多边形和内点的归属关系．由于该算法充分利用了弧段的特征,从而避免了多边形的组织和弧段的重复处理以及非直接包含关系的判断,保证了海量数据生成拓扑数据结构的效率．同时文章还对归属中的退化问题提出了解决方案．算法的实际应用表明,该算法具有较高的效率和较强的实用性．     

判断点与多边形拓扑关系的改进算法

为了解决射线法不能有效地判断点在复杂多边形内或外的问题,根据射线与多边形边界相交的特性,分析射线所经过的多边形的不同类型顶点,提出了对顶点数加1、加2和加3的运算方法。通过判断交点个数的奇偶性,改进了射线法,并给出了计算模型和算法的详细步骤,简单有效的将现有的射线法扩展到更复杂的多边形中,能准确的判断点与多边形的位置关系。4种不同算法对比分析结果表明,该算法能解决其它3种算法存在的问题,并且在简单多边形和复杂多边形中都是有效的。     

多边形链求交的改进算法

多边形链求交是CAD&CG及相关领域研究中的一个基本问题 利用多边形链的凸凹性、单调性等特性 ,结合包围盒技术 ,在扫描线算法基础上 ,提出一种多边形链求交的改进算法 该算法特别适用于包含大量直线段且交点数相对于顶点数少得多的多边形链求交的情况     

基于隐函数插值的连续多分辨率模型

提出了一种基于变分隐函数插值的连续多分辨率模型生成算法,通过递归地删除网格模型中的边得到连续的简化模型.算法采用变分隐函数插值的方法对网格模型分区域插值,生成原始模型的区域插值隐函数曲面,并以对应隐函数曲面上的采样点作为边折叠的目标点.算法建立了可调加权控制函数来控制边的简化顺序.在模型简化过程中,可通过交互调节控制函数的权值执行不同的简化原则,使得重要度低的边优先删除.此外,通过建立独立集,避免了模型的局部过度简化.实验结果表明,此算法能实现较理想的简化效果.     

一种基于最小搜索圆平面多边形域约束Delaunay三角剖分算法

给出一种新的基于边优先的二维多边形域任意散乱数据的约束Delaunay三角剖分算法.算法结合网格分块技术,提出基于最小搜索圆的点搜索思想,并证明了该思想的正确性,有效地提高了搜索第三点的速度.算法中散乱数据可以是任意复杂的折线、封闭多边形环及离散点.另外,在三角剖分过程中,实时地去掉封闭点和封闭边,极大地加快了构网速度,实现了平面多边形域散乱数据的快速约束Delaunay三角化.     

基于多态蚁群优化的图像边缘检测

为了获得更好的边缘检测效果,提出了多态蚁群优化的边缘检测算法。通过侦察蚁的局部搜索标记侦察素,在搜索蚁进行全局搜索的过程中辅以侦察素的作用,提高算法的寻优能力。实验表明,算法在能够提取出弱边缘的情况下,有效地抑制了噪声和纹理信息。     

折线链节点标注技术

针对传统多边形位置关系计算比较烦琐,以及简单多边形的理论难以拓展到一般多边形的问题,提出标注节点状态的方法.通过定义11种位置来描述折线链上每个节点的状态,再采用"线段端点与线段"和"线段端点与邻折线"的标注方法来实现任意折线链的标注,同时利用两线段分割预处理使相交仅发生在端点处,从而使算法更高效;然后给出折线链基本位置关系的节点特征,并且探讨了三维顶点的标注方法.该方法的标注原理简单、方法实用,算法空间和时间复杂度分别为O(n)和O(n2).实验结果表明,该方法对任意形状的折线链都能实现稳定标注;通过搜索节点状态特征可以求解折线链间的相互关系,还可以实现一般折线链的碰撞检测、相交区域计算以及多边形简单化分解等.     

一种基于树结构的立体图像特征提取算法

针对立体图像匹配中的特征检测问题，提出了一种基于树结构的立体图像中边缘点、直线段、交点和凸多边形区域等特征的检测方案。该方法首先基于改进的Canny算子实现立体图像边缘的检测；基于立体图像的边缘梯度信息，文中提出一种分层并行式迭代式链码跟踪方法实现图像中直线段的检测：为提高检测速度并有利于凸多边形区域特征的检测，基于凸多边形区域的几何定义，通过提取直线段交点并采用树结构实现对已检测的相关直线段信息的遍历处理，最终得到树结构表示的凸多边形区域特征。实验证明，所提方法在结构化环境具有很好的检测精度和实时性。     

四边形网格划分过程中的边界提取与优化算法的实现

提出一种非封闭曲面的海量空间数据点四边形网格划分过程中的边界优化处理算法和边界快速提取方法;详细论述了边界拟合、边界跳跃、边界分离、边界融合、边界封闭的处理过程;边界点的提取算法,确保边界点提取的正确性,从而避免数据划分过程中带来的数据边界失真现象.给出边界优化处理和边界提取算法的运行实例,说明了算法的可行性.     

粒边缘模型及其实现

针对现有边缘提取算法难以提取任意形状、任意分布区域的边缘及与具体对象的相关性不密切等问题,构建一种粒边缘模型,并给出对应的实现算法：任意区域边缘提取算法（Arbitrary Region Edge Extraction,AREE）。粒相关边缘由拓扑信息系统、概念粒、连通粒和边缘空间等新概念组成。AREE算法定义行连通段,给出并证明计算边缘集的定理,搜索内点,完成边缘提取。对比分析和实验结果显示：算法能精确、快速地提取出各类图像中任意连通粒的边缘。     

Finding convex edge groupings in an image

In an image, there are groups of intensity edges that are likely to have resulted from the same convex object in a scene. A new method for identifying such groups is described here. Groups of edges that form a convex polygonal chain, such as a convex polygon or a spiral, are extracted from a set of image edge fragments. A key property of the method is that its output is no more complex than the original image. The method uses a triangulation of the linear edge segments in an image to define a local neighborhood that is scale invariant. From this local neighborhood a local convexity graph is constructed; this encodes which neighboring image edges could be part of a convex group. A path in the graph corresponds to a convex polygonal chain in the image, with a cyclic path corresponding to a polygon. We have implemented the method and found that it is efficient in practice as well as in theory. Examples are presented to illustrate that the technique finds intuitively salient groups, including for images of cluttered scenes.     

Towards a Systematic Method for Proving Termination of Graph Transformation Systems

We describe a method for proving the termination of graph transformation systems. The method is based on the fact that infinite reductions must include infinite ‘creation chains’, that is chains of edges in different graphs of the reduction sequence, such that each edge is involved in creating the next edge. In our approach, the length of such creation chains is recorded by associating with each edge label a creation depth, which denotes the minimal length of a creation chain from an edge in the initial graph to that edge. We develop an algorithm which can prove the absence of such infinite chains (and therefore termination), analyse problems of the approach and propose possible solutions.