顾及障碍物和子空间剖分的室内导航方法及系统

摘要

本发明提供一种顾及障碍物和子空间剖分的室内导航方法及系统，包括：根据目标区域中障碍物与非障碍物在室内的布局对目标区域的原始室内图进行处理，获取目标区域的室内简化图；对室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型；选取不规则三角网模型中各三角形的特征点作为路径点构建室内路径网络图；根据预设限制条件优化室内路径网络图；利用Dijkstra算法计算优化后的室内路径网络图中预设起点与终点之间的最短路径。本发明实现了顾及障碍物的最短路径的查找，生成的路径不会穿过障碍物且不会发生弯曲，可处理凹形空间中不规则物体，可有效地处理不通视的情况。

权利要求

1.一种顾及障碍物和子空间剖分的室内导航方法，其特征在于，包括：

根据目标区域中障碍物与非障碍物在室内的布局，对目标区域的原始室内图进行处理，获取目标区域的室内简化图，包括：所述目标区域的原始室内图中包含障碍物和非障碍物，根据所述障碍物和非障碍物的形状、所述障碍物和非障碍物与房间的比例大小，将所述障碍物和非障碍物用点线形式表示；对所述原始室内图中室内空间存在的公共区域、不可直接进入以及不可通行的区域添加标识，所述标识用于表示该区域是否授权以及通行方式的属性；其中，所述室内简化图是指反映目标区域的室内空间信息布局情况的空间信息图，既简洁地描述了周围环境又包含了几何、语义和拓扑信息；其中，所述将所述障碍物和非障碍物用点线形式表示，包括：将门用中间点表示；将墙体用连接端点的线表示；将障碍物按其与房间的比例大小用点线状物体表示，该点线状物体包括：直线段、三角形和多边形；

对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型；

选取所述不规则三角网模型中各三角形的特征点，将所述特征点作为路径点构建室内路径网络图；

根据预设限制条件优化所述室内路径网络图，所述预设限制条件包括：如果表示障碍物的节点连线与特征点连线相交，则在所述室内路径网络图中删除该特征点连线；

利用Dijkstra算法，计算优化后的室内路径网络图中预设起点与预设终点之间的最短路径。

2.根据权利要求1所述的方法，其特征在于，所述对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型，包括：遵循最小角最大准则和空外接圆准则，对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型，且在构建不规则三角网模型时满足图中的线段长均小于预设阈值；

其中，所述最小角最大准则为所有最小内角之和最大；所述空外接圆准则为在Delaunay三角剖分中任意三角形的外接圆范围内不会存在其他点。

3.根据权利要求1所述的方法，其特征在于，所述选取所述不规则三角网模型中各三角形的特征点，将所述特征点作为路径点构建室内路径网络图，包括：选择所述不规则三角网模型中各三角形的重心作为特征点，将这些特征点连接起来，构建室内路径网络图；

其中，这些特征点连接起来构成的线段为室内路径网络的边，表示各个区域之间通行的路径。

4.根据权利要求1所述的方法，其特征在于，所述根据预设限制条件优化所述室内路径网络图中的路径，包括：将所有特征点连线与表示障碍物的节点连线逐一进行比较，若某一特征点连线与某一表示障碍物的节点连线在一条线段的两边，则确定该特征点连线与该表示障碍物的节点连线相交，则在所述室内路径网络图中删除该特征点连线。

5.一种顾及障碍物和子空间剖分的室内导航系统，其特征在于，包括：

室内简化图获取模块，用于根据目标区域中障碍物与非障碍物在室内的布局，对目标区域的原始室内图进行处理，获取目标区域的室内简化图，包括：所述目标区域的原始室内图中包含障碍物和非障碍物，根据所述障碍物和非障碍物的形状、所述障碍物和非障碍物与房间的比例大小，将所述障碍物和非障碍物用点线形式表示；对所述原始室内图中室内空间存在的公共区域、不可直接进入以及不可通行的区域添加标识，所述标识用于表示该区域是否授权以及通行方式的属性；其中，所述室内简化图是指反映目标区域的室内空间信息布局情况的空间信息图，既简洁地描述了周围环境又包含了几何、语义和拓扑信息；其中，所述将所述障碍物和非障碍物用点线形式表示，包括：将门用中间点表示；将墙体用连接端点的线表示；将障碍物按其与房间的比例大小用点线状物体表示，该点线状物体包括：直线段、三角形和多边形；

三角剖分模块，用于对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型；

室内路径网络图构建模块，用于选取所述不规则三角网模型中各三角形的特征点，将所述特征点作为路径点构建室内路径网络图；

室内路径网络图优化模块，用于根据预设限制条件优化所述室内路径网络图，所述预设限制条件包括：如果表示障碍物的节点连线与特征点连线相交，则在所述室内路径网络图中删除该特征点连线；

最短路径计算模块，用于利用Dijkstra算法，计算优化后的室内路径网络图中预设起点与预设终点之间的最短路径。

6.根据权利要求5所述的系统，其特征在于，所述三角剖分模块，具体用于遵循最小角最大准则和空外接圆准则，对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型，且在构建不规则三角网模型时满足图中的线段长均小于预设阈值；

其中，所述最小角最大准则为所有最小内角之和最大；所述空外接圆准则为在Delaunay三角剖分中任意三角形的外接圆范围内不会存在其他点。

7.根据权利要求5所述的系统，其特征在于，所述室内路径网络图构建模块，具体用于选择所述不规则三角网模型中各三角形的重心作为特征点，将这些特征点连接起来，构建室内路径网络图；

其中，这些特征点连接起来构成的线段为室内路径网络的边，表示各个区域之间通行的路径；

和/或，

所述室内路径网络图优化模块，具体用于

将所有特征点连线与表示障碍物的节点连线逐一进行比较，若某一特征点连线与某一表示障碍物的节点连线在一条线段的两边，则确定该特征点连线与该表示障碍物的节点连线相交，则在所述室内路径网络图中删除该特征点连线。

说明书

顾及障碍物和子空间剖分的室内导航方法及系统

技术领域

[0001] 本发明涉及室内导航技术领域，尤其涉及一种顾及障碍物和子空间剖分的室内导航方法及系统。

背景技术

[0002] 目前，户外环境中定位问题已经解决，因为像GPS全球定位技术以及利用遥感和摄影测量技术获得大量的道路网络数据集已经成为可能。像手机、汽车上都装有导航系统，这些都是成熟的室外导航领域。它的原理主要利用GPS定位，利用导航电子地图进行引导，结合相关的导航软件完成导航服务。但是GPS在室内不能定位，主要是通过WiFi、蓝牙等无线信号进行室内定位。随着城市化进程加快，在公共建筑如购物中心、机场和音乐厅变得更大、更复杂的情况下，即使是熟悉这些环境的人们也很难到达一些特定的房间或地点。由此室内导航得到更多的关注。

[0003] 现在好多商家已经意识到室内导航的许多商业价值，比如商场促销活动消息结合顾客位置进行推送；车库内定位导航找到停车位等。但是明显存在一些难点，比如商场的平面图数据、品牌数据没法获得；室内导航图的设计不易；室内定位还不是很精确；用户可以在建筑内部边缘之间自由移动；由于复杂的室内空间环境，不容易直接构建导航网络。要实现室内导航系统仍存在很多需要研究和解决的问题，例如：如何在室内提供优秀的定位信息；室内环境导航图的设计；最短路径规划算法等等。这些问题需要做进一步的验证和研究。

[0004] 目前国内外对室内导航算法的研究有很多，其中建立室内空间模型是实现导航的基础和关键。室内实体或现象在空间上会受到各类构件的约束，如门、墙、走廊和楼梯等，如此就使得室内空间非连续化，针对这个问题，越来越多的学者开始研究建立有效的模型将室内非连续空间连续化。其中包括建筑规划延伸模型、语义模型、拓扑模型和网格模型。在地理空间中，使用单纯的语义模型来描述室内空间是不够全面、直接的，因此，更多的研究趋向于在语义模型中加入拓扑信息来优化模型。或者是在拓扑模型基础上计入其他信息的混合模型。因为拓扑模型中的节点和弧段类似于图论中的元素，而且图论有成熟的数学体系为支撑。

[0005] 在目前许多的室内空间模型中，大多数是对建筑物室内某区域空间的粗粒度抽象，缺少对室内障碍物等细节的描述。也有一些学者，虽然考虑了障碍物的存在，但是只是针对固定存在的并且影响起止点通视性的障碍物，对路径图进行手动添加可视点，从而形成起止点的路径。现有技术中将障碍物描述为简单的矩形，但是不涉及复杂图形的处理，根据用户的尺寸计算障碍物间最小距离并建立障碍物组，在寻找起止点的路径时，选择涉及到的障碍物组从而减少了计算量。

[0006] 中轴变换(Medial Axis Transform，简称MAT)和可见性图表(Visibility Graph,简称VG)是室内路径计算的两个主要贡献,促使导航网络的生成。直中轴变换(Straight Medial Axis Transform，简称S-MAT)不适合处理较大的形状任意的空间，在开放空间，S-MAT生成的路径会产生扭曲，这显然是中轴变换的弱点。基于VG引入的门到门“door-to-door”方法，图中的每个节点代表一个点的位置，以及它们之间每个边缘代表一个可见的连接。这种方法存在两个问题：边的数量迅速增加，即使在凸空间没有障碍物情况下，可能的组合数量也是二次的，而且随之而来的路线描述解读对于人来说特别复杂。

[0007] 鉴于此，如何克服现有算法的局限性，从室内存在障碍物的角度出发提供一种室内导航方法，以实现顾及障碍物的最短路径的查找成为目前需要解决的技术问题。

发明内容

[0008] 为解决上述的技术问题，本发明提供一种顾及障碍物和子空间剖分的室内导航方法及系统，针对现有算法的局限性，从室内存在障碍物的角度出发，构建一个合适的室内空间模型，建立室内路径网络，实现了顾及障碍物的最短路径的查找，以实现室内导航，本方法可以处理凹形空间中不规则物体，并且生成的路径不会穿过障碍物而且不会发生弯曲。

[0009] 第一方面，本发明提供一种顾及障碍物和子空间剖分的室内导航方法，包括：

[0010] 根据目标区域中障碍物与非障碍物在室内的布局，对目标区域的原始室内图进行处理，获取目标区域的室内简化图；

[0011] 对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型；

[0012] 选取所述不规则三角网模型中各三角形的特征点，将所述特征点作为路径点构建室内路径网络图；

[0013] 根据预设限制条件优化所述室内路径网络图，所述预设限制条件包括：如果表示障碍物的节点连线与特征点连线相交，则在所述室内路径网络图中删除该特征点连线；

[0014] 利用Dijkstra算法，计算优化后的室内路径网络图中预设起点与预设终点之间的最短路径。

[0015] 可选地，所述根据目标区域中障碍物与非障碍物在室内的布局，对目标区域的原始室内图进行处理，获取目标区域的室内简化图，包括：

[0016] 所述目标区域的原始室内图中包含障碍物和非障碍物，根据所述障碍物和非障碍物的形状、所述障碍物和非障碍物与房间的比例大小，将所述障碍物和非障碍物用点线形式表示；

[0017] 对所述原始室内图中室内空间存在的公共区域、不可直接进入以及不可通行的区域添加标识，所述标识用于表示该区域是否授权以及通行方式的属性；

[0018] 其中，所述室内简化图是指反映目标区域的室内空间信息布局情况的空间信息图，既简洁地描述了周围环境又包含了几何、语义和拓扑信息。

[0019] 可选地，将所述障碍物和非障碍物用点线形式表示，包括：

[0020] 将门用中间点表示；将墙体用连接端点的线表示；将障碍物按其与房间的比例大小用点线状物体表示，该点线状物体包括：直线段、三角形和多边形。

[0021] 可选地，所述对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型，包括：

[0022] 遵循最小角最大准则和空外接圆准则，对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型，且在构建不规则三角网模型时满足图中的线段长均小于预设阈值；

[0023] 其中，所述最小角最大准则为所有最小内角之和最大；所述空外接圆准则为在Delaunay三角剖分中任意三角形的外接圆范围内不会存在其他点。

[0024] 可选地，所述选取所述不规则三角网模型中各三角形的特征点，将所述特征点作为路径点构建室内路径网络图，包括：

[0025] 选择所述不规则三角网模型中各三角形的重心作为特征点，将这些特征点连接起来，构建室内路径网络图；

[0026] 其中，这些特征点连接起来构成的线段为室内路径网络的边，表示各个区域之间通行的路径。

[0027] 可选地，所述根据预设限制条件优化所述室内路径网络图中的路径，包括：

[0028] 将所有特征点连线与表示障碍物的节点连线逐一进行比较，若某一特征点连线与某一表示障碍物的节点连线在一条线段的两边，则确定该特征点连线与该表示障碍物的节点连线相交，则在所述室内路径网络图中删除该特征点连线。

[0029] 第二方面，本发明提供一种顾及障碍物和子空间剖分的室内导航系统，包括：

[0030] 室内简化图获取模块，用于根据目标区域中障碍物与非障碍物在室内的布局，对目标区域的原始室内图进行处理，获取目标区域的室内简化图；

[0031] 三角剖分模块，用于对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型；

[0032] 室内路径网络图构建模块，用于选取所述不规则三角网模型中各三角形的特征点，将所述特征点作为路径点构建室内路径网络图；

[0033] 室内路径网络图优化模块，用于根据预设限制条件优化所述室内路径网络图，所述预设限制条件包括：如果表示障碍物的节点连线与特征点连线相交，则在所述室内路径网络图中删除该特征点连线；

[0034] 最短路径计算模块，用于利用Dijkstra算法，计算优化后的室内路径网络图中预设起点与预设终点之间的最短路径。

[0035] 可选地，所述室内简化图获取模块，具体用于

[0036] 所述目标区域的原始室内图中包含障碍物和非障碍物，根据所述障碍物和非障碍物的形状、所述障碍物和非障碍物与房间的比例大小，将所述障碍物和非障碍物用点线形式表示；

[0037] 对所述原始室内图中室内空间存在的公共区域、不可直接进入以及不可通行的区域添加标识，所述标识用于表示该区域是否授权以及通行方式的属性；

[0038] 其中，所述室内简化图是指反映目标区域的室内空间信息布局情况的空间信息图，既简洁地描述了周围环境又包含了几何、语义和拓扑信息。

[0039] 可选地，所述三角剖分模块，具体用于

[0040] 遵循最小角最大准则和空外接圆准则，对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型，且在构建不规则三角网模型时满足图中的线段长均小于预设阈值；

[0041] 其中，所述最小角最大准则为所有最小内角之和最大；所述空外接圆准则为在Delaunay三角剖分中任意三角形的外接圆范围内不会存在其他点。

[0042] 可选地，所述室内路径网络图构建模块，具体用于

[0043] 选择所述不规则三角网模型中各三角形的重心作为特征点，将这些特征点连接起来，构建室内路径网络图；

[0044] 其中，这些特征点连接起来构成的线段为室内路径网络的边，表示各个区域之间通行的路径；

[0045] 和/或，

[0046] 所述室内路径网络图优化模块，具体用于

[0047] 将所有特征点连线与表示障碍物的节点连线逐一进行比较，若某一特征点连线与某一表示障碍物的节点连线在一条线段的两边，则确定该特征点连线与该表示障碍物的节点连线相交，则在所述室内路径网络图中删除该特征点连线。

[0048] 由上述技术方案可知，本发明的顾及障碍物和子空间剖分的室内导航方法及系统，在总结当前室内导航路径图生成算法的基础上，针对现有算法的局限性，从室内存在障碍物的角度出发，构建一个合适的室内空间模型，建立室内路径网络，实现了顾及障碍物的最短路径的查找，相比于S-MAT和“door-to-door”方法，S-MAT不适合处理较大的形状任意的空间，本发明可以克服此类问题，生成的路径不会穿过障碍物而且不会发生弯曲；并且本发明可以处理凹形空间中不规则物体，而且包含了“door-to-door”方法的优点，即有效地处理了不通视的情况。

附图说明

[0049] 图1为本发明一实施例提供的一种顾及障碍物和子空间剖分的室内导航方法的流程示意图；

[0050] 图2为图1所示方法的一案例的原始室内图；

[0051] 图3为图2所示案例的室内简化图；

[0052] 图4为图2所示案例的室内空间区域剖分及特征点显示图；

[0053] 图5为本实施例图1所示方法提供的一种线段相交示意图；

[0054] 图6为图2所示案例的路径网络图及起止点最短路径；

[0055] 图7为本发明实施例提供的一种顾及障碍物和子空间剖分的室内导航系统的结构示意图。

具体实施方式

[0056] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整的描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他的实施例，都属于本发明保护的范围。

[0057] 图1示出了本发明一实施例提供的顾及障碍物和子空间剖分的室内导航方法的流程示意图，如图1所示，本实施例的顾及障碍物和子空间剖分的室内导航方法，包括下述步骤101-105：

[0058] 101、根据目标区域中障碍物与非障碍物在室内的布局，对目标区域的原始室内图进行处理，获取目标区域的室内简化图。

[0059] 可理解的是，一般的室内图，如某建筑的二维平面布置图，该图的信息不能直接为用户所用，而且还未出现可以直接应用的存储信息的数据库，因此需要根据原始的室内图，根据障碍物与非障碍物在室内的布局，通过适当处理得到可利用的室内简化图。所述室内简化图是指反映目标区域的室内空间信息布局情况的空间信息图，既简洁地描述了周围环境又包含了几何、语义和拓扑信息。

[0060] 室内空间一般会由阻碍通行的结构物隔开，比如墙体，桌椅等，这些常见的结构物也称为障碍物，它们将空间划分成功能不同的房间。在构造室内简化图时，我们必须解决障碍物及各个物体的表示问题。一般室内物体都可以描述成不同形状的图形，我们将室内物体用点线形式表示，在具体应用中，所述步骤101可具体包括：

[0061] 所述目标区域的原始室内图中包含障碍物和非障碍物，根据所述障碍物和非障碍物的形状、所述障碍物和非障碍物与房间的比例大小，将所述障碍物和非障碍物用点线形式表示；举例来说，可以将门用中间点表示；将墙体用连接端点的线表示；将障碍物按其与房间的比例大小用直线段、三角形和多边形等点线状物体表示；

[0062] 对所述原始室内图中室内空间存在的公共区域、不可直接进入以及不可通行的区域添加标识，所述标识用于表示该区域是否授权以及通行方式的属性，用如此的语义信息增强室内简化图；举例来说，出入口可以直接通过，有些房间需要钥匙才可以进入，窗户和紧急出口在一般情况下不可以使用。

[0063] 102、对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型。

[0064] 可理解的是，所述室内简化图中，对于有些区域即室内无障碍物直接可达的房间无需剖分，用直线段连接出发点与目的地即为最短路径；另一方面，有些区域存在障碍物，需要将其剖分之后进行路径规划，如客厅、商场大厅等，得到的路径需要绕开障碍物并且满足最短条件。

[0065] 在具体应用中，所述步骤102遵循最小角最大准则和空外接圆准则，对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，即将较大的室内空间分解成多个小空间区域，构建不规则三角网模型，且在构建不规则三角网模型时满足图中的线段长均小于预设阈值；

[0066] 其中，所述最小角最大准则为所有最小内角之和最大；所述空外接圆准则为在Delaunay三角剖分中任意三角形的外接圆范围内不会存在其他点。

[0067] 可理解的是，Delaunay三角剖分用于生成非结构化网格，对于任意给定的平面点集，只存在着唯一的一种三角剖分方法，该剖分方法遵循最小角最大准则和空外接圆准则。基于这两种准则，以及其对于区域边界线和内部媒质分界线形状不规则的情况和场的分布变化较大的情况都能较好的适应，和其他二维三角剖分比较得出，只有Delaunay三角剖分才同时满足全局和局部最优。在构建不规则三角网(TIN)函数pTRI＝Create_Tri()中，为了获得高质量的三角网需要预设一个阈值，确保图中的线段长均小于这个预设阈值，这样所有边才能出现在三角网中。但是在障碍物内存在多余的三角形时，需要将其删掉才能得到最终的三角网。

[0068] 103、选取所述不规则三角网模型中各三角形的特征点，将所述特征点作为路径点构建室内路径网络图。

[0069] 在具体应用中，所述步骤103可以具体包括：

[0070] 选择所述不规则三角网模型中各三角形的重心作为特征点，将这些特征点连接起来，构建室内路径网络图；

[0071] 其中，这些特征点连接起来构成的线段为室内路径网络的边，表示各个区域之间通行的路径。

[0072] 可理解的是，剖分后的室内空间由许多三角形构成，所述不规则三角网模型中每个三角形可用一个点来表示，而这些点是不规则三角网中的节点。选择三角形的重心作为特征点，当处于该三角形内时，均用代表这个三角形的特征点来表示，换句话说，从该区域走到另一个区域，实则点到点的移动，将这些特征点连接起来构成的线段表示各个区域之间通行的路径，也就是路径网络的边。

[0073] 可理解的是，特征点的选取简单而直接，本实施例优先选择三角形的重心作为特征点。在具体应用中，本实施例也可以选择一些容易辨认的代表某种功能的点作为特征点，比如某个植物或者地面上的地标等。

[0074] 104、根据预设限制条件优化所述室内路径网络图，所述预设限制条件包括：如果表示障碍物的节点连线与特征点连线相交，则在所述室内路径网络图中删除该特征点连线。

[0075] 在具体应用中，在创建室内路径网络时，需要避免相邻三角形的连接，因为这样会生成锯齿形的路径。因此，障碍物存在的情况下，所述步骤104中需增加构建路径的预设限制条件，因此所述步骤104可以具体包括：

[0076] 将所有特征点连线与表示障碍物的节点连线逐一进行比较，若某一特征点连线与某一表示障碍物的节点连线在一条线段的两边，则确定该特征点连线与该表示障碍物的节点连线相交，则在所述室内路径网络图中删除该特征点连线。

[0077] 105、利用迪克斯特拉Dijkstra算法，计算优化后的室内路径网络图中预设起点与预设终点之间的最短路径。

[0078] 可理解的是，Dijkstra算法的基本思路是：Dijkstra是一个按权值大小递增的次序产生最短路径的算法，它可用于计算从有向图中任意一节点到其他节点的最优路径，不仅包括起点和终点。它是目前公认的求解最短路径问题的最经典算法，只要图中所有弧的权为非负，它都适用。因此本实施例利用Dijkstra算法解决图中任意两个顶点之间的最短路径问题，所述最短路径为优化后的室内路径网络图中预设起点与预设终点之间绕开室内障碍物的最短路径，步骤105可实现绕开室内障碍物，并通过判断室内空间该区域是否授权通过以及通行方式的属性，基于路径网络图寻找最短路径。

[0079] 下面举一个具体的例子来进一步说明本实施例。

[0080] 图2为图1所示方法的一案例的原始室内图，该原始室内图为室内布局图，包括出入口、教室，以及特殊用途的房间(包括教室、办公室、会议室、储藏室和卫生间等)。这些室内空间包括一些桌椅、板凳和障碍物等。其中最右边的大厅内设置了一些不规则的障碍物。对图2所示案例执行上述步骤101之后，可以得到如图3所示的室内简化图，图3中表示开口信息的节点被赋予不同的“可进入”信息，其中2个出口(E1&E2)、16个房门(其中有4个房门需要钥匙才可进入，包括D1、D2、D4、D14，其他可直接进入)以及14扇窗户(W1-W14)，出口可以随意通行，房间需要有进入的钥匙，窗口一般情况下不可通行，用如此的语义信息增强室内简化图。对图2所示案例执行上述步骤102之后，可以得到如图4所示的室内空间区域剖分及特征点显示图，图4中最终构建出的三角形个数是304个。执行上述步骤103遍历图4中全部三角形之后可得到所有的路径点，加上出发点(E1)和目的地(W9)两个点组成了特征点集合(见图4)，将这些特征点连接起来构成路径网络的边。执行上述步骤104，可参考图5，如图
5所示，令
只要d1×d2<0并且d3×d4<0，则p1p2和p3p4这两条线段必然相交，但是
结果等于0则要判断对应的点是否在线段上。图4的特征点之间可以连接46665条线段。根据上述预设限制条件，将所有特征点连线与表示障碍物的节点连线进行比较，如果满足以上相交条件则需将该路线删除，最终图6还剩下3732条线段。执行上述步骤105，假若一个学生从出口E1进入，需要到自习教室的靠窗位置自习，对于图6，将出口E1和窗户W9预设为起点和终点，通过Dijkstra算法，可以找到两点间的最短路径，图6中最黑的一条线给出了绕过走廊上的障碍物以及教室内的桌椅到达窗户W9的最短路径。

[0081] 本实施例的顾及障碍物和子空间剖分的室内导航方法，在总结当前室内导航路径图生成算法的基础上，针对现有算法的局限性，从室内存在障碍物的角度出发，构建一个合适的室内空间模型，建立室内路径网络，实现了顾及障碍物的最短路径的查找，相比于S-MAT和“door-to-door”方法，S-MAT不适合处理较大的形状任意的空间，本发明可以克服此类问题，生成的路径不会穿过障碍物而且不会发生弯曲；并且本发明可以处理凹形空间中不规则物体，而且包含了“door-to-door”方法的优点，即有效地处理了不通视的情况。

[0082] 图7示出了本发明一实施例提供的一种顾及障碍物和子空间剖分的室内导航系统的结构示意图，如图7所示，本实施例的顾及障碍物和子空间剖分的室内导航系统，包括：室内简化图获取模块71、三角剖分模块72、室内路径网络图构建模块73、室内路径网络图优化模块74和最短路径计算模块75；其中：

[0083] 室内简化图获取模块71，用于根据目标区域中障碍物与非障碍物在室内的布局，对目标区域的原始室内图进行处理，获取目标区域的室内简化图；

[0084] 三角剖分模块72，用于对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型；

[0085] 室内路径网络图构建模块73，用于选取所述不规则三角网模型中各三角形的特征点，将所述特征点作为路径点构建室内路径网络图；

[0086] 室内路径网络图优化模块74，用于根据预设限制条件优化所述室内路径网络图，所述预设限制条件包括：如果表示障碍物的节点连线与特征点连线相交，则在所述室内路径网络图中删除该特征点连线；

[0087] 最短路径计算模块75，用于利用Dijkstra算法，计算优化后的室内路径网络图中预设起点与预设终点之间的最短路径。

[0088] 在具体应用中，所述室内简化图获取模块71，可具体用于

[0089] 所述目标区域的原始室内图中包含障碍物和非障碍物，根据所述障碍物和非障碍物的形状、所述障碍物和非障碍物与房间的比例大小，将所述障碍物和非障碍物用点线形式表示；

[0090] 对所述原始室内图中室内空间存在的公共区域、不可直接进入以及不可通行的区域添加标识，所述标识用于表示该区域是否授权以及通行方式的属性；

[0091] 其中，所述室内简化图是指反映目标区域的室内空间信息布局情况的空间信息图，既简洁地描述了周围环境又包含了几何、语义和拓扑信息。

[0092] 在具体应用中，所述三角剖分模块72，可具体用于

[0093] 遵循最小角最大准则和空外接圆准则，对所述室内简化图中存在障碍物的室内空间进行Delaunay三角剖分，构建不规则三角网模型，且在构建不规则三角网模型时满足图中的线段长均小于预设阈值；

[0094] 其中，所述最小角最大准则为所有最小内角之和最大；所述空外接圆准则为在Delaunay三角剖分中任意三角形的外接圆范围内不会存在其他点。

[0095] 在具体应用中，所述室内路径网络图构建模块73，可具体用于

[0096] 选择所述不规则三角网模型中各三角形的重心作为特征点，将这些特征点连接起来，构建室内路径网络图；

[0097] 其中，这些特征点连接起来构成的线段为室内路径网络的边，表示各个区域之间通行的路径。

[0098] 在具体应用中所述室内路径网络图优化模块74，可具体用于

[0099] 将所有特征点连线与表示障碍物的节点连线逐一进行比较，若某一特征点连线与某一表示障碍物的节点连线在一条线段的两边，则确定该特征点连线与该表示障碍物的节点连线相交，则在所述室内路径网络图中删除该特征点连线。

[0100] 可理解的是，所述最短路径计算模块75可利用Dijkstra算法，实现绕开室内障碍物，并通过判断室内空间该区域是否授权通过以及通行方式的属性，基于路径网络图寻找最短路径。

[0101] 本实施例的顾及障碍物和子空间剖分的室内导航系统，在总结当前室内导航路径图生成算法的基础上，针对现有算法的局限性，从室内存在障碍物的角度出发，构建一个合适的室内空间模型，建立室内路径网络，实现了顾及障碍物的最短路径的查找，相比于S-MAT和“door-to-door”方法，S-MAT不适合处理较大的形状任意的空间，本发明可以克服此类问题，生成的路径不会穿过障碍物而且不会发生弯曲；并且本发明可以处理凹形空间中不规则物体，而且包含了“door-to-door”方法的优点，即有效地处理了不通视的情况。

[0102] 本实施例所述的系统可以用于执行上述方法实施例，其原理和技术效果类似，此处不再赘述。

[0103] 需要说明的是，对于系统实施例而言，由于其与方法实施例基本相似，所以描述的比较简单，相关之处参见方法实施例的部分说明即可。

[0104] 本实施例的基于大数据与市价匹配的农业科技成果估价系统，可避免过多的人为参与带来的主观误差，以网络大数据为数据源，通过筛选，然后运用市场价格匹配模型进行分析，能够保证得到的农业科技成果的价格不脱离市场，更具有可参考性。

[0105] 本领域普通技术人员可以理解：实现上述各方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成。前述的程序可以存储于一计算机可读取存储介质中。该程序在执行时，执行包括上述各方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

[0106] 最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的范围。