论文部分内容阅读
地理信息系统正在获得越来越广泛而深入的应用。Web也已经成为地理信息访问、服务共享的主流平台。以空间查询与空间分析为主要内容的空间运算是GIS(GeographicInformation System，地理信息系统)的核心特征之一，具有计算密集、数据密集的特点，是空间信息服务(如 Web Feature Service)实现中的关键问题。与此同时，互联网地图服务的后台计算设施正在向着大规模、分布式、并行化快速演进。如何在此背景下，提供高效能的空间查询与空间分析功能是网络地图服务系统设计与实现中的挑战性问题。
在充分分析应用需求与技术可行性的基础上，本文在“十一五”863项目“基于先进计算架构的高性能空间分析中间件”和“基于新软硬件体系结构的网络地图服务器关键技术研发”的支持下，从理论基础、算法设计、原型验证等多个层次，在数据模型与空间索引、空间查询与空间算子、空间分析等方面，取得了如下的创新性贡献：
提出并实现了适用于互联网地图服务的“两素对应”(即：图片像素与矢量要素对应)空间索引算法。该算法可嵌入在网络地图瓦片的预生成/绘制过程中，以很小的时空代价实现地图瓦片像素与地理要素的关联，克服了传统绘制引擎仅处理地理要素的几何实体而丢失要素属性的缺陷。同时，此做法相比于经典的R树族索引技术，可有效消除重叠区域，提高了WMS(Web Mapping Service)中GetFeatureInfo(获取要素信息)、WFS(Web Feature Service)中Spatial Filter(空间过滤器)等的效率。实验表明，此索引在过滤精度及密集数据的查询效率上整体要优于R树至少22％，适用于网络地图服务中的空间信息检索。
实现了基于栅格技术的空间查询算法。为克服矢量空间关系判断的时间与空间复杂度较高的缺点，提出了栅格空间查询算法实现框架，实现了包括Disjoint/Intersect、Equal、DWithin/Beyond、Touch、Cross、Within/Contain、Overlap、BBOX等十一种空间查询算子/过滤器。此算法基于亚像素精度，较现有成果可以更精确地记录边界栅格的覆盖面积，并根据覆盖面积计算出要素空间关系。同时，索引中关联了要素属性等信息，使得栅格图片具有地理要素的所有特征。利用城市类地理数据集的测试表明，算法的正确率大大高于四色栅格签名(4CRS)，在互联网环境精度可被接受的条件下，空间查询平均性能优于Oracle Spatial约10～15倍。
实现了基于栅格方法的叠加分析算法。针对基于计算几何的图层叠加分析方法的高计算复杂性和低效率的问题，提出了基于栅格的算法实现框架，包括三个算法：基于扫描线的矢量数据栅格化、基于游程表示的图层叠加算法、基于窗口和要素属性的边界追踪。与前人研究成果相比，本算法解决了长度小于栅格场分辨率的游程处理，提出了基于要素属性信息的矢量化过程等，提高了算法对数据的适应性和鲁棒性。利用真实测试数据从交、并、差等操作方面，进行了性能测试(包括内存占用与处理时间等)。在误差允许范围内，本算法实测性能优于业界领先的ArcGIS约一倍。若提前建立索引，则能在占用更少内存的情况下，算法性能相比于ArcGIS10提高两倍以上。此算法适用于以预生成分级地图瓦片作为表现形式的互联网地图服务中的叠加分析并为其他类分析(如：缓冲分析、网络分析等)提供了良好的算法框架和实现参考。
实现了一套栅格体系空间运算算法库。基于C++开发了面向互联网地图服务的空间运算算法库，并实现了包含Flex客户端的完整网络地图服务系统。在相同配置(软硬件配置、并发测试用例)情况下，对于GetFeatureInfo、GetFeature等典型操作，平均响应时间约为ArcGIS Server10的30％。