摘要
文章提出了一种基于有向弧段的多边形拓扑关系生成算法,改进了传统算法。算法对每个结点的关联弧段按方位角排序并对这种有序性进行了补充定义,同时为弧段增加两个方向相关的字段,分别表示弧段的方向和是否被遍历过,搜索多边形的同时对遍历过的有向弧段加以标记。本算法避免了多边形的反复搜索和内角的计算,提高了建立多边形拓扑关系的效率。最后,对该算法进行了分析和实例计算。
A directional-arcs-based algorithm for generating polygons＇topology relationships is presented in the paper, making some advances to existed ones. For the algorithm, each node＇s related arcs are sorted by azimuth where their order has been given an additional meaning. Two new attributes are added to arcs, one for the direction and another for whether the directional arc has been visited. While searching for possible polygons mark the visited directional arcs. Thus the algorithm avoids the repeated calculation of polygons＇ interior angles and the redundant search work. So the efficiency of generating polygons＇ topology relationships has been improved. Finally, analysis and instance of the algorithm is illustrated.
出处
《电脑与信息技术》
2008年第5期46-49,共4页
Computer and Information Technology
关键词
多边形
有向弧段
拓扑关系
GIS
polygon
directional arc
topology relationship
GIS
