几何代数GIS计算模型

第1章绪论 现有GIS以几何学、地图学和计算机图形学为理论和方法支撑，形成了 “以 地图模型为核心、以欧氏与计算几何为基础、以空间数据管理与分析为目标”的 研究模式。难以避免由于欧氏几何运算的坐标相关性、多维不统一性等特性所导 致的计算结构复杂、语义不清晰以及动态计算困难等问题。同时，基于欧氏几何 的空间计算更侧重对几何形态的描述和表达，而对度量、拓扑、关系、语义等特 征信息的表达与计算集成不足。使得很难定义完备的空间计算算子，实现对空间 计算的统一表达与运算。而由之带来的数据模型、数据结构、数据存储与管理方 式以及空间索引机制等方面的复杂性，导致了空间计算拓展困难。从空间计算的 数学基础进行创新，是改进和完善空间计算方法的有效途径。 1.1地理信息计算方法的发展与需求 随着物联网及大数据时代的到来，对海量、动态、非结构化的多源空间数据 的分析已成为当今及未来GIS发展的核心功能。大数据已经成为可以与物质资产 和人力资本相提并论的重要生产要素，传统的以数据为核心的“管理型GIS”软 件已趋于成熟，迫切需要发展以空间多要素分析与服务为核心，可有效支撑海量 数据分析与过程模拟的“分析型GIS”。“分析型GIS”的发展代表地理信息研究 范式从经验和实证向系统综合和大数据挖掘转变，并呈现从空间格局到时空过程、 从现象描述到机理建模与模拟、从部门与区域研究向多尺度综合集成研究的发展 趋向。然而现有GIS对地理语义、多尺度时空演化过程和要素相互作用的集成表 达不够，迫切需要发展“以地理场景为基础、以时空融合为特征、以地理分析和 模型集成为目标”的地理信息计算模式，从而能够对现实世界离散和连续、具象 与抽象、几何与代数等多重表达进行融合集成，支撑地理信息的结构化、并行化 处理与分析，实现多尺度地理场景及地理规律的表达、建模与综合分析。 1.1.1地理空间和要素表达的完备化 全球性、大尺度地学综合研究的兴起，以及地理现象与地理过程内在的时空 多尺度特征，使得地理空间表达需要同时使用笛卡儿、球面等不同坐标系统。GIS 研究对象也从笛卡儿坐标系下相对简单的基本几何对象类型，逐渐发展为涉及多个坐标系统以及包含流形、非流形等不同形式、不同类型的复杂地理对象。GIS 对地理空间的表达应能真实反映现实世界，实现复杂地理对象及连续地理现象一 体化表达、建模与分析。然而，从几何视角出发的基于点、线、面、体、像素（pixel）、 体元（voxel）等基本几何对象的现实地理世界表达本质上是基于离散化表达与描 述思路的数据模型构建方法，难以同时兼顾连续与离散对象的统一表达与描述。 传统基于欧氏几何框架的空间数据表达，对不同维度、不同坐标系统下地理对象 和现象的表达与运算缺乏统一性，不仅增加了数据模型、分析算法及系统架构的 复杂度，也难以支撑复杂空间分析及地理模型的运算需求。 地理问题的描述、分析与求解要求能够表达真实的地理环境，需要对所涉及 的相关要素与内涵进行综合考虑与分析，进而要求对几何、时间、语义、关系及 属性特征的整体表达，从而有效支撑复杂地理实体的分析和运算。现有GIS空间 表达多侧重几何表达，属性、语义、时空关系等信息未能在数据模型层次上加以 表达，而是在数据组织层面将其以元件、属性表等结构通过ID关联，其时空关 系、语义信息等往往需要经过相对复杂的计算和推理后求得。 基于上述分析，如图1.1所示，需要集成不同空间（欧氏、射影、球面等）、 统一不同坐标参考（投影坐标系统、时空参考系统、空间直角坐标系），实现平面/球面、连续/离散、绝对/相对的一体化表达。在表达要素上，需要从空间+属性+ 时间的地图学视角地理信息表达扩展为包含地理语义、时空定位、几何形态、演 化过程、要素关系和属性特征的地理学视角地理信息表达。 1.1.2 GIS算法维度统一性和通用性 随着空间对象的多样性和空间关系的复杂性的不断攀升，以欧氏几何和计算 几何为基础的GIS空间计算高度依赖坐标系统，其运算和表达缺乏参数化和自适 应特征，难以实现不同维度、不同坐标系统下地理对象的统一计算。多维表达和 运算的不统一性使得对复杂地理对象及过程的分析与运算在流程和结构上具有 “定制”特性，在数学基础上对多维统一计算的支撑能力弱，使得大部分算法难以 直接实现维度拓展，部分可支撑高维计算的算法又往往需要进行大量繁杂的解析 和重构工作，限制了现有GIS对大规模海量数据的建模、表达与分析能力。 由于不同数据模型底层数学理论基础不同，不同的应用需求往往需要通过复 杂的坐标变换、对象剖分与函数逼近以及具有较高计算复杂度的算法加以实现， 在多维对象表达、存储以及拓扑关系维护上也缺乏统一性，使得难以定义有限且 完备的分析算子，并难以构建相对统一的算法框架，这既削弱了 GIS对地理问题 的表达与分析能力，又增加了 GIS体系的复杂度。 如图1.2所示，理想的地理信息计算需要构建统一的数据表达与算子计算方 法，实现面向目标的逻辑描述和形式化的GIS问题求解，并可根据不同计算环境 及软硬件约束自动生成算法，进行代码优化与并行化。 1.1.3 GIS算法并行计算能力的提升 并行计算是有效提升大规模GIS空间分析效率，实现对海量数据和复杂场景 分析的重要途径。传统基于几何视角的现实地理世界数据模型构建方法，本质上 是基于离散化点、线、面、体、像素、体元等的表达与描述思路。GIS的“点-线-面”数据结构及其关系代数存储模型已基本解决了空间位置、几何形态和属性 特征的一体化组织与管理问题。但由于空间对象的多样性和空间关系的复杂性的 快速增加，并且以计算几何和欧氏几何为基础的GIS空间计算十分依赖其坐标系 统，其表达和运算缺少参数化和自适应特征，所以基于以上的空间分析算法需要 对不同维度对象的分析分别加以考虑，且其运算与对象类型、对象坐标以及运算 流程均高度相关，使得基于其上的分布式并行算法往往存在结构复杂、算法实现 不易和性能调优困难等问题，难以实现对并行计算的全面支撑，更难实现在复杂 动态环境下实时、动态调整并行策略，进行并行计算代码的自动生成。以上问题 同样由于不同地理数据模型底层数学理论基础的不一致，从而难以实现有限且完 备的分析算子定义，导致难以构建相对统一的算法框架。因此寻找具有对象自适 应性和流程无关性，并具有明确的几何语义，易于实现结构化解析与动态绑定的 新型空间GIS并行化计算方法是解决现有GIS运算效率问题的新途径。 1.2 GIS计算模型及研究进展 目前GIS计算模型并没有一个统一的定义，现有研究更多侧重于GIS数据模 型和表达模型的构建，计算则隐含于数据模型设计过程中，或者通过GIS软件系 统架构间接表达，上述过程更多的是关注计算机实现细节，对计算方法、计算模 式的理论总结较为匮乏。本书将GIS计算模型定义为解决GIS分析问题的通用模 式和计算方法，计算模型一般建立在统一的GIS数据表达基础上，具有可扩展性， 并以模板的方式实现GIS计算。 1.2.1 GIS运算空间构建研究 GIS运算空间包含基本对象表达和对象运算两方面。受现实地理世界变化的 复杂性和综合性的制约，地理信息的表达模式多样、表达方法不统一，极大地影 响了 GIS分析和应用的效率，亟须发展地理数据的统一表达方法。地理信息领域 长期关注地理要素在语义、位置、几何、属性、空间关系等方面的抽象与表达， 从二维/三维表达方法逐渐发展到时空数据模型的构建（Molenaar，1990； Egenhofer and Franzosa， 1991； Nicolas and Renato， 1991；李德仁和李清泉，1997；陈军和郭薇，1998;龚建雅，1997;李清泉和李德仁，1998;吴立新等，2007； Goodchlld et al.，2007;周成虎，2015）。这些数据表达方法及其相应的组织存储方法，在GIS运算空间构建中扮演了基础地理数据组织和交换的作用（康栋贺等，2017; Wang et al.，2020）。早在20世纪，就有部分学者致力于统一的地理时空数据表达 方法的构建，如Tomlin（1988）提出了地图代数方法，期望以代数式的方式来组织 管理地图数据（主要为栅格数据），虽然此后针对矢量数据做出了一系列的改进 （Camara，2005; Li and Hodgson，2004），但由于其底层数学基础仍然是场模型， 限制了其进一步的推广应用；也有学者提出了矢栅一体化模型（Winter and Frank， 2000）、面向对象的模型（Cova and Goodchild，2002）、地理本体模型（Galton，2003） 及地理原子模型（Goodchild，2011）以实现矢量、栅格数据的一体化表达，此外也 有面向地理学“大数据”进行各种地理信息的融合表达研究（吴志峰等，2015; Pei et al.，2020），然而，由于缺乏数学基础层面的统一，这些模型主要用于实现 地理数据的形式化描述；随着面向对象技术的成熟，有学者提出利用类和泛型实 现相关专题数据的统一组织与分析（Manola and Dayal，1986），但该类方法往往需 要根据应用领域精心设计基类及其派生过程，在通用性和普适性上仍有待发展。 在对空间中对象运算的支撑方面，现有空间对象表达研究的核心主要是解决 海量时空数据的压缩存储、快速提取、可视化表达与远程调度等问题。例如，为 应对全球海量数据存储而提出的四叉树结构（Samet，1984; Fekete，1990; Ottoson and Hauska，2002）和多层次空间数据模型等（Goodchild，2008），而瓦片编码技术 在全球多尺度空间数据存储（陈静等，2011），特别是多尺度数据调度与数据服务 方面也发挥着重要作用。近年来，一批学者认识到现有数据的组织与管理方式不 利于进行球面空间的表达，也难以支撑地理模式的计算，因此球面离散格网拓分 的方法成为海量数据管理的研究热点，例如球面六边形格网系统（贲进等，2010）， 基于复平面的正二十面体格网编码方案（Zheng，2007），兼容三角形、四边形、 六边形格网的复合菱形离散格网系统（Lin et al.，2018）等。但以上结构只是通过 数据结构的设计实现对空间计算的间接支持，未能构建一套统一的求解方案，不 利于GIS计算模型的构建。 1.2.2空间对象的计算模式研究 近年来，面向多维、海量、动态数据的空间计算研究日渐增多（Tao et al.， 2007），空间计算成为 GIS 分析的核心内容（Mouratidis and Mamoulis， 2010; Gao et al.，2010）。研究内容覆盖空间关系描述方法、空间关系认知、时空推理、空间 知识表达和处理等方面。基于空间计算的检索、形式化表达及推理研究也日渐成 为空间分析的核心内容。其中空间关系的计算是空间计算的基础，也是矢量空间计算的核心内容之一。早期的空间计算研究多针对单一空间关系类型开展，包含 不同维度空间、不同数据类型间的空间关系计算、空间关系计算不确定性问题及 实时动态计算等方面（李青元，1997；赵仁亮，2002；张锦明，2003；周秋生等， 2005；谢顺平等，2010）。综合考虑距离、拓扑和方向这三种基本空间关系建立集 成化的模型日渐成为现有空间关系分析的主流趋势（邓敏等，2009，2010；何建华 等，2008；陈娟等，2010；刘新等，2010；沈敬伟等，2011）。此外包括地理语义 的空间关系查询和推理（杜冲等，2010；邓敏等，2011），针对大尺度空间关系计 算的研究（陈军等，2007；侯妙乐等，2012）也逐渐兴起。随着空间关系计算的复 杂性不断提高，一些学者转向思考空间关系计算中的不确定性研究（杜晓初和黄茂 军，2007），并发展出空间对象间的模糊拓