室内路网模型的构建方法研究与实现

卢 伟，魏峰远，张 硕，索荣遥

(1.河南理工大学 测绘与国土信息工程学院，河南 焦作 454003；2.北京博阳世通信息技术有限公司，北京 100101)

1 引言

随着城市变化突飞猛进，高大的建筑物不断增加，而且越来越多样化，室内导航以及基于位置的服务(location-based service，LBS)显得越来越重要[1-2]。室内路网模型的建立可以帮助人们在一些陌生或复杂的室内环境中(例如飞机场、会议室、展览厅、企业、医院、博物馆等室内区域)，用最短的时间，走最短的路，办最快的事。目前室外导航技术已相当成熟，如车载导航、手机导航、PDA手持导航等，这些均采用全球定位系统(global positioning system，GPS)卫星信号进行定位，通过结合相关的电子地图和导航软件完成位置服务。室内导航与室外导航在某些技术方面存在很多不同点，如定位技术、路网数据构建等。近年来，对室内导航系统及关键技术的研究逐渐兴起，如室内移动导航系统的路径规划方法研究[3]、室内精确定位导航系统的设计与实现[4]、位置服务中面向路网的位置匿名技术研究与实现[5]等。但目前针对室内路径点获取及路网模型构建方面的研究仍处于起步阶段，没有形成一套完整、规范的建模流程。如何确定室内路径点并建立路网模型是信号源部署和室内导航的基础环节，具有非常重要的现实意义。

2 概述

2.1 室内位置信息图

室内位置信息图，是指反映室内空间信息布局情况的空间信息图，该图既简洁地描述了周围环境又包含了足够的信息量[3]。

建筑物内部的结构物(又可称为障碍物，如墙体、走廊、展览台、墙壁壁画、桌椅等)，将整个室内空间划分成房间、公共场所以及可以进入、不可直接进入的区域。室内物体的形状基本上都可近似看成规则图形(如圆形、长方形、三角形等)，所以在构造室内位置信息图时，可以用点线连接形式表达空间布局信息。具体方法是将空间存在相互连接的地方表示成点的形式，并按每个物体与房间的比例大小，将其表示成直线段、三角形、四边形等点线形状。

(1)节点，如横、竖墙壁交接处为一个节点；门与墙的连接处为两个节点。

(2)直线段，如较小物体，表示成直线段；对于不可进入或不能直接进入的区域，以直线段表示其边界。

(3)三角形，如形状近似为三角形的物体，三条边为不能穿越的部分。

(4)四边形，如较大物体，将其近似成四边形；圆形物体，取圆的外切四边形表示，四条边线为不可穿越的部分。

2.2 Delaunay三角网剖分

Delaunay(简称DT)三角网剖分方法属于生成非结构化网格[6-7]的方法，这类方法逐步成为目前最流行的全自动网格生成方法之一，其对于区域边界线和内部媒质分界线形状不规则的情况以及场的分布变化较大的情况都能较好的适应。

Delaunay三角网剖分是前苏联数学家Delaunay在1934年提出的：对于任意给定的平面点集，只存在着唯一的一种三角网剖分方法，满足所谓的“最大化最小角”优化准则，即所有最小内角之和最大。这种剖分方法遵循“空外接圆”和“最小角最大”准则，因此，在各种二维三角网剖分[8-10]中，只有Delaullay三角网剖分才同时满足全局和局部最优，特别适用于有限元分析应用中的网格生成，获得性能优良、形状最佳的三角形单元。

3 室内路网模型的构建方法

3.1 室内空间区域剖分

实际建立室内路网模型时要合理地建立路径，并不需要对整个室内空间区域进行剖分，这样既可以保证路网的完整，又能有效地减少工作量。根据室内空间布局的用途将室内环境分为两部分，一是无需剖分区域，如走廊、卫生间、小型房间、无障碍物直接可达的房间等，用简单的直线段连接成路径，即为最短路径；二是需要剖分区域，如博物馆展览大厅、机场大厅、商场房间等大型室内环境存在障碍物，则必须进行空间区域剖分，使构建的路径可以避开障碍物且尽量满足最短条件。

以图1所示的展厅(26.5 m×16.5 m)布局为例，根据构造室内位置信息图的思想，对展厅实现空间描述，将图1(a)环境图中的墙体、门、展台等室内物体信息转换成相应的坐标位置，用点线方式表示，如图1(b)。

图1 展厅

其中，A1A2、A3A4、A5A6和A7A8分别表示门，Wl、W2、W3分别表示位于房间内部的障碍物。因为构建网路模型时仅考虑障碍物所在位置的可达性，所以房间四周的物体可忽略。

室内位置信息图建立起来之后，要对由障碍物围成的空间进行剖分处理，以便选取路径点。具体的室内空间区域剖分方法是：在ArcGIS中用整个空间区域的散点集，即图1(b)中J1-J25表示共25个结点，创建TIN不规则三角网，该三角网满足Delaunay三角网原则，剖分结果如图2(a)所示。但在ArcGIS中创建TIN不规则三角网时，软件默认的剖分区域为散点集的外围区域，所以当剖分区域为凸多边形时，可完美剖分，得到室内空间区域剖分图；当剖分区域为凹多边形时，会出现多余剖分，需要人工进行删除处理，得到室内空间区域剖分图，如图2(b)所示。

图2 室内空间区域剖分图

3.2 路径点的选取

经过剖分处理后的室内空间被更加细化、准确描述成小的空间区域。在这些小空间区域中移动时，需要明确下一步的方向和位置，而剖分后的小区域无法直接用作移动路径的点，所以需要对路径点进行选取。

路径点的选取方法是：将Delaunay三角网剖分后的各空间区域量化表示成路径点，即选择剖分后的小区域(三角形)的一个特征点(如重心、内心等)作为该小区域的表示，只要在该小区域内部范围内，均用这个特征点表示路径点。

特征点的选取原则：所有三角形都存在这样的特征点，该点最好分布于三角形的内部，其特征明显且容易获得。

图3 三角形的重心

考虑以上选取原则与实际计算的复杂性，综合ArcGIS软件中“Feature To Point”的判断转点方法，于是选择三角形的重心作为其特征点。

三角形的重心：是三角形三边中线的交点。如图3，设三角形的三个顶点坐标分别为A(x1,y1)、B(x2,y2)，C(x3,y3)，则其重心的坐标如式(1)所示计算：

(1)

遍历图中全部剖分形成的三角形(29个)之后并按照以式(1)计算，得到各小区域的重心，作为构建路网模型的路径点(L1-L29表示29个路径点)，如图4所示。

图4 路径点的选取

3.3 路径的建立与优化

路径的建立方法：将空间区域量化成的路径点(如图4上的点L1-L29)连接起来构成的线段来表示各个区域之间可以通行的路径，配合ArcGIS进行二次开发来完成路径的建立与优化。在忽略障碍物存在的情况下，路径点之间的位置关系共可以构建406条连接线，如图5所示。

图5 路径的建立

分析存在障碍物的情况，必须对图5(b)进行适当处理，增加构建路径的限制条件。本文选用以下限制条件来进行路径的筛选与优化：

(1)路径间的可取代性

相邻路径点的连线距离最短。但在构建路径时，一些非相邻路径点的连线距离(如图6中c的值)可以近似等于相邻路径点的连线距离之和(如图6中a+b的值)，从而产生大量近似可以替代的路径，浪费存储空间。

图6 三角形 判断法

本文采用三角形判断法，如图6所示，通过设定参量σ作为参考值进行路径的删减。其中图上A、B、C为路径点，ɑ、b、c分别代表路径点之间的路径。

路径间的可取代性判断式：

(2)

若满足式(2)中的条件，则路径c可以被取代，即删除路径c，保留路径ɑ、b。σ的选值根据实际应用需求而定，本文取σ=0，0.02和0.05的情况进行分析。

(2)障碍物与路径的位置关系

若路径与表示障碍物的结点连线相交或超出剖分区域，则删除该路径。为了更加精确、细致的构建路网，本文取“路径与障碍物实际区域是否相交”为限制条件，进行路径的删减。

根据上述两个限制条件，当σ=0时，路径点连线减少到189条，如图7(a)；当σ=0.02时，路径点连线减少到91条，如图7(b)；当σ=0.05时，路径点连线可继续减少到80条，如图7(c)。

图7 避开障碍物的路径图

3.4 路网模型的构建与实现

(1)网络数据集的创建

将σ=0，0.02和0.05时的路径，分别在ArcCatalog中进行网络数据集的创建(New Network Dataset)，在ArcMap中打开时的表现如图8(c)所示。

图8 A1A2→A3A4的最短路线

如图8所示，当从门A1A2出发到达门A3A4时，需要避开障碍物W1，图中的粗线表示三种情况下A1A2与A3A4之间的最短路线。

(2)路径理论值与实际值之间的误差分析

选取实验区域中10条路线的理论值与实际值之间的误差进行数据分析，根据计算，得到数据统计表1。

表1 距离数据统计表

其中，S0表示起始点与目的点之间的最短距离理论值；S0.02、S0.05表示当σ=0.02、σ=0.05构建路径时起始点到目的点所用距离实际值；ε0.02、ε0.05表示当σ=0.02、σ=0.05时路径距离实际值与理论值之间的差值。

(3)对路网进行配准

将建立好的网络数据集路网导入ArcMap中，找到与室内地图中实验区域相对应的三个角点，将其坐标改成之前记录的值，对路网进行配准，如图9(a)，完成路网模型的构建。以系统Web版为测试平台，加载制作好的室内地图及路网模型，在地图上选取起始点，自动生成最优路径操作，其效果图如图9(b)所示。另外，还可以对地图进行拖拽等操作。

图9 室内地图及路网模型

4 结语

本文根据对室内环境的空间结构分析，建立了室内位置信息图，并在此基础上结合Delaunay三角网剖分思想，探索了室内空间区域剖分方法，实现了从路径点获取到路网模型构建的全过程处理。实验表明，这种室内路网模型构建方法可行、有效。随着人们对室内移动位置服务需求的增加，室内路网模型的构建将成为一项基础且关键的任务。本文提出的室内路网模型构建方法是针对二维的空间信息图进行相应的表示与处理，虽然可以为室内路网制作和位置服务应用开发提供借鉴，但过程中丢失了部分信息如室内部分高度等。如何针对三维室内环境进行详细的描述与分析，建立路网模型是下一步的研究方向。

[1] 余涛，余彬.位置服务[M].北京：机械工业出版社，2005.

[2] WANG Shu，MIN J W，YI B K.Location Based Services for Mobiles：Technologies and Standards[EB/OL].[2014-08-02].http：//mobile-location-services.googlecode.com/svn-history/r44/trunk/Reference/ICC2008LBSforMobilessimplifiedR2.pdf.

[3] 徐静.室内移动导航系统的路径规划方法研究[D].长春：长春理工大学，2009.

[4] 杨德军.室内精确定位导航系统的设计与实现[D].北京：北京邮电大学，2011.

[5] 郑准永.位置服务中面向路网的位置匿名技术研究与实现[D].大连：大连理工大学，2013.

[6] STEVEN J.OWEN.A Survey of Unstructured Mesh Generation Technology[EB/OL].[2014-08-02].http：//ima.udg.edu/～sellares/ComGeo/OwenSurv.pdf.

[7] 陈建军.非结构化网格生成及其并行化的若十问题研究[D].杭州：浙江大学，2006.

[8] CHEN Hao，BISHO P J.Delaunay Triangulation for Curved Surfaces[C]//Proceedings of the 6th International Meshing Roundtable.Park City：[s.n.]，1997：115-127.

[9] 武晓波，王世新.Delaunay三角网的生成算法研究[J].测绘学报，1999.28(1)：28-35.

[10] 贺全兵，黎贵友，文进.生成Delaunay三角网的改进算法[J].计算机与数字工程，2005.8(34)：50-52.