文件名称：区间树查询算法实现
文件大小：3KB
文件格式：CPP
更新时间：2015-04-08 07:30:43
计算几何 区间树查询 算法实现
截窗查询是对二维或三维空间中特定区域内的线段、多边形、曲线等进行分析处理的查询技术，是计算几何在诸如地理信息系统、计算机辅助设计、计算机辅助制造等领域广泛应用的重要方法。本文讨论的区间树查询算法，是在平面内线段均与坐标轴平行的理想的情况下，采用几何分析的方法，通过构造空间复杂度为O(n)的便于搜索的区间树，能够在O(log n + k)(k为所有报告出的线段数量）的时间内，完成与坐标轴平行线段对垂直线段区间的查询。