(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210355627.3 (22)申请日 2022.04.06 (71)申请人 南京师范大学 地址 210024 江苏省南京市 鼓楼区宁海路 122号 (72)发明人 陈康正　吴明光　 (74)专利代理 机构 南京苏高专利商标事务所 (普通合伙) 32204 专利代理师 柏尚春 (51)Int.Cl. G06F 30/13(2020.01) G06F 30/20(2020.01) G06F 17/16(2006.01) (54)发明名称 基于V-TMM计算建筑物与绿地拓扑关系的方 法 (57)摘要 本发明公开了一种基于V ‑TMM计算建筑物与 绿地拓扑关系的方法， 包括面要素的梯形网格构 建、 点‑梯形格网判定、 拓扑关系模型定义、 采用 V‑TMM计算多边形拓扑关系等四个技术环节。 以 水平扫描线将面几何对象剖分为梯形面片， 构建 梯形连通图； 针对梯形面片行列号和横纵坐标区 间唯一性， 定义了点 ‑梯形格网判定； 给出了面几 何对象拓扑关系的形式化定义， 建立了顶点 ‑梯 形格网模型(V ‑TMM)； 设计了基于V ‑TMM的多边形 拓扑关系计算流程。 本发明可以实现面要素拓扑 关系的高效计算。 权利要求书1页 说明书7页 附图3页 CN 114756932 A 2022.07.15 CN 114756932 A 1.一种基于V ‑TMM计算建筑物与绿地拓扑关系的方法， 其特 征在于， 包括如下步骤： 步骤1， 面要素的水平扫描 线剖分， 构建梯形格网； 步骤2， 点 ‑梯形格网判定； 步骤3， 面几何对象拓扑关系的形式化定义， 建立顶点 ‑梯形格网模型(V ‑TMM)； 步骤4， 基于V ‑TMM计算建筑物与绿地的拓扑关系， 检测是否存在违规建筑用地。 2.根据权利要求1所述的基于V ‑TMM计算建筑物与绿地拓扑关系的方法， 其特征在于， 所述步骤1具体包括： (1)将面要素几何化为多边形， 从多边形的每个顶点做水平扫描线与多边形边形成交 点， 每两条相 邻扫描线构成一个扫描 行， 匹配扫描 行之间的交点与多边形顶点， 得到相交边 集合； (2)位于同一扫描行的相交边自左向右两两配对， 组成梯形面片， 根据梯形面片之间的 邻接关系和邻接个数， 区分梯形面片中的骨干梯形和细节梯形； (3)寻找梯形链头， 或是位于多边形顶部的三角形， 或是跟在骨干梯形下方的细节梯 形； 由每个梯形链头出发， 逐个梯形面片向下遍历， 直到遇到第一个骨干梯形停止， 构建梯 形链； 所有梯形链构建完成后， 组合成梯形 连通图； (4)经过步骤(1)、 (2)和(3)后得到一个代表多边形的梯形连通图； 梯形面片是组成多 边形的基本单元， 而梯形连通图是梯形面片集合经过分类规整之后， 一种高级、 完备的多边 形剖分形式， 面向各种基于梯形格网数据结构的计算、 分析、 可视化需求。 3.根据权利要求2所述的一种基于V ‑TMM计算建筑物与绿地拓扑关系的方法， 其特征在 于， 所述步骤2具体包括： (1)在步骤1构建的梯形连通 图中， 对于待判定点逐个遍历梯形链， 判定该点是否落在 当前梯形链内； (2)判定点是否位于梯形链的首尾梯形之间， 若是则定位点所在的细节梯形行， 否则点 在多边形外； (3)判定点是否位于该细节梯形行的某个细节梯形中， 若是则点在多边形内， 否则点在 多边形外； (4)经过步骤(1)、 (2)和(3)后判定点是否在多边形剖分而成的梯形格网内， 即点是否 在多边形内， 该判定称为 点‑梯形格网判定 。 4.根据权利要求3所述的一种基于V ‑TMM计算建筑物与绿地拓扑关系的方法， 其特征在 于， 所述步骤3具体包括： 对于拓扑关系待计算的两个多边形A、 B， 构建两者的梯形连通图， 利用点‑梯形格网判定， 得到多边形B的顶 点在多边形A中的个数， 根据该个数将八种基本拓 扑关系分为三大类， 再结合每一大类拓扑关系对应的辅助判定， 形成确定性的拓扑关系矩 阵， 该拓扑关系模型成为顶点 ‑梯形格网模型(V ‑TMM)。 5.根据权利要求4所述的一种基于V ‑TMM计算建筑物与绿地拓扑关系的方法， 其特征在 于， 所述步骤4具体包括： 输入建筑物与绿地的坐标数据， 将 两者几何化为多边形； 通过步骤 1的水平线扫描剖分后， 用梯形连通图来表示任意建筑物或绿地， 进而获取一个建筑物A的 顶点集合PA， 通过步骤2得到PA在一个绿地B中的点个数， 代 入步骤3定义的拓扑关系矩阵， 根 据矩阵取值， 计算建筑物与绿地的拓扑关系， 完成是否存在建筑占用绿地的违规情况检测。权　利　要　求　书 1/1 页 2 CN 114756932 A 2基于V‑TMM计算建筑物 与绿地拓扑关系 的方法 技术领域 [0001]本发明涉及地理信息系统(GIS)、 计算机辅助设计(CAD)、 计算机地图制图(CAC)， 导航地图、 电子地图等领域， 特别涉及一种基于V ‑TMM计算建筑物与绿地拓扑关系的方法。 背景技术 [0002]拓扑关系GIS中最基本和最重要的空间关系， 在GIS空间推理与应用中具有重要地 位。 近年来拓扑关系概念模 型得到了深入的研究， 包括N ‑交集模型、 RCC模 型、 2DString模 型 等。 尽管拓扑关系形式化表达方面的研究颇多， 但鲜有拓扑关系计算方法的研究进展。 与拓 扑关系概念 模型相结合的计算 算法， 以及算法的效率和稳定性 等方面的研究相对缺乏。 [0003]当前针对拓扑关系计算的方法包括解析几何算法、 平面图(Planar  graph)算法及 平面扫描(Plane  sweep)转换方法等。 解析几何方法通过建立直线的参数方程， 通过解算 点‑线段、 线段 ‑线段、 线段 ‑面等的位置关系来实现空间目标的拓扑关系判断。 解析几何算 法往往具有较高的运行效率且容易和度量、 方位等空间关系进行综合计算， 但是难以和4/ 9‑交集模型等拓扑概念模 型集成进而计算复杂的拓扑谓词。 平面图方法通过相交等几何关 系预处理， 将点、 线和面等几何对 象转换为平面图， 将图中的节点、 边标记为几何目标的内 部(interior)、 边界(bou ndary)和外部(exterior)， 将面标记为边的左、 右。 然后利用4/9交 集模型及其扩展(如维度模型)， 来求解出复杂拓扑谓词。 但是平面图方法在将几何对象转 换为平面图时， 涉及大量求交运算， 计算效率不高， 且转换过程中丢失了距离、 方位等信息， 难以进行混合的空间关系计算。 扫描转换方法将2维的拓扑关系计算转换为0维的像素点， 或者1维的扫描线、 或者二维的多边形来进行计算。 转换后能够显著降低算法复杂度， 可以 获得较高的计算效率。 但是， 这类算法往往针对某类对象之间的拓扑关系计算而提出。 尚没 有形成一个通用的拓扑关系高效计算方法。 [0004]为解决上述问题， 需要一种新的方法， 能够实现GIS拓扑关系的快速计算。 名称为 “一种区域用水网络拓扑关系确认方法、 装置和系统 ”， 申请号CN201910145895.0， 公开号为 CN111626460A的中国专利， 本发明涉及供水系统内用水网络拓扑关系技术领域， 提供了一 种区域用水网络拓扑关系确认方法、 装置和系统。 其中方法包括确定潜在会发生用水网络 拓扑关系归属错误的一个或者多个区域； 获取对应所述一个或者多个区域内所包含的各流 量计量装置的水流量数据； 根据所述水流量数据， 确认所述一个或者多个区域， 处于用水网 络拓扑关系归属错误状态的一个或者多个流量计量装置。 本发明提出了一种确定潜在 会发 生用水网络拓扑关系归属错误的一个或者多个区域， 并通过水流量数据确定出所述一个或 者多个区域中， 处于用水网络拓扑关系归属错误状态的一个或者多个流量计量装置的概 率， 从而极大程度上节约了实地考察的工作人员人力成本， 还提高了排查的效率。 名称为 “一种基于空间位置的拓扑关系获取方法、 装置和存储介质 ”， 申请号为CN202110253348.1， 公开号为CN112632399A的中国专利， 公开了一种基于空间位置的拓扑关系获取方法、 装置 和存储介质， 其中方法包括： 获取目标对象 的WGS84历史坐标点数据， 并利用WGS84历史坐标 点数据， 生成Web墨卡托坐标系下的真实地理投影坐标面； 获取 目标对象的WGS84实时坐标说　明　书 1/7 页 3 CN 114756932 A 3