主流的GIS应用与spatial database 均采用了对象模型，一个空间要素包含几何与属性两部分，并不保存对象之间的拓扑关系。基于种种考虑，拓扑模型已经不常用，拓扑关系的生成转变为由实时计算生成。拓扑关系计算的核心是9交叉模型，本文的主要目的是揭示对象模型（以多边形为例）到拓扑模型的关联过程。并且结合 geos与ArcGIS中相应的内容予以说明。
1）对象模型对多边形的表达
多边形在对象模型中的表达通常为由有序坐标串构成的一个闭合外环(Exterior Ring)与0个或者多个有序坐标串构成的闭合内环（Inner Rings）。外环可能构成顺时针或者逆时针顺序。所有的系统都会指定一种外环的顺序，而不会允许顺逆时针同时存在。因为环的时针顺序担负着区别面的内部(Interior)与外部(Exterior)的任务。系统会规定环的左侧(针对逆时针)或者右侧(针对顺时针)为面的内部。对应的，内环的顺序与外环恰好相反，因为这样符合关于环的那一侧是内部/外部的统一规定。
在CGAL、Geos、MIF、GDAL等大多数库和数据格式中，规定多边形的外环为逆时针顺序，不过ArcGIS家族比较特殊，将外环规定为顺时针顺序。在进行地理信息数据交换时，这些规定格外重要。
2)Simple Polygon
既然规定了沿着环的一侧圈定面的内部，那么“简单”多边形就要保证其边不能存在自相交的情况。Simple Polygon 在学术界也被称为 Jordan Polygon ,因为Jordan 曲线原理可以证明平面上封闭的曲线可以将平面划分为两个互不连通的区域。虽然没有特殊说明，但是很多算法均要求参与运算的多边形为简单多边形。
1.point in Polygon: 按照从点出发的一条射线与多边形的边交点的个数判断点是否在多边形内的算法称之为射线法(Ray Casting Algorithm)。如果点在多边形内部，则交点个数为基数个，反之为偶数个。但是如果输入的多边形存在自相交叠的情况，那么上述条件不能满足。比如下面的五角星。
2.多边形布尔运算(overlay)
因为拓扑关系建立的核心在于9交叉模型，因此对于输入对象的内部、外部、边界的确认非常的严格。前文说道，外环、内环的顺序担负着标识面/多边形内部的重要责任，所以叠置型空间分析的输入要求为简单多边形。
因此ArcGIS开发了“验证与修复几何数据”方法，并且将其作为叠置分析的准备步骤。其中以下检查项与外部、内部的建立有关系：
- Incorrect Ring Ording: 不正确的环走向。
- SelfIntersections:自相交
以上错误发生时，会造成叠置分析的失败或者结果错误。
CGAL中使用CGAL::is_simple_2 函数判断多边形是否为简单多边形。
3) 对象模型到拓扑模型的关联：Label方法
叠置分析的输入是对象模型数据，转换为拓扑模型数据并且计算出拓扑关系后，需要对应到对象模型上。需要解决的问题是，怎样建立对象模型与拓扑模型之间的关联呢？我们可以看一下geos的解决方案。
我们知道，拓扑模型在本质上是一种基于图的数据结构，geos中的拓扑模型称为geomgraph,对象模型是我们熟知的geometry。geometry与geomgraph之间的关联是通过Label geos::geomgraph::Label 实现的。在拓扑模型中，节点与弧段是主要的组成部分。在geos中，node与edge 称为GraphComponent。Label是GraphComponent的成员对象。一个GraphComponent拥有一个Label对象。
Label对象的作用是标记Geometry的内部、外部、边界是否在 GraphComponent的 左边、右边、还是上面。每一个Geometry 对应一个 TopologyLocation geos::geom::TopologyLocation 。 因为geos是针对二元对象设计的算法库，因此geos中一个label对应两个TopologyLocation。如果要实现大规模叠置分析算法，可以将TopologyLocation扩展到多个。
TopologyLocation的结构是：
Edge/Node 的 [上面(ON)/左侧(LEFT)/右侧(RIGHT)] = Geometry 的 [内部(INTERIOR)/外部(EXTERIOR)/边界(BOUNDARY)]
geos中，TopologyLocation 通过数据成员 std::vector<int> location 表达 ON,LEFT,RIGHT三个位置对应Geometry的 BOUNDARY,INTERIOR或者EXTERIOR。
- 对于线对象或者点对象,对照9交叉模型，可以知道 geograph[ON] = INTERIOR;其余LEFT,RIGHT均为 EXTERIOR。
- 对于面对象，可以知道geograph[ON] = BOUNDARY,而LEFT,RIGHT 对应INTERIOR还是EXTERIOR则要看 edge的方向。
通过TopologyLocation，geomgraph与geometry的关系被关联起来了。
总结一下，对象模型与拓扑模型的关联是拓扑关系建立的一个重要的步骤，在这个步骤，对象的内部、外部、边界信息输入到拓扑模型，并且在之后的9交叉模型的建立中起到关键作用。下一节，我会分享九交叉模型的构建算法。
GEOS 通过Label-TopologyLocation关联拓扑模型与对象模型的设计，是一种非常有效的方法，我见过的一些拓扑与对象的关联方法，有一部分是通过牺牲效率，通过计算实现的；另外一些则是通过用标识点标记面等其他方式实现(这种方式会导致上层业务应用产生一些用户不必要进行的令人费解的操作)。geos的这种实现应该是一些优秀的空间计算/GIS软件的通用方案(尽管ArcGIS的TopogyEngine并没有暴露关于Overlay实现的细节)。
参考材料