刘金奎 罗银辉

摘 要：无人机飞行区域电子围栏规划中的核心问题在于解决无人机所申请飞行区域与禁飞区的冲突，而无人机飞行区域的冲突归根结底在于所申请飞行区域与禁飞区拓扑关系的判断。为了能够有效判断飞行区域之间的拓扑关系，提出一种无人机飞行区域拓扑关系判断方法：基于点集拓扑理论，利用九交模型（9IM）对无人机飞行区域拓扑关系进行重新划分和描述；提出解决无人机电子围栏飞行区域拓扑关系判断的算法流程以及计算实现方法；最后，利用VC++设计飞行区域拓扑关系判断实验。结果表明，该方法能够快速、有效判断出相关拓扑关系。

关键词：无人机；拓扑关系；九交模型；飞行区域冲突

DOI：10.11907/rjdk.172789

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）004-0054-04

Abstract：The core issue in UAV flight area electronic fence planning is to solve conflict between the UAV application area and the no-fly zone.While the conflict of the UAV flight area lies in the analysis of the topological relation between the applied flight area and the no-fly zone.In order to effectively determine the topological relationship between flight regions，the paper presents a method of determining topological relation of UAV flight area： Based on the theory of point set topology， the q intersection model （9IM） is used to re-divide and describe the topological relation of UAV flight area.The algorithm flow and the method of calculating the topology relation of the UAV electronic fence flight area are proposed.Finally， the validity of the method is verified by using VC ++ to design the flight area topological relation. The result shows that this method can quickly and effectively judge the topological relation.

Key Words：UAV； topological relations； 9IM； flight area conflict

0 引言

民用無人机发展带来了民用无人机市场的繁荣，同时也由于管理的无序性使得“黑飞”问题频频出现[1]。无人机实名制以及无人机飞行计划申请是根除“黑飞”问题的重要手段。随着电子围栏技术的发展与成熟，其在无人机飞行区域规划中的应用能够有效解决无人机离地飞行计划申请。而无人机飞行区域电子围栏规划中最主要的难点在于解决无人机飞行区域电子围栏申请过程中出现的申请区域电子围栏冲突问题。由于无人机的飞行高度有严格限制，所以其电子围栏区域为特殊的三维区域，即底面为多边形柱体。申请区域电子围栏冲突问题研究实际可以转化为无人机飞行区域的空间拓扑关系判断问题研究。此外，由于无人机的飞行区域存在安全余度考量，因此本文研究的无人机飞行区域拓扑关系与九交模型（9IM）描述的拓扑关系不同，需要对无人机飞行区域拓扑关系描述进行研究。

对于拓扑关系的描述，目前最主要的有基于逻辑的公理化拓扑理论和传统数学拓扑两种方法，其中应用最多的是RCC（区域连接演算）形式化模型和4/9交模型。此外，还有很多学者提出的改进方法。例如，赵仁量等[2]利用空间实体的Voronoi区域替代空间实体外部，改进了9交模型，提出了基于Voronoi图的新9交模型（V9I）。在拓扑关系计算方面：陈军等[3]提出线目标间复杂拓扑关系的分解-组合计算思路，计算线目标之间的拓扑关系；邓念东等[4]采用GTP作为描述空间目标的体元，通过描述体元之间的关系，进而表达空间目标之间的拓扑关系；赵红超[5]以扩展的BMN交点算法为支撑，利用模板元编程的特性，设计并实现了点、线、面之间的拓扑关系的判断；倪建华[6]针对空间拓扑关系类型区分不够详细和算法描述薄弱等问题，对点、线、面目标之间拓扑关系的描述和计算进行了研究；ArcGIS在组件ArcObjects的 IRelationalOperator接口中实现了7种拓扑关系，分别为相等、包含、被包含、相离、重叠、相接和相交[7]；Oracle公司提供了Oracle Spatial插件，并在Oracle中提供SDO_RELATE等函数查询目标间的拓扑关系。Oracle描述的拓扑关系类型分别为相离、相接、重叠-边界相交、重叠-边界相离、相等、包含、被包含、覆盖、位于和任意相交。

综上所述，九交模型（9IM）广泛应用于拓扑关系的描述，能够区分较多的拓扑关系。对于无人机飞行区域而言，传统9IM所描述的某些拓扑关系类型并不需要确定区分。为了能够更加快速、简洁地判断申请的无人机飞行区域与禁飞区是否存在冲突，本文对无人机飞行区域间拓扑关系进行重新描述并对拓扑关系计算算法进行研究。

1 无人机飞行区域拓扑关系描述

空间关系主要包括拓扑关系、顺序关系和度量关系。其中，拓扑关系是最为基础和重要的空间关系。其计算建立在对空间目标拓扑关系合理的描述上，适合空间目标实际情况的拓扑关系描述能够大大提高拓扑关系计算效率。本文研究对象是无人机飞行区域，在现实中不需要对9IM中所描述的邻接、相等、覆盖和反覆盖进行准确区分，因为在计算两个区域边界存在相切时有很多情况需要考虑，这会大大增加计算量。只需要判断两个区域的边界是否存在交集，只要交集不为空就可以把两个区域的拓扑关系认定为交叠。根据对九交模型（9IM）所描述的二维空间对象拓扑关系的分析以及无人机飞行区域拓扑关系的特殊性，对无人机飞行区域拓扑关系进行重新归纳和描述。无人机飞行区域拓扑关系可以归纳为以下4种：第一，相离，即区域a的所有边界点都在区域b之外，同时区域b的所有边界点都在区域a之外；第二，包含，即区域a的所有边界点全在区域b的内部；第三，反包含，即区域b所有的边界点全在区域a的内部；第四，交叠，即区域a与区域b的边界存在交点（边界交集不为空）。

如果空间目标a和b的内部、边界和外部分别用a°、a、a-和b°、b、b-表示，则9IM的表现形式如式（1）所示[8]。交集之间可能的取值为{*，1，0}，其中，“*”表示不关心交集的值；“0”表示交集为空；“1”表示交集不为空。

根据无人机飞行区域的特殊性，将无人机飞行区域的拓扑关系归纳描述为4种拓扑关系：{Disjoint，Contains，Contained-by，Cross}。图1给出了无人机飞行区域的4种拓扑关系，并给出了相应的9IM矩阵表现形式。

2 无人机飞行区域拓扑关系计算

2.1 无人机飞行区域拓扑关系判断流程

在上述判断流程中涉及到折线与面位置关系的判断、直线与面位置关系的判断、点是否在面内的判断、点是否在线上的判断和两条直线是否相交的判断。以下分别对所涉及的判断算法进行分析。

折线与面位置关系的判断：折线与面位置关系可以划分为折线与面相交、折线与面相离和折线在面内部3种关系[9]。在进行位置关系判断时，如果折线中每一条直线都在面的内部，则折线在面的内部；如果折线中有任一条直线与面相交，则折线与面相交；如果折线中所有直线都在面的外部，则折线与面相离。

直线与面位置关系的判断：直线与面位置关系可以划分为直线与面相交、直线与面相离和直线在面内部3种关系[10]。在进行位置关系判断时，如果直线的两个端点都在面的内部，则直线在面内部；如果直线的两个端点分别在面的不同部分，则直线与面相交；如果直线的两个端点都在面外部，且直线与面边界的任一直线段都不相交，则直线与面相离。

点是否在面内的判断：采用传统的射线法进行计算，通过穿过该点射线与面交点的个数判断[11]。若交点个数为奇数，则点在面内；若交点个数为偶数，则点在面外部。

点是否在线上的判断：首先分别计算直线的长度和点到直线两个端点的长度，用点到直线两个端点长度的和减去直线的长度，得到的值取绝对值除以直线的长度，然后将值与α对比，如果小于α，则点在直线上；否则点不在线上。

2.2 无人机飞行区域拓扑关系计算实现方法

根据上述算法思想及流程，以VC++语言作为工具实现其具体计算，在实现过程中定义以下函数：polygonAndPolygon（）判断面与面关系；polyLineAndPolygon（）判断折线与面关系；LineAndPolygon（）判断直线与面关系；isPointInPolygon（）判断点是否在面内；isLineIntersect（）判断两条直线是否相交；isPointInLine（）函数判断点是否在线上。在算法实现过程中各个函数的调用关系见图2。

3 实验验证

在实验中（电脑配置：英特尔酷睿3处理器3.50GHZ，4.00GB内存，500GB硬盘，win7 64位操作系统），以Visual Studio 2013作为开发平台，以VC++为可视化工具，设计一个拓扑关系判断验证系统，包括飞行区域的输入、飞行区域的交互（缩放、平移、删除）、飞行区域的选取以及飞行区域拓扑关系的计算等功能。在验证过程中，由于要驗证区域是验证者输入的，特别是对于区域边界间存在相互重合的情况可能会很难输入准确，因此输入区域的误差可能会造成判断结果与实际输入位置关系存在不一致的情况。以下是分别对所描述飞行区域拓扑关系判断的验证：

图3选取一组相离区域进行验证，可以看出其位置关系与判断结果相一致，即区与区拓扑关系为相离。

图4、图5和图6分别选取3种不同的相交位置关系进行拓扑关系验证，其验证结果与预期算法结果相一致，即区与区拓扑关系为相交。

图7中选取灰色区域包含于黑色区域进行验证，其实际位置关系与判断结果相一致，即区与区拓扑关系为包含。

图8中选取灰色区域包含黑色区域进行验证，其实际位置关系与判断结果相一致，即区与区拓扑关系为反包含。

4 结语

对于无人机飞行区域而言，不需要对飞行区域边界存在切点的问题进行明确区分，能够更加简化对无人机飞行区域拓扑关系的描述，从而减少算法计算量。因此，本文采用9IM对无人机飞行区域拓扑关系进行重归新纳和描述，详细介绍了拓扑关系判断中的算法流程以及具体实现方法，并通过实验验证了算法的可行性。飞行区域拓扑关系的判断能够有效解决飞行区域冲突问题，进而在无人机飞行区域电子围栏规划中能得到有效应用。

参考文献：

[1] 柯玉宝，车彦卓.如何规范管理无人机[J].机器人产业，2016，1：16-21.

[2] 赵仁量.基于Voronoi图的空间关系计算研究[D].长沙：中南大学，2002.

[3] 陈军，刘万增，李志林，等.线目标拓扑关系的细化计算方法[J].测绘学报，2006，35（8）：255-230.

[4] 邓念东，候恩科.基于GTP单纯刨分的地下实体拓扑关系形式化描述方法[J].煤炭学报，2008，33（5）：527-531.

[5] 赵红超.空间关系的研究和实现[D].北京：中国科学院，2006.

[6] 倪建华.拓扑关系计算方法研究与实现[D].长沙：中南大学，2009.

[7] 高峰.技术引领未来——无人机云系统全面解析[J].计算机与网络，2016，7：13-14.

[8] 邓敏，李成名，刘文宝.利用拓扑和度量相结合的方法描述面目标间的空间关系[J].测绘学报，2002，31（2）：2-3.

[9] 齐东洲，吴敏.高效的多边形布尔计算方法[J].计算机应用，2014，34（S2）：78-82.

[10] 李永红，华一新.一种快速判断线段相交的方法[J].测绘通报，2003，30（7）：1-2.

[11] 王润科，张彦丽.判断点与多边形位置关系的算法综述[J].甘肃联合大学学报，2006，20（6）：2-4.

（责任编辑：何 丽）