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

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

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

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

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

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

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

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

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

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

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

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

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

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

一种GIS拓扑多边形链搜索的改进算法

针对GIS拓扑多边形链搜索中悬挂弧段的处理问题,提出了一种改进算法。该算法利用在一趟搜索中,非悬挂弧段仅经过一次,而悬挂弧段会经过两次这一规律来识别并标记悬挂弧段;在进行多边形链搜索时,通过避让悬挂弧段以避免将其对应的关联弧段加入多边形链,从而保证搜索结果的正确性。测试结果表明,该算法能明显提高多边形链搜索的效率。     

快速多边形区域三角化算法与实现 *

多边形区域三角化的基本思想是 :首先将简单多边形分解为多个单调多边形 ,然后对每个单调多边形进行三角化。快速多边形区域三角化算法先由多边形顶点的位置特征分为不同的类型 ,并沿指定方向对顶点进行排序 ,然后顺序取出各顶点 ,根据顶点类型 ,确定准单调多边形的产生、增长或结束 ,最后对所产生的多个单调多边形进行三角化。该算法充分利用多边形的顶点、边的拓扑关系 ,计算量少、实现简单 ,适用于带有洞、岛的任意简单多边形 ,速度较快。     

基于拓扑映射的多边形顶点凸凹判别算法

通过拓扑映射,多边形顶点凸凹判别可以转化为映射点在射影直线上的位置关系问题。首先求得相邻边在两条射影直线上的映射点,基于一般映射点归纳得到顶点凸凹判别的4条规则,然后将两条射影直线上的映射点归结为一条射影直线,从而得到更有效的映射点求取方法,顶点凸凹判别规则统一为两条;进一步考虑非固有映射点的求取方法,提高了算法的稳定性,实验结果表明,该算法实现简单、速度快、稳定可靠。     

确定两个任意简单多边形空间关系的算法

阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。     

A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains

We introduce a new method for computing the geodesic Voronoi diagram of point sites in a simple polygon and other restricted polygonal domains. Our method combines a sweep of the polygonal domain with the merging step of a usual divide-and-conquer algorithm. The time complexity is O((n+k) log(n+k)) where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O(n+k) . Other polygonal domains where our method is applicable include (among others) a polygonal domain of parallel disjoint line segments and a polygonal domain of rectangles in the L ₁ metric. Received February 15, 1996; revised November 2, 1996.     

基于拓扑映射的点集在凸多边形内外判断算法

通过拓扑映射 ,点在凸多边形内外的判别可以转化为映射点在射影直线上的位置关系问题 .首先通过设置中心点 ,获取凸多边形各顶点的拓扑映射点 ,对于每个检测点 ,根据其映射点与顶点拓扑映射点的相对位置关系 ,即可确定检测点位于多边形哪条边的范围内 ;然后将检测点与该边进行包围盒测试 ,对于点在边包围盒外的情况 ,只需根据比较判别即可得到结果 ,对于点在边包围盒边界上或内部的情况 ,则需通过叉积运算进行判别 .该方法几何意义清晰 ,实验结果表明 ,该算法运行可靠 ,对于单个点或多点组成的点集均有较高的检测速度 .     

二维拓扑空间关系的最小集及其在时空数据模型中的实现

提出了二维拓扑空闯关系的一个描述框架并定义了二维拓扑空间关系的一个最小集。该最小集由6类不同的拓扑空间关系构成。该文证明了该拓扑空间关系集的完备性和互斥性,并给出了在时空数据模型STORM上的实现。     

Delaunay三角网支持下的多边形化简与合并

多边形的化简与合并运算是自动化制图综合中的重要算子,这类算子的设计要基于多边形几何特征,拓扑特征的分析,还需要一种有力的空间数据模型用于支持多边形各弯曲特征部位之间,多边形与多边形之间,多边形的各岛屿之间邻近关系探测,鉴于Delaunay三角网的“最大最小角规则”和“外接圆规则”,使得其成为空产邻近分析的一种强有力工具,因此在二维空间建立约束Delaunay三角网模型和形式检索机制的基础上,系统地讨论了多边形弯曲特征的化简,夸大,以及邻近多边形合并的方法,并将多边形化简分解为“岛屿”选取,凹部填充,狭长区域中轴化,保留凹部的夸大,以及凸部的弃除等几个步骤完成,又将多边形合并区分为吸刷式,包络式,分解式等3种情形,同时给出了这些算法的实验结果。     

一般多边形的碰撞算法

文章首先对凸多边形碰撞问题进行了仔细的考查,然后对一般多边形碰撞问题进行了深入细致的研究,在此基础上提出了求解凸多边形碰撞问题和一般多边形碰撞问题的最优算法。     

带有给定切线多边形的C5连续有理样条曲线

描述了一种与给定多边形相切的有理样条曲线的算法。在算法中,所有的有理样条曲线的控制点可以通过对多边形的顶点简单计算产生。所构造的曲线对多边形具有保形性。曲线可以局部修改。最后给出了两个算例。     

A unifying approach for a class of problems in the computational geometry of polygons

A generalized problem is defined in terms of functions on sets and illustrated in terms of the computational geometry of simple planar polygons. Although its apparent time complexity is O(n ²), the problem is shown to be solvable for several cases of interest (maximum and minimum distance, intersection detection and rerporting) in O(n logn), O(n) or O(logn) time, depending on the nature of a specialized selection function. (Some of the cases can also be solved by the Voronoi diagram method; but time complexity increases with that approach.) A new use of monotonicity and a new concept of locality in set mappings contribute significantly to the derivation of the results.     

多边形三角形分解的扇形扫描算法

讨论了任意多边形区域的三角形分解问题,提出了一种扇形扫描方法。该方法沿着多边形轮廓搜索各个可行的目标三角形,逐步将多边形未分解区域缩小,最终完成三角形分解。给出了分解实例。