适用于反向寻车的停车场地图设计

冯小刚　杜军威

摘要：针对综合体地下停车场空间庞大、结构复杂等特点，停车、寻车已成为制约车主消费体验的瓶颈，提出了一种面向地下停车场地图结构设计方案，能够实现多层停车场图形抽象为一个图模型，基于图模型能够快速计算寻车的有效最短路径。设计方案集成于手机反向寻车软件，并通过实际部署的案例，验证地图结构设计的有效性和准确性。

关键词：停车场；反向寻车；最短路径；二维码；寻车软件

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2014）36-8692-03

随着社会的进步、经济的发展，城市中大型商场、购物中心等不断出现，其停车场规模也不断扩大。由于停车场内空间大、环境及标志物类似、方向不易辨别，车主在返回停车场找车时，往往迷失方向，找不到自己的车辆。这不仅让用户浪费了宝贵的时间，降低了用户在停车场的体验，也降低了停车场的周转效率。因此大型停车场找车难问题成为近几年人们不断研究和急需解决的问题。

近年来人们一直对停车场反向寻车[1][2]方法进行着不停地探索，并且已取得了一定的效果。目前主要解决方案有刷卡定位方式、条形码取票定位方式、视频识别定位方式[3]、指纹识别方式等。这几种反向寻车方式都有一些缺点，刷卡定位、条形码取票、指纹识别方式都需要车主用户在特定的地方记录位置信息并拥有或者索取位置凭证，视频设别方式需要在停车场每个车位旁安装一个视频设别装置，实施成本极高。此外，车主寻车时，必须在指定的寻车终端查询车辆车位信息，不能随行随找，使用效果不是很理想。该文提出的停车场地图设计能够很容易的转化为图[4][5]的模型，从而为停车场反向寻车提供一种更好的解决方案。

1 地图设计

停车场通常包括若干停车楼层，每个停车楼层中有若干线路、柱子、停车位、电梯或楼梯出入口等。本设计中停车场地图包含以下内容：各个停车楼层的图片文件（每个停车楼层一个图片；该图片展现了相应停车楼层的结构）、整个停车场地图描述文件（XML[6]格式的文件）；一系列二维码信息文件（二维码存储停车场地图描述文件中柱子相关信息，通过二维码可以确定停车场中的柱子，通常由寻车软件读取并使用）。停车场地图描述文件描述了每个停车楼层及其大小、每个停车楼层包含的线路、各个线路之间的交叉点、每个楼层中的车位或者柱子（本设计采用柱子）、各个停车楼层之间的关联点。

在根据地图描述文件构造图时，线路交叉点作为图的节点、线路（两个交叉点之间的部分）作为图的边。由于停车场中柱子点很多，如果将每个柱子都视为一个位置点放在模型图中的点集中，那么构造的图的顶点数和边数会非常多，增加计算的复杂度。本设计中柱子点不包括在图的点集中，而是在计算两个位置（柱子）之间的最短路径时，柱子动态添加到图的点集中，与柱子相关的边动态添加到图的边集中，从而有效地减少了图的点数和边数，降低了计算的复杂度。

楼层图片文件片段和地图描述文件片段分别如图1和图2。

1.1 地图描述文件详细描述

根元素park表示一个停车场，width和height属性分别表示停车场长度和宽度，停车场各个楼层长度和宽度通常一样。元素floor表示停车场中的一个停车楼层，每个停车楼层有一个唯一标示id，停车楼层内有lines、points和pillars，分别表示线路集合、线路的交叉点集合和柱子集合。每个交叉点元素point有唯一标示id、x坐标和y坐标（在楼层图片文件中的横纵坐标），每个线路元素line有唯一标示id、线路长度length、线路的起始点和终止点，每个柱子元素pillar有一个唯一标示id、柱子的x坐标和y坐标（在楼层图片文件中的横纵坐标）和该柱子所属的线路（距离该柱子最近的线路），元素relation表示两个停车楼层之间的连接线路，连接的端点为某楼层上的某个点。

此外柱子还有一些描述信息message，该信息描述了此柱子的位置坐标和所属的线路。该信息可以用于外部使用（如对其生成二维码贴于实际停车场中对应的柱子上，通过手机扫描二维码即可获得该柱子的相关信息）。

通过地图描述文件，我们可以将停车场结构抽象为图的模型，进而可以计算任意两点之间的最短路径，结合地图文件将最优线路展示给车主用户。

2 基于地图文件计算最短线路

本文地图文件是针对于停车场反向停车而设计的。反向寻车核心即为确定车主与车的位置及车主位置到车位置之间的最短线路的计算。确定了停车场中的两个点以后既可以根据停车场地图描述文件计算两点之间的最短线路。停车场中两个点通常由车主用户使用手机扫描相应的二维码得到（每个二维码所包含的信息是根据柱子的相关信息而生成）。根据两个点（柱子信息）及描述文件计算最短线路的步骤如下：

1） 确定两个点person、car（它们包含了柱子的相关信息）及停车场地图描述文件，

2） 定义图的邻接矩阵matrix及图的点集合points和边集合lines

3） 解析停车场描述文件，根据point元素初始化图的点集，根据line元素初始化图的边集

4） 将点person添加到点集中作为点集的第一个元素，同时根据点坐标及其所属线路line_person计算点person到线line_person之间的垂线段并将该垂线段添加的图的边集中

5） 将点car添加到点集中作为点集的最后一个元素，同时根据点坐标及其所属线路line_car计算点car到线line_car之间的垂线段并将该垂线段添加的图的边集中

6） 根据图的点集合points和边集合lines初始化图的邻接矩阵matrix，线路的长度作为图中边的权值

7） 使用一种最短路径计算方法（如迪杰斯特拉算法）计算从起始点（person作为起始点）到终止点（car作为终止点）的最短路径，最短路径上的点存储在一个数组result_path中。

3 实验结果

针对上述地图设计，该文设计并实现的停车场反向寻车软件对上述地图设计进行了验证。该软件需要运行在手机上，并要求手机具有摄像头功能，本测试手机为华为荣耀3C Android[7-9]平台手机。该文分别就起始点、终止点在同一停车楼层和起始点、终止点在不同停车楼层进行了验证，试验时起始点和终止点均为随机选取并进行了多次试验。实验结果展示分别如图3和图4。

4 结论

本文提出了一种适用于反向寻车的停车场地图设计，该设计主要是地图描述文件的设计，该地图描述文件可以转化为图的模型。结合二维码存储停车场柱子位置信息，本设计能够通过手机计算并展示车主位置和停车位置之间的最短线路，从而可以有效地解决大型停车场车主用户找车难问题。

参考文献：

[1] 王扬，薛娟.智能停车场反向寻车系统设计与实现[J].无线互联科技，2012（11）.

[2] 樊勇，任燕，司博章.一种新型停车场反向寻车系统[J].物联网技术，2013（2）.

[3] 科拓.车位引导|反向寻车[EB/OL].http：//www.keytop.com.cn/

[4] 刘小晶，杜选.数据结构（java语言描述）[M].北京：清华大学出版社，2011：192-232.

[5] 王桂平，王衍，任嘉辰.图论算法理论、实现及应用[M].北京；北京大学出版社，2011.

[6] W3C. XML教程[EB/OL].http：//www.w3school.com.cn/xml/.

[7] 王雅宁.轻松学android开发[M].北京：电子工业出版社，2013：1-331.

[8] Google. Android[EB/OL].http：//developer.android.com/index.html.

[9] 李宁. Android/Ophne开发完全讲义[M].北京：中国水利水电出版社，2010.endprint

摘要：针对综合体地下停车场空间庞大、结构复杂等特点，停车、寻车已成为制约车主消费体验的瓶颈，提出了一种面向地下停车场地图结构设计方案，能够实现多层停车场图形抽象为一个图模型，基于图模型能够快速计算寻车的有效最短路径。设计方案集成于手机反向寻车软件，并通过实际部署的案例，验证地图结构设计的有效性和准确性。

关键词：停车场；反向寻车；最短路径；二维码；寻车软件

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2014）36-8692-03

随着社会的进步、经济的发展，城市中大型商场、购物中心等不断出现，其停车场规模也不断扩大。由于停车场内空间大、环境及标志物类似、方向不易辨别，车主在返回停车场找车时，往往迷失方向，找不到自己的车辆。这不仅让用户浪费了宝贵的时间，降低了用户在停车场的体验，也降低了停车场的周转效率。因此大型停车场找车难问题成为近几年人们不断研究和急需解决的问题。

近年来人们一直对停车场反向寻车[1][2]方法进行着不停地探索，并且已取得了一定的效果。目前主要解决方案有刷卡定位方式、条形码取票定位方式、视频识别定位方式[3]、指纹识别方式等。这几种反向寻车方式都有一些缺点，刷卡定位、条形码取票、指纹识别方式都需要车主用户在特定的地方记录位置信息并拥有或者索取位置凭证，视频设别方式需要在停车场每个车位旁安装一个视频设别装置，实施成本极高。此外，车主寻车时，必须在指定的寻车终端查询车辆车位信息，不能随行随找，使用效果不是很理想。该文提出的停车场地图设计能够很容易的转化为图[4][5]的模型，从而为停车场反向寻车提供一种更好的解决方案。

1 地图设计

停车场通常包括若干停车楼层，每个停车楼层中有若干线路、柱子、停车位、电梯或楼梯出入口等。本设计中停车场地图包含以下内容：各个停车楼层的图片文件（每个停车楼层一个图片；该图片展现了相应停车楼层的结构）、整个停车场地图描述文件（XML[6]格式的文件）；一系列二维码信息文件（二维码存储停车场地图描述文件中柱子相关信息，通过二维码可以确定停车场中的柱子，通常由寻车软件读取并使用）。停车场地图描述文件描述了每个停车楼层及其大小、每个停车楼层包含的线路、各个线路之间的交叉点、每个楼层中的车位或者柱子（本设计采用柱子）、各个停车楼层之间的关联点。

在根据地图描述文件构造图时，线路交叉点作为图的节点、线路（两个交叉点之间的部分）作为图的边。由于停车场中柱子点很多，如果将每个柱子都视为一个位置点放在模型图中的点集中，那么构造的图的顶点数和边数会非常多，增加计算的复杂度。本设计中柱子点不包括在图的点集中，而是在计算两个位置（柱子）之间的最短路径时，柱子动态添加到图的点集中，与柱子相关的边动态添加到图的边集中，从而有效地减少了图的点数和边数，降低了计算的复杂度。

楼层图片文件片段和地图描述文件片段分别如图1和图2。

1.1 地图描述文件详细描述

根元素park表示一个停车场，width和height属性分别表示停车场长度和宽度，停车场各个楼层长度和宽度通常一样。元素floor表示停车场中的一个停车楼层，每个停车楼层有一个唯一标示id，停车楼层内有lines、points和pillars，分别表示线路集合、线路的交叉点集合和柱子集合。每个交叉点元素point有唯一标示id、x坐标和y坐标（在楼层图片文件中的横纵坐标），每个线路元素line有唯一标示id、线路长度length、线路的起始点和终止点，每个柱子元素pillar有一个唯一标示id、柱子的x坐标和y坐标（在楼层图片文件中的横纵坐标）和该柱子所属的线路（距离该柱子最近的线路），元素relation表示两个停车楼层之间的连接线路，连接的端点为某楼层上的某个点。

此外柱子还有一些描述信息message，该信息描述了此柱子的位置坐标和所属的线路。该信息可以用于外部使用（如对其生成二维码贴于实际停车场中对应的柱子上，通过手机扫描二维码即可获得该柱子的相关信息）。

通过地图描述文件，我们可以将停车场结构抽象为图的模型，进而可以计算任意两点之间的最短路径，结合地图文件将最优线路展示给车主用户。

2 基于地图文件计算最短线路

本文地图文件是针对于停车场反向停车而设计的。反向寻车核心即为确定车主与车的位置及车主位置到车位置之间的最短线路的计算。确定了停车场中的两个点以后既可以根据停车场地图描述文件计算两点之间的最短线路。停车场中两个点通常由车主用户使用手机扫描相应的二维码得到（每个二维码所包含的信息是根据柱子的相关信息而生成）。根据两个点（柱子信息）及描述文件计算最短线路的步骤如下：

1） 确定两个点person、car（它们包含了柱子的相关信息）及停车场地图描述文件，

2） 定义图的邻接矩阵matrix及图的点集合points和边集合lines

3） 解析停车场描述文件，根据point元素初始化图的点集，根据line元素初始化图的边集

4） 将点person添加到点集中作为点集的第一个元素，同时根据点坐标及其所属线路line_person计算点person到线line_person之间的垂线段并将该垂线段添加的图的边集中

5） 将点car添加到点集中作为点集的最后一个元素，同时根据点坐标及其所属线路line_car计算点car到线line_car之间的垂线段并将该垂线段添加的图的边集中

6） 根据图的点集合points和边集合lines初始化图的邻接矩阵matrix，线路的长度作为图中边的权值

7） 使用一种最短路径计算方法（如迪杰斯特拉算法）计算从起始点（person作为起始点）到终止点（car作为终止点）的最短路径，最短路径上的点存储在一个数组result_path中。

3 实验结果

针对上述地图设计，该文设计并实现的停车场反向寻车软件对上述地图设计进行了验证。该软件需要运行在手机上，并要求手机具有摄像头功能，本测试手机为华为荣耀3C Android[7-9]平台手机。该文分别就起始点、终止点在同一停车楼层和起始点、终止点在不同停车楼层进行了验证，试验时起始点和终止点均为随机选取并进行了多次试验。实验结果展示分别如图3和图4。

4 结论

本文提出了一种适用于反向寻车的停车场地图设计，该设计主要是地图描述文件的设计，该地图描述文件可以转化为图的模型。结合二维码存储停车场柱子位置信息，本设计能够通过手机计算并展示车主位置和停车位置之间的最短线路，从而可以有效地解决大型停车场车主用户找车难问题。

参考文献：

[1] 王扬，薛娟.智能停车场反向寻车系统设计与实现[J].无线互联科技，2012（11）.

[2] 樊勇，任燕，司博章.一种新型停车场反向寻车系统[J].物联网技术，2013（2）.

[3] 科拓.车位引导|反向寻车[EB/OL].http：//www.keytop.com.cn/

[4] 刘小晶，杜选.数据结构（java语言描述）[M].北京：清华大学出版社，2011：192-232.

[5] 王桂平，王衍，任嘉辰.图论算法理论、实现及应用[M].北京；北京大学出版社，2011.

[6] W3C. XML教程[EB/OL].http：//www.w3school.com.cn/xml/.

[7] 王雅宁.轻松学android开发[M].北京：电子工业出版社，2013：1-331.

[8] Google. Android[EB/OL].http：//developer.android.com/index.html.

[9] 李宁. Android/Ophne开发完全讲义[M].北京：中国水利水电出版社，2010.endprint

摘要：针对综合体地下停车场空间庞大、结构复杂等特点，停车、寻车已成为制约车主消费体验的瓶颈，提出了一种面向地下停车场地图结构设计方案，能够实现多层停车场图形抽象为一个图模型，基于图模型能够快速计算寻车的有效最短路径。设计方案集成于手机反向寻车软件，并通过实际部署的案例，验证地图结构设计的有效性和准确性。

关键词：停车场；反向寻车；最短路径；二维码；寻车软件

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2014）36-8692-03

随着社会的进步、经济的发展，城市中大型商场、购物中心等不断出现，其停车场规模也不断扩大。由于停车场内空间大、环境及标志物类似、方向不易辨别，车主在返回停车场找车时，往往迷失方向，找不到自己的车辆。这不仅让用户浪费了宝贵的时间，降低了用户在停车场的体验，也降低了停车场的周转效率。因此大型停车场找车难问题成为近几年人们不断研究和急需解决的问题。

近年来人们一直对停车场反向寻车[1][2]方法进行着不停地探索，并且已取得了一定的效果。目前主要解决方案有刷卡定位方式、条形码取票定位方式、视频识别定位方式[3]、指纹识别方式等。这几种反向寻车方式都有一些缺点，刷卡定位、条形码取票、指纹识别方式都需要车主用户在特定的地方记录位置信息并拥有或者索取位置凭证，视频设别方式需要在停车场每个车位旁安装一个视频设别装置，实施成本极高。此外，车主寻车时，必须在指定的寻车终端查询车辆车位信息，不能随行随找，使用效果不是很理想。该文提出的停车场地图设计能够很容易的转化为图[4][5]的模型，从而为停车场反向寻车提供一种更好的解决方案。

1 地图设计

停车场通常包括若干停车楼层，每个停车楼层中有若干线路、柱子、停车位、电梯或楼梯出入口等。本设计中停车场地图包含以下内容：各个停车楼层的图片文件（每个停车楼层一个图片；该图片展现了相应停车楼层的结构）、整个停车场地图描述文件（XML[6]格式的文件）；一系列二维码信息文件（二维码存储停车场地图描述文件中柱子相关信息，通过二维码可以确定停车场中的柱子，通常由寻车软件读取并使用）。停车场地图描述文件描述了每个停车楼层及其大小、每个停车楼层包含的线路、各个线路之间的交叉点、每个楼层中的车位或者柱子（本设计采用柱子）、各个停车楼层之间的关联点。

在根据地图描述文件构造图时，线路交叉点作为图的节点、线路（两个交叉点之间的部分）作为图的边。由于停车场中柱子点很多，如果将每个柱子都视为一个位置点放在模型图中的点集中，那么构造的图的顶点数和边数会非常多，增加计算的复杂度。本设计中柱子点不包括在图的点集中，而是在计算两个位置（柱子）之间的最短路径时，柱子动态添加到图的点集中，与柱子相关的边动态添加到图的边集中，从而有效地减少了图的点数和边数，降低了计算的复杂度。

楼层图片文件片段和地图描述文件片段分别如图1和图2。

1.1 地图描述文件详细描述

根元素park表示一个停车场，width和height属性分别表示停车场长度和宽度，停车场各个楼层长度和宽度通常一样。元素floor表示停车场中的一个停车楼层，每个停车楼层有一个唯一标示id，停车楼层内有lines、points和pillars，分别表示线路集合、线路的交叉点集合和柱子集合。每个交叉点元素point有唯一标示id、x坐标和y坐标（在楼层图片文件中的横纵坐标），每个线路元素line有唯一标示id、线路长度length、线路的起始点和终止点，每个柱子元素pillar有一个唯一标示id、柱子的x坐标和y坐标（在楼层图片文件中的横纵坐标）和该柱子所属的线路（距离该柱子最近的线路），元素relation表示两个停车楼层之间的连接线路，连接的端点为某楼层上的某个点。

此外柱子还有一些描述信息message，该信息描述了此柱子的位置坐标和所属的线路。该信息可以用于外部使用（如对其生成二维码贴于实际停车场中对应的柱子上，通过手机扫描二维码即可获得该柱子的相关信息）。

通过地图描述文件，我们可以将停车场结构抽象为图的模型，进而可以计算任意两点之间的最短路径，结合地图文件将最优线路展示给车主用户。

2 基于地图文件计算最短线路

本文地图文件是针对于停车场反向停车而设计的。反向寻车核心即为确定车主与车的位置及车主位置到车位置之间的最短线路的计算。确定了停车场中的两个点以后既可以根据停车场地图描述文件计算两点之间的最短线路。停车场中两个点通常由车主用户使用手机扫描相应的二维码得到（每个二维码所包含的信息是根据柱子的相关信息而生成）。根据两个点（柱子信息）及描述文件计算最短线路的步骤如下：

1） 确定两个点person、car（它们包含了柱子的相关信息）及停车场地图描述文件，

2） 定义图的邻接矩阵matrix及图的点集合points和边集合lines

3） 解析停车场描述文件，根据point元素初始化图的点集，根据line元素初始化图的边集

4） 将点person添加到点集中作为点集的第一个元素，同时根据点坐标及其所属线路line_person计算点person到线line_person之间的垂线段并将该垂线段添加的图的边集中

5） 将点car添加到点集中作为点集的最后一个元素，同时根据点坐标及其所属线路line_car计算点car到线line_car之间的垂线段并将该垂线段添加的图的边集中

6） 根据图的点集合points和边集合lines初始化图的邻接矩阵matrix，线路的长度作为图中边的权值

7） 使用一种最短路径计算方法（如迪杰斯特拉算法）计算从起始点（person作为起始点）到终止点（car作为终止点）的最短路径，最短路径上的点存储在一个数组result_path中。

3 实验结果

针对上述地图设计，该文设计并实现的停车场反向寻车软件对上述地图设计进行了验证。该软件需要运行在手机上，并要求手机具有摄像头功能，本测试手机为华为荣耀3C Android[7-9]平台手机。该文分别就起始点、终止点在同一停车楼层和起始点、终止点在不同停车楼层进行了验证，试验时起始点和终止点均为随机选取并进行了多次试验。实验结果展示分别如图3和图4。

4 结论

本文提出了一种适用于反向寻车的停车场地图设计，该设计主要是地图描述文件的设计，该地图描述文件可以转化为图的模型。结合二维码存储停车场柱子位置信息，本设计能够通过手机计算并展示车主位置和停车位置之间的最短线路，从而可以有效地解决大型停车场车主用户找车难问题。

参考文献：

[1] 王扬，薛娟.智能停车场反向寻车系统设计与实现[J].无线互联科技，2012（11）.

[2] 樊勇，任燕，司博章.一种新型停车场反向寻车系统[J].物联网技术，2013（2）.

[3] 科拓.车位引导|反向寻车[EB/OL].http：//www.keytop.com.cn/

[4] 刘小晶，杜选.数据结构（java语言描述）[M].北京：清华大学出版社，2011：192-232.

[5] 王桂平，王衍，任嘉辰.图论算法理论、实现及应用[M].北京；北京大学出版社，2011.

[6] W3C. XML教程[EB/OL].http：//www.w3school.com.cn/xml/.

[7] 王雅宁.轻松学android开发[M].北京：电子工业出版社，2013：1-331.

[8] Google. Android[EB/OL].http：//developer.android.com/index.html.

[9] 李宁. Android/Ophne开发完全讲义[M].北京：中国水利水电出版社，2010.endprint