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

An algorithm of Polygon Auto-Construction Based on Angle Changing Tendence

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

Creating polygon is a normal arithmetic through turn left or right algorithm. According to the rule, polygons can be created by clockwise or anti-clockwise. But it may make some repeated and invalid polygons. The purpose of this paper is to introduce a method to judge polygon search direction and creat every polygon by only left algorithm. The method presented in this paper is to judge the polygons search direction to according to the angle changing between adjacent lines. Experimental results show that it is an efficient method to create polygons automatically and avoid invalid polygons.