基于二叉树的几何图形拓扑运算

蔡琪

摘要：该文提出了一种基于二叉树的几何图形拓扑处理算法，实现几何图形间的精确处理。并能有效解决大多数边界问题，同时可以按需求设定不同的精度。

关键词：二叉树；拓扑运算；边界问题

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）34-8191-03

随着Web技术的发展，越来越多的应用被从传统的PC端移植到Web端，用户只需要通过Web浏览器就可以得到所需要的服务。这些Web上的应用不仅方便了用户，也使得自身变得越来越普及。例如百度地图每天的定位请求数就达20亿以上，可见其用户规模。而百度地图这类应用仅仅是WebGis中的一项小功能，而WebGis同样在在城市规划，交通规划提供许多功能支持。

WebGis是Web上的地理信息系统，其功能主要是对空间上采集的地理信息进行分析与处理，例如通过人口统计所得的数据得到的城市人口密度分布图，通过道路车辆统计所得的道路交通流量图。这类信息通常需要通过对采集信息进行精确的拓扑计算得出，例如要计算一个下图红线划定范围内的建筑面积，就需要拿红色区域和A，B，C，D四块区域进行逻辑判断，同时计算相交区域面积。而当前一些开源的拓扑运算库如Dotspatial等，存在着边界问题处理不好，精度值无法确定，效率不高等一些问题。

1 关键技术

1） 多边形的二叉树分割

对平面任意闭合多边形，若指定其包围区域为内侧，则边界与内侧相对的另外一侧为外侧，若要判断内外侧，一般通过多边形的方向进行判断。通常多边形的方向分为顺时针与逆时针，沿多边形方向，一般定义左侧为内侧，右侧为外侧，所以若指定包围的闭合区域为内侧，则多边形为逆时针。如下图，箭头方向指定了逆时针的方向。

定义好了多边形的方向后，我们可以对多边形进行二叉树分割，其算法大致思想是将多边形的边按照多边形方向形成边序列，取出序列中首个边作为二叉树的根节点，将其直线方向作为根节点的方向，再将剩余的边与根节点方向进行拓扑判断，根据剩余边与根节点方向的拓扑关系，如左侧相离，右侧相离，相交，共线等，依次存入根节点的左子节点，右子节点，以及自身的同向列表中。这里采用递归的方式构建树，下面给出相应伪码：

2） 通过二叉树找多边形求交

构建完多边形的二叉树后，我们可通过多边形的二叉树判断一条边是在多边形内部还是外部。这里以下图中边a，b，c为例。将边a与首先树的根节点进行判断，根节点中存的是边1，则a在边1所在直线方向的右侧，将边a再与根节点的右子节点进行判断，右子节点中存储的为边2，a在边2所在直线的左侧，将a与其左子树进行判断，重复该过程直到该节点没有任何子树了，可以看到该节点中存储为边7，由于a在边7左侧，之前已经介绍过逆时针方向的多边形，其内部在其边的方向的左侧，至此可判断a在多边形内。这里边b与边2相交，因此在判断时需要将边b截断，边2左侧的继续和边2的左子树进行判断，边2右侧的继续和边2的右子树进行判断，这里左侧边与之前边a的判断顺序一样，最后判定位于多边形内部，而边2右侧的的与边3进行判断，其位于边3右侧，而边3没有右子树，所以这里判定其为多边形外部，边c的判定与其相仿。

解决了边与多边位置的判断，我们就可以开始进行多边形的求交运算。两个多边形求交本质上就是找到各个多边形在另一个多边内部的边。因此只需要对将一个多边形的所有边与另一个多边形的二叉树进行判断，再将另一多边形重复该操作，这样便可找到所有的公共边。

3） 其他拓扑运算

之前介绍了多边形相交，这里定义多边形P与Q相交为P∩Q。这里再定义多边形取反，这里只需要将多边形的所有边进行取反，也就是将时针方向取反，这里定义多边形P取反为?P。其余多边形的拓扑运算均可用这两种运算表示。

4） 拓扑运算结果的多边形重构

由于实际计算中出现的情况较多，这里就出现的多种典型的歧义性情况作出分析并给出相应的算法。

对于以上出现的一个闭合区域的情况，只需将得到的边按照边的方向连接成环即可。而实际中往往会出现多个闭合区域的情况，如下图。该文给出的方法的是先将得到的边集合进行连通性分析，以结果中的顶点为节点形成无向图，对各个连通区间进行单独处理。

在之前的二叉树计算时，我们将与边重合的情况也列入多边形内部的情况，所以在得到的结果中会出现重合边情况。对于边重合的情况通常有两种，分别为同向边重合与异向边重合。下图给出了两种不同的边重合情况。两种情况的处理方法不同。例如下图a中，两个多边形的边属于同向边重合，在计算时需要将两条重合边合并为一条，再加入到之前的连通图中进行计算，而对于图b中的情况，由于异向边重合时，结果往往就是该边所在的这条线段，所以出现异向边重合时，我们将其所在线段作为结果，并将两条异向重合边从之前的中间结果中剔除。

顶点重合的情况通常分为无邻边重合与有邻边重合。通常无邻边重合出现在多边形仅一点相交的情况，如图a，其处理方式也较为简单，将该顶点作为结果即可。对于有邻边的顶点相交，通常在排除边重合之后需要做一些处理。如图b中两个图形作并操作，则与顶点相邻的有6条边，这里需要确定每条边通过顶点与哪条边相连。

对于这种类型的点重合，确定边成对的关系主要是通过边的方向来确定。如下图，这六条边有3条是指向重合点，3条由顶点指向外部，我们可将这六条边按此规律分为入边与出边。这里有三条入边，指向重合点，另三条出边由顶点出来，其中每条入边对应着一条出边，不会出现其他情况。要找到入边对应的出边，这里通过夹角的方式来判定其对应关系，由于入边左侧对应的是多边形的内部，则按其顺时针方向找到的最小转角的边应为其对应的出边，所以这里的处理方法是选择一条入边，计算其与所有出边的顺时针转角，选择最小转角的出边作为其对应边，然后依次对其余入边进行处理。

经过以上处理后，剩下的边在方向上只有唯一的一条路径，将剩余边按照顺序连接成闭合区域即可。

2 实验结果

本文所介绍的基于二叉树的拓扑运算算法，时间复杂度为nlogn，与当前使用较多的裁剪算法相比，其时间复杂度为n^2，效率得到明显提升，同时本算法对于多种歧义情况均有处理，且在实际应用中效果较好。但由于多边形拓扑运算情况较多，实验中可能会出现未考虑到的情况，将在之后的实验中进行修正。

参考文献：

[1] 潘瑜春，钟耳顺，赵春江.GIS空间数据库的更新技术[J].地球信息科学，2004（1）.

[2] 杜爽，陈成永.以节点操作实现多边形求交的算法[J].测绘通报，2007（10）.

[3] 宋立明，闫浩文，李茜茜，李双元.两个简单多边形求交的算法[J].测绘与空间地理信息，2011（6）.

[4] 樊建华，黄有群，刘嘉敏.带孔洞的多边形求交算法[J].沈阳工业大学学报，2001（5）.

[5] Philip J Schneider，David H Eberly .Geometric tools for computer graphics[C]. 2005.endprint

摘要：该文提出了一种基于二叉树的几何图形拓扑处理算法，实现几何图形间的精确处理。并能有效解决大多数边界问题，同时可以按需求设定不同的精度。

关键词：二叉树；拓扑运算；边界问题

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）34-8191-03

随着Web技术的发展，越来越多的应用被从传统的PC端移植到Web端，用户只需要通过Web浏览器就可以得到所需要的服务。这些Web上的应用不仅方便了用户，也使得自身变得越来越普及。例如百度地图每天的定位请求数就达20亿以上，可见其用户规模。而百度地图这类应用仅仅是WebGis中的一项小功能，而WebGis同样在在城市规划，交通规划提供许多功能支持。

WebGis是Web上的地理信息系统，其功能主要是对空间上采集的地理信息进行分析与处理，例如通过人口统计所得的数据得到的城市人口密度分布图，通过道路车辆统计所得的道路交通流量图。这类信息通常需要通过对采集信息进行精确的拓扑计算得出，例如要计算一个下图红线划定范围内的建筑面积，就需要拿红色区域和A，B，C，D四块区域进行逻辑判断，同时计算相交区域面积。而当前一些开源的拓扑运算库如Dotspatial等，存在着边界问题处理不好，精度值无法确定，效率不高等一些问题。

1 关键技术

1） 多边形的二叉树分割

对平面任意闭合多边形，若指定其包围区域为内侧，则边界与内侧相对的另外一侧为外侧，若要判断内外侧，一般通过多边形的方向进行判断。通常多边形的方向分为顺时针与逆时针，沿多边形方向，一般定义左侧为内侧，右侧为外侧，所以若指定包围的闭合区域为内侧，则多边形为逆时针。如下图，箭头方向指定了逆时针的方向。

定义好了多边形的方向后，我们可以对多边形进行二叉树分割，其算法大致思想是将多边形的边按照多边形方向形成边序列，取出序列中首个边作为二叉树的根节点，将其直线方向作为根节点的方向，再将剩余的边与根节点方向进行拓扑判断，根据剩余边与根节点方向的拓扑关系，如左侧相离，右侧相离，相交，共线等，依次存入根节点的左子节点，右子节点，以及自身的同向列表中。这里采用递归的方式构建树，下面给出相应伪码：

2） 通过二叉树找多边形求交

构建完多边形的二叉树后，我们可通过多边形的二叉树判断一条边是在多边形内部还是外部。这里以下图中边a，b，c为例。将边a与首先树的根节点进行判断，根节点中存的是边1，则a在边1所在直线方向的右侧，将边a再与根节点的右子节点进行判断，右子节点中存储的为边2，a在边2所在直线的左侧，将a与其左子树进行判断，重复该过程直到该节点没有任何子树了，可以看到该节点中存储为边7，由于a在边7左侧，之前已经介绍过逆时针方向的多边形，其内部在其边的方向的左侧，至此可判断a在多边形内。这里边b与边2相交，因此在判断时需要将边b截断，边2左侧的继续和边2的左子树进行判断，边2右侧的继续和边2的右子树进行判断，这里左侧边与之前边a的判断顺序一样，最后判定位于多边形内部，而边2右侧的的与边3进行判断，其位于边3右侧，而边3没有右子树，所以这里判定其为多边形外部，边c的判定与其相仿。

解决了边与多边位置的判断，我们就可以开始进行多边形的求交运算。两个多边形求交本质上就是找到各个多边形在另一个多边内部的边。因此只需要对将一个多边形的所有边与另一个多边形的二叉树进行判断，再将另一多边形重复该操作，这样便可找到所有的公共边。

3） 其他拓扑运算

之前介绍了多边形相交，这里定义多边形P与Q相交为P∩Q。这里再定义多边形取反，这里只需要将多边形的所有边进行取反，也就是将时针方向取反，这里定义多边形P取反为?P。其余多边形的拓扑运算均可用这两种运算表示。

4） 拓扑运算结果的多边形重构

由于实际计算中出现的情况较多，这里就出现的多种典型的歧义性情况作出分析并给出相应的算法。

对于以上出现的一个闭合区域的情况，只需将得到的边按照边的方向连接成环即可。而实际中往往会出现多个闭合区域的情况，如下图。该文给出的方法的是先将得到的边集合进行连通性分析，以结果中的顶点为节点形成无向图，对各个连通区间进行单独处理。

在之前的二叉树计算时，我们将与边重合的情况也列入多边形内部的情况，所以在得到的结果中会出现重合边情况。对于边重合的情况通常有两种，分别为同向边重合与异向边重合。下图给出了两种不同的边重合情况。两种情况的处理方法不同。例如下图a中，两个多边形的边属于同向边重合，在计算时需要将两条重合边合并为一条，再加入到之前的连通图中进行计算，而对于图b中的情况，由于异向边重合时，结果往往就是该边所在的这条线段，所以出现异向边重合时，我们将其所在线段作为结果，并将两条异向重合边从之前的中间结果中剔除。

顶点重合的情况通常分为无邻边重合与有邻边重合。通常无邻边重合出现在多边形仅一点相交的情况，如图a，其处理方式也较为简单，将该顶点作为结果即可。对于有邻边的顶点相交，通常在排除边重合之后需要做一些处理。如图b中两个图形作并操作，则与顶点相邻的有6条边，这里需要确定每条边通过顶点与哪条边相连。

对于这种类型的点重合，确定边成对的关系主要是通过边的方向来确定。如下图，这六条边有3条是指向重合点，3条由顶点指向外部，我们可将这六条边按此规律分为入边与出边。这里有三条入边，指向重合点，另三条出边由顶点出来，其中每条入边对应着一条出边，不会出现其他情况。要找到入边对应的出边，这里通过夹角的方式来判定其对应关系，由于入边左侧对应的是多边形的内部，则按其顺时针方向找到的最小转角的边应为其对应的出边，所以这里的处理方法是选择一条入边，计算其与所有出边的顺时针转角，选择最小转角的出边作为其对应边，然后依次对其余入边进行处理。

经过以上处理后，剩下的边在方向上只有唯一的一条路径，将剩余边按照顺序连接成闭合区域即可。

2 实验结果

本文所介绍的基于二叉树的拓扑运算算法，时间复杂度为nlogn，与当前使用较多的裁剪算法相比，其时间复杂度为n^2，效率得到明显提升，同时本算法对于多种歧义情况均有处理，且在实际应用中效果较好。但由于多边形拓扑运算情况较多，实验中可能会出现未考虑到的情况，将在之后的实验中进行修正。

参考文献：

[1] 潘瑜春，钟耳顺，赵春江.GIS空间数据库的更新技术[J].地球信息科学，2004（1）.

[2] 杜爽，陈成永.以节点操作实现多边形求交的算法[J].测绘通报，2007（10）.

[3] 宋立明，闫浩文，李茜茜，李双元.两个简单多边形求交的算法[J].测绘与空间地理信息，2011（6）.

[4] 樊建华，黄有群，刘嘉敏.带孔洞的多边形求交算法[J].沈阳工业大学学报，2001（5）.

[5] Philip J Schneider，David H Eberly .Geometric tools for computer graphics[C]. 2005.endprint

摘要：该文提出了一种基于二叉树的几何图形拓扑处理算法，实现几何图形间的精确处理。并能有效解决大多数边界问题，同时可以按需求设定不同的精度。

关键词：二叉树；拓扑运算；边界问题

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）34-8191-03

随着Web技术的发展，越来越多的应用被从传统的PC端移植到Web端，用户只需要通过Web浏览器就可以得到所需要的服务。这些Web上的应用不仅方便了用户，也使得自身变得越来越普及。例如百度地图每天的定位请求数就达20亿以上，可见其用户规模。而百度地图这类应用仅仅是WebGis中的一项小功能，而WebGis同样在在城市规划，交通规划提供许多功能支持。

WebGis是Web上的地理信息系统，其功能主要是对空间上采集的地理信息进行分析与处理，例如通过人口统计所得的数据得到的城市人口密度分布图，通过道路车辆统计所得的道路交通流量图。这类信息通常需要通过对采集信息进行精确的拓扑计算得出，例如要计算一个下图红线划定范围内的建筑面积，就需要拿红色区域和A，B，C，D四块区域进行逻辑判断，同时计算相交区域面积。而当前一些开源的拓扑运算库如Dotspatial等，存在着边界问题处理不好，精度值无法确定，效率不高等一些问题。

1 关键技术

1） 多边形的二叉树分割

对平面任意闭合多边形，若指定其包围区域为内侧，则边界与内侧相对的另外一侧为外侧，若要判断内外侧，一般通过多边形的方向进行判断。通常多边形的方向分为顺时针与逆时针，沿多边形方向，一般定义左侧为内侧，右侧为外侧，所以若指定包围的闭合区域为内侧，则多边形为逆时针。如下图，箭头方向指定了逆时针的方向。

定义好了多边形的方向后，我们可以对多边形进行二叉树分割，其算法大致思想是将多边形的边按照多边形方向形成边序列，取出序列中首个边作为二叉树的根节点，将其直线方向作为根节点的方向，再将剩余的边与根节点方向进行拓扑判断，根据剩余边与根节点方向的拓扑关系，如左侧相离，右侧相离，相交，共线等，依次存入根节点的左子节点，右子节点，以及自身的同向列表中。这里采用递归的方式构建树，下面给出相应伪码：

2） 通过二叉树找多边形求交

构建完多边形的二叉树后，我们可通过多边形的二叉树判断一条边是在多边形内部还是外部。这里以下图中边a，b，c为例。将边a与首先树的根节点进行判断，根节点中存的是边1，则a在边1所在直线方向的右侧，将边a再与根节点的右子节点进行判断，右子节点中存储的为边2，a在边2所在直线的左侧，将a与其左子树进行判断，重复该过程直到该节点没有任何子树了，可以看到该节点中存储为边7，由于a在边7左侧，之前已经介绍过逆时针方向的多边形，其内部在其边的方向的左侧，至此可判断a在多边形内。这里边b与边2相交，因此在判断时需要将边b截断，边2左侧的继续和边2的左子树进行判断，边2右侧的继续和边2的右子树进行判断，这里左侧边与之前边a的判断顺序一样，最后判定位于多边形内部，而边2右侧的的与边3进行判断，其位于边3右侧，而边3没有右子树，所以这里判定其为多边形外部，边c的判定与其相仿。

解决了边与多边位置的判断，我们就可以开始进行多边形的求交运算。两个多边形求交本质上就是找到各个多边形在另一个多边内部的边。因此只需要对将一个多边形的所有边与另一个多边形的二叉树进行判断，再将另一多边形重复该操作，这样便可找到所有的公共边。

3） 其他拓扑运算

之前介绍了多边形相交，这里定义多边形P与Q相交为P∩Q。这里再定义多边形取反，这里只需要将多边形的所有边进行取反，也就是将时针方向取反，这里定义多边形P取反为?P。其余多边形的拓扑运算均可用这两种运算表示。

4） 拓扑运算结果的多边形重构

由于实际计算中出现的情况较多，这里就出现的多种典型的歧义性情况作出分析并给出相应的算法。

对于以上出现的一个闭合区域的情况，只需将得到的边按照边的方向连接成环即可。而实际中往往会出现多个闭合区域的情况，如下图。该文给出的方法的是先将得到的边集合进行连通性分析，以结果中的顶点为节点形成无向图，对各个连通区间进行单独处理。

在之前的二叉树计算时，我们将与边重合的情况也列入多边形内部的情况，所以在得到的结果中会出现重合边情况。对于边重合的情况通常有两种，分别为同向边重合与异向边重合。下图给出了两种不同的边重合情况。两种情况的处理方法不同。例如下图a中，两个多边形的边属于同向边重合，在计算时需要将两条重合边合并为一条，再加入到之前的连通图中进行计算，而对于图b中的情况，由于异向边重合时，结果往往就是该边所在的这条线段，所以出现异向边重合时，我们将其所在线段作为结果，并将两条异向重合边从之前的中间结果中剔除。

顶点重合的情况通常分为无邻边重合与有邻边重合。通常无邻边重合出现在多边形仅一点相交的情况，如图a，其处理方式也较为简单，将该顶点作为结果即可。对于有邻边的顶点相交，通常在排除边重合之后需要做一些处理。如图b中两个图形作并操作，则与顶点相邻的有6条边，这里需要确定每条边通过顶点与哪条边相连。

对于这种类型的点重合，确定边成对的关系主要是通过边的方向来确定。如下图，这六条边有3条是指向重合点，3条由顶点指向外部，我们可将这六条边按此规律分为入边与出边。这里有三条入边，指向重合点，另三条出边由顶点出来，其中每条入边对应着一条出边，不会出现其他情况。要找到入边对应的出边，这里通过夹角的方式来判定其对应关系，由于入边左侧对应的是多边形的内部，则按其顺时针方向找到的最小转角的边应为其对应的出边，所以这里的处理方法是选择一条入边，计算其与所有出边的顺时针转角，选择最小转角的出边作为其对应边，然后依次对其余入边进行处理。

经过以上处理后，剩下的边在方向上只有唯一的一条路径，将剩余边按照顺序连接成闭合区域即可。

2 实验结果

本文所介绍的基于二叉树的拓扑运算算法，时间复杂度为nlogn，与当前使用较多的裁剪算法相比，其时间复杂度为n^2，效率得到明显提升，同时本算法对于多种歧义情况均有处理，且在实际应用中效果较好。但由于多边形拓扑运算情况较多，实验中可能会出现未考虑到的情况，将在之后的实验中进行修正。

参考文献：

[1] 潘瑜春，钟耳顺，赵春江.GIS空间数据库的更新技术[J].地球信息科学，2004（1）.

[2] 杜爽，陈成永.以节点操作实现多边形求交的算法[J].测绘通报，2007（10）.

[3] 宋立明，闫浩文，李茜茜，李双元.两个简单多边形求交的算法[J].测绘与空间地理信息，2011（6）.

[4] 樊建华，黄有群，刘嘉敏.带孔洞的多边形求交算法[J].沈阳工业大学学报，2001（5）.

[5] Philip J Schneider，David H Eberly .Geometric tools for computer graphics[C]. 2005.endprint