基于二叉树的几何图形拓扑运算

2015-01-06 08:01:02蔡琪
电脑知识与技术 2014年34期

蔡琪

摘要:该文提出了一种基于二叉树的几何图形拓扑处理算法,实现几何图形间的精确处理。并能有效解决大多数边界问题,同时可以按需求设定不同的精度。

关键词:二叉树;拓扑运算;边界问题

中图分类号:TP311 文献标识码:A 文章编号:1009-3044(2014)34-8191-03

随着Web技术的发展,越来越多的应用被从传统的PC端移植到Web端,用户只需要通过Web浏览器就可以得到所需要的服务。这些Web上的应用不仅方便了用户,也使得自身变得越来越普及。例如百度地图每天的定位请求数就达20亿以上,可见其用户规模。而百度地图这类应用仅仅是WebGis中的一项小功能,而WebGis同样在在城市规划,交通规划提供许多功能支持。

WebGis是Web上的地理信息系统,其功能主要是对空间上采集的地理信息进行分析与处理,例如通过人口统计所得的数据得到的城市人口密度分布图,通过道路车辆统计所得的道路交通流量图。这类信息通常需要通过对采集信息进行精确的拓扑计算得出,例如要计算一个下图红线划定范围内的建筑面积,就需要拿红色区域和A,B,C,D四块区域进行逻辑判断,同时计算相交区域面积。而当前一些开源的拓扑运算库如Dotspatial等,存在着边界问题处理不好,精度值无法确定,效率不高等一些问题。

1 关键技术

1) 多边形的二叉树分割

对平面任意闭合多边形,若指定其包围区域为内侧,则边界与内侧相对的另外一侧为外侧,若要判断内外侧,一般通过多边形的方向进行判断。通常多边形的方向分为顺时针与逆时针,沿多边形方向,一般定义左侧为内侧,右侧为外侧,所以若指定包围的闭合区域为内侧,则多边形为逆时针。……

登录APP查看全文