適用于反向?qū)ぼ嚨耐＼噲?chǎng)地圖設(shè)計(jì)

馮小剛　杜軍威

摘要：針對(duì)綜合體地下停車場(chǎng)空間龐大、結(jié)構(gòu)復(fù)雜等特點(diǎn)，停車、尋車已成為制約車主消費(fèi)體驗(yàn)的瓶頸，提出了一種面向地下停車場(chǎng)地圖結(jié)構(gòu)設(shè)計(jì)方案，能夠?qū)崿F(xiàn)多層停車場(chǎng)圖形抽象為一個(gè)圖模型，基于圖模型能夠快速計(jì)算尋車的有效最短路徑。設(shè)計(jì)方案集成于手機(jī)反向?qū)ぼ囓浖?，并通過(guò)實(shí)際部署的案例，驗(yàn)證地圖結(jié)構(gòu)設(shè)計(jì)的有效性和準(zhǔn)確性。

關(guān)鍵詞：停車場(chǎng)；反向?qū)ぼ?；最短路徑；二維碼；尋車軟件

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）36-8692-03

隨著社會(huì)的進(jìn)步、經(jīng)濟(jì)的發(fā)展，城市中大型商場(chǎng)、購(gòu)物中心等不斷出現(xiàn)，其停車場(chǎng)規(guī)模也不斷擴(kuò)大。由于停車場(chǎng)內(nèi)空間大、環(huán)境及標(biāo)志物類似、方向不易辨別，車主在返回停車場(chǎng)找車時(shí)，往往迷失方向，找不到自己的車輛。這不僅讓用戶浪費(fèi)了寶貴的時(shí)間，降低了用戶在停車場(chǎng)的體驗(yàn)，也降低了停車場(chǎng)的周轉(zhuǎn)效率。因此大型停車場(chǎng)找車難問(wèn)題成為近幾年人們不斷研究和急需解決的問(wèn)題。

近年來(lái)人們一直對(duì)停車場(chǎng)反向?qū)ぼ嘯1][2]方法進(jìn)行著不停地探索，并且已取得了一定的效果。目前主要解決方案有刷卡定位方式、條形碼取票定位方式、視頻識(shí)別定位方式[3]、指紋識(shí)別方式等。這幾種反向?qū)ぼ嚪绞蕉加幸恍┤秉c(diǎn)，刷卡定位、條形碼取票、指紋識(shí)別方式都需要車主用戶在特定的地方記錄位置信息并擁有或者索取位置憑證，視頻設(shè)別方式需要在停車場(chǎng)每個(gè)車位旁安裝一個(gè)視頻設(shè)別裝置，實(shí)施成本極高。此外，車主尋車時(shí)，必須在指定的尋車終端查詢車輛車位信息，不能隨行隨找，使用效果不是很理想。該文提出的停車場(chǎng)地圖設(shè)計(jì)能夠很容易的轉(zhuǎn)化為圖[4][5]的模型，從而為停車場(chǎng)反向?qū)ぼ囂峁┮环N更好的解決方案。

1 地圖設(shè)計(jì)

停車場(chǎng)通常包括若干停車樓層，每個(gè)停車樓層中有若干線路、柱子、停車位、電梯或樓梯出入口等。本設(shè)計(jì)中停車場(chǎng)地圖包含以下內(nèi)容：各個(gè)停車樓層的圖片文件（每個(gè)停車樓層一個(gè)圖片；該圖片展現(xiàn)了相應(yīng)停車樓層的結(jié)構(gòu)）、整個(gè)停車場(chǎng)地圖描述文件（XML[6]格式的文件）；一系列二維碼信息文件（二維碼存儲(chǔ)停車場(chǎng)地圖描述文件中柱子相關(guān)信息，通過(guò)二維碼可以確定停車場(chǎng)中的柱子，通常由尋車軟件讀取并使用）。停車場(chǎng)地圖描述文件描述了每個(gè)停車樓層及其大小、每個(gè)停車樓層包含的線路、各個(gè)線路之間的交叉點(diǎn)、每個(gè)樓層中的車位或者柱子（本設(shè)計(jì)采用柱子）、各個(gè)停車樓層之間的關(guān)聯(lián)點(diǎn)。

在根據(jù)地圖描述文件構(gòu)造圖時(shí)，線路交叉點(diǎn)作為圖的節(jié)點(diǎn)、線路（兩個(gè)交叉點(diǎn)之間的部分）作為圖的邊。由于停車場(chǎng)中柱子點(diǎn)很多，如果將每個(gè)柱子都視為一個(gè)位置點(diǎn)放在模型圖中的點(diǎn)集中，那么構(gòu)造的圖的頂點(diǎn)數(shù)和邊數(shù)會(huì)非常多，增加計(jì)算的復(fù)雜度。本設(shè)計(jì)中柱子點(diǎn)不包括在圖的點(diǎn)集中，而是在計(jì)算兩個(gè)位置（柱子）之間的最短路徑時(shí)，柱子動(dòng)態(tài)添加到圖的點(diǎn)集中，與柱子相關(guān)的邊動(dòng)態(tài)添加到圖的邊集中，從而有效地減少了圖的點(diǎn)數(shù)和邊數(shù)，降低了計(jì)算的復(fù)雜度。

樓層圖片文件片段和地圖描述文件片段分別如圖1和圖2。

1.1 地圖描述文件詳細(xì)描述

根元素park表示一個(gè)停車場(chǎng)，width和height屬性分別表示停車場(chǎng)長(zhǎng)度和寬度，停車場(chǎng)各個(gè)樓層長(zhǎng)度和寬度通常一樣。元素floor表示停車場(chǎng)中的一個(gè)停車樓層，每個(gè)停車樓層有一個(gè)唯一標(biāo)示id，停車樓層內(nèi)有l(wèi)ines、points和pillars，分別表示線路集合、線路的交叉點(diǎn)集合和柱子集合。每個(gè)交叉點(diǎn)元素point有唯一標(biāo)示id、x坐標(biāo)和y坐標(biāo)（在樓層圖片文件中的橫縱坐標(biāo)），每個(gè)線路元素line有唯一標(biāo)示id、線路長(zhǎng)度length、線路的起始點(diǎn)和終止點(diǎn)，每個(gè)柱子元素pillar有一個(gè)唯一標(biāo)示id、柱子的x坐標(biāo)和y坐標(biāo)（在樓層圖片文件中的橫縱坐標(biāo)）和該柱子所屬的線路（距離該柱子最近的線路），元素relation表示兩個(gè)停車樓層之間的連接線路，連接的端點(diǎn)為某樓層上的某個(gè)點(diǎn)。

此外柱子還有一些描述信息message，該信息描述了此柱子的位置坐標(biāo)和所屬的線路。該信息可以用于外部使用（如對(duì)其生成二維碼貼于實(shí)際停車場(chǎng)中對(duì)應(yīng)的柱子上，通過(guò)手機(jī)掃描二維碼即可獲得該柱子的相關(guān)信息）。

通過(guò)地圖描述文件，我們可以將停車場(chǎng)結(jié)構(gòu)抽象為圖的模型，進(jìn)而可以計(jì)算任意兩點(diǎn)之間的最短路徑，結(jié)合地圖文件將最優(yōu)線路展示給車主用戶。

2 基于地圖文件計(jì)算最短線路

本文地圖文件是針對(duì)于停車場(chǎng)反向停車而設(shè)計(jì)的。反向?qū)ぼ嚭诵募礊榇_定車主與車的位置及車主位置到車位置之間的最短線路的計(jì)算。確定了停車場(chǎng)中的兩個(gè)點(diǎn)以后既可以根據(jù)停車場(chǎng)地圖描述文件計(jì)算兩點(diǎn)之間的最短線路。停車場(chǎng)中兩個(gè)點(diǎn)通常由車主用戶使用手機(jī)掃描相應(yīng)的二維碼得到（每個(gè)二維碼所包含的信息是根據(jù)柱子的相關(guān)信息而生成）。根據(jù)兩個(gè)點(diǎn)（柱子信息）及描述文件計(jì)算最短線路的步驟如下：

1） 確定兩個(gè)點(diǎn)person、car（它們包含了柱子的相關(guān)信息）及停車場(chǎng)地圖描述文件，

2） 定義圖的鄰接矩陣matrix及圖的點(diǎn)集合points和邊集合lines

3） 解析停車場(chǎng)描述文件，根據(jù)point元素初始化圖的點(diǎn)集，根據(jù)line元素初始化圖的邊集

4） 將點(diǎn)person添加到點(diǎn)集中作為點(diǎn)集的第一個(gè)元素，同時(shí)根據(jù)點(diǎn)坐標(biāo)及其所屬線路line_person計(jì)算點(diǎn)person到線line_person之間的垂線段并將該垂線段添加的圖的邊集中

5） 將點(diǎn)car添加到點(diǎn)集中作為點(diǎn)集的最后一個(gè)元素，同時(shí)根據(jù)點(diǎn)坐標(biāo)及其所屬線路line_car計(jì)算點(diǎn)car到線line_car之間的垂線段并將該垂線段添加的圖的邊集中

6） 根據(jù)圖的點(diǎn)集合points和邊集合lines初始化圖的鄰接矩陣matrix，線路的長(zhǎng)度作為圖中邊的權(quán)值

7） 使用一種最短路徑計(jì)算方法（如迪杰斯特拉算法）計(jì)算從起始點(diǎn)（person作為起始點(diǎn)）到終止點(diǎn)（car作為終止點(diǎn)）的最短路徑，最短路徑上的點(diǎn)存儲(chǔ)在一個(gè)數(shù)組result_path中。

3 實(shí)驗(yàn)結(jié)果

針對(duì)上述地圖設(shè)計(jì)，該文設(shè)計(jì)并實(shí)現(xiàn)的停車場(chǎng)反向?qū)ぼ囓浖?duì)上述地圖設(shè)計(jì)進(jìn)行了驗(yàn)證。該軟件需要運(yùn)行在手機(jī)上，并要求手機(jī)具有攝像頭功能，本測(cè)試手機(jī)為華為榮耀3C Android[7-9]平臺(tái)手機(jī)。該文分別就起始點(diǎn)、終止點(diǎn)在同一停車樓層和起始點(diǎn)、終止點(diǎn)在不同停車樓層進(jìn)行了驗(yàn)證，試驗(yàn)時(shí)起始點(diǎn)和終止點(diǎn)均為隨機(jī)選取并進(jìn)行了多次試驗(yàn)。實(shí)驗(yàn)結(jié)果展示分別如圖3和圖4。

4 結(jié)論

本文提出了一種適用于反向?qū)ぼ嚨耐＼噲?chǎng)地圖設(shè)計(jì)，該設(shè)計(jì)主要是地圖描述文件的設(shè)計(jì)，該地圖描述文件可以轉(zhuǎn)化為圖的模型。結(jié)合二維碼存儲(chǔ)停車場(chǎng)柱子位置信息，本設(shè)計(jì)能夠通過(guò)手機(jī)計(jì)算并展示車主位置和停車位置之間的最短線路，從而可以有效地解決大型停車場(chǎng)車主用戶找車難問(wèn)題。

參考文獻(xiàn)：

[1] 王揚(yáng)，薛娟.智能停車場(chǎng)反向?qū)ぼ囅到y(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].無(wú)線互聯(lián)科技，2012（11）.

[2] 樊勇，任燕，司博章.一種新型停車場(chǎng)反向?qū)ぼ囅到y(tǒng)[J].物聯(lián)網(wǎng)技術(shù)，2013（2）.

[3] 科拓.車位引導(dǎo)|反向?qū)ぼ嘯EB/OL].http：//www.keytop.com.cn/

[4] 劉小晶，杜選.數(shù)據(jù)結(jié)構(gòu)（java語(yǔ)言描述）[M].北京：清華大學(xué)出版社，2011：192-232.

[5] 王桂平，王衍，任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京；北京大學(xué)出版社，2011.

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

[7] 王雅寧.輕松學(xué)android開發(fā)[M].北京：電子工業(yè)出版社，2013：1-331.

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

[9] 李寧. Android/Ophne開發(fā)完全講義[M].北京：中國(guó)水利水電出版社，2010.endprint

摘要：針對(duì)綜合體地下停車場(chǎng)空間龐大、結(jié)構(gòu)復(fù)雜等特點(diǎn)，停車、尋車已成為制約車主消費(fèi)體驗(yàn)的瓶頸，提出了一種面向地下停車場(chǎng)地圖結(jié)構(gòu)設(shè)計(jì)方案，能夠?qū)崿F(xiàn)多層停車場(chǎng)圖形抽象為一個(gè)圖模型，基于圖模型能夠快速計(jì)算尋車的有效最短路徑。設(shè)計(jì)方案集成于手機(jī)反向?qū)ぼ囓浖?，并通過(guò)實(shí)際部署的案例，驗(yàn)證地圖結(jié)構(gòu)設(shè)計(jì)的有效性和準(zhǔn)確性。

關(guān)鍵詞：停車場(chǎng)；反向?qū)ぼ?；最短路徑；二維碼；尋車軟件

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）36-8692-03

隨著社會(huì)的進(jìn)步、經(jīng)濟(jì)的發(fā)展，城市中大型商場(chǎng)、購(gòu)物中心等不斷出現(xiàn)，其停車場(chǎng)規(guī)模也不斷擴(kuò)大。由于停車場(chǎng)內(nèi)空間大、環(huán)境及標(biāo)志物類似、方向不易辨別，車主在返回停車場(chǎng)找車時(shí)，往往迷失方向，找不到自己的車輛。這不僅讓用戶浪費(fèi)了寶貴的時(shí)間，降低了用戶在停車場(chǎng)的體驗(yàn)，也降低了停車場(chǎng)的周轉(zhuǎn)效率。因此大型停車場(chǎng)找車難問(wèn)題成為近幾年人們不斷研究和急需解決的問(wèn)題。

近年來(lái)人們一直對(duì)停車場(chǎng)反向?qū)ぼ嘯1][2]方法進(jìn)行著不停地探索，并且已取得了一定的效果。目前主要解決方案有刷卡定位方式、條形碼取票定位方式、視頻識(shí)別定位方式[3]、指紋識(shí)別方式等。這幾種反向?qū)ぼ嚪绞蕉加幸恍┤秉c(diǎn)，刷卡定位、條形碼取票、指紋識(shí)別方式都需要車主用戶在特定的地方記錄位置信息并擁有或者索取位置憑證，視頻設(shè)別方式需要在停車場(chǎng)每個(gè)車位旁安裝一個(gè)視頻設(shè)別裝置，實(shí)施成本極高。此外，車主尋車時(shí)，必須在指定的尋車終端查詢車輛車位信息，不能隨行隨找，使用效果不是很理想。該文提出的停車場(chǎng)地圖設(shè)計(jì)能夠很容易的轉(zhuǎn)化為圖[4][5]的模型，從而為停車場(chǎng)反向?qū)ぼ囂峁┮环N更好的解決方案。

1 地圖設(shè)計(jì)

停車場(chǎng)通常包括若干停車樓層，每個(gè)停車樓層中有若干線路、柱子、停車位、電梯或樓梯出入口等。本設(shè)計(jì)中停車場(chǎng)地圖包含以下內(nèi)容：各個(gè)停車樓層的圖片文件（每個(gè)停車樓層一個(gè)圖片；該圖片展現(xiàn)了相應(yīng)停車樓層的結(jié)構(gòu)）、整個(gè)停車場(chǎng)地圖描述文件（XML[6]格式的文件）；一系列二維碼信息文件（二維碼存儲(chǔ)停車場(chǎng)地圖描述文件中柱子相關(guān)信息，通過(guò)二維碼可以確定停車場(chǎng)中的柱子，通常由尋車軟件讀取并使用）。停車場(chǎng)地圖描述文件描述了每個(gè)停車樓層及其大小、每個(gè)停車樓層包含的線路、各個(gè)線路之間的交叉點(diǎn)、每個(gè)樓層中的車位或者柱子（本設(shè)計(jì)采用柱子）、各個(gè)停車樓層之間的關(guān)聯(lián)點(diǎn)。

在根據(jù)地圖描述文件構(gòu)造圖時(shí)，線路交叉點(diǎn)作為圖的節(jié)點(diǎn)、線路（兩個(gè)交叉點(diǎn)之間的部分）作為圖的邊。由于停車場(chǎng)中柱子點(diǎn)很多，如果將每個(gè)柱子都視為一個(gè)位置點(diǎn)放在模型圖中的點(diǎn)集中，那么構(gòu)造的圖的頂點(diǎn)數(shù)和邊數(shù)會(huì)非常多，增加計(jì)算的復(fù)雜度。本設(shè)計(jì)中柱子點(diǎn)不包括在圖的點(diǎn)集中，而是在計(jì)算兩個(gè)位置（柱子）之間的最短路徑時(shí)，柱子動(dòng)態(tài)添加到圖的點(diǎn)集中，與柱子相關(guān)的邊動(dòng)態(tài)添加到圖的邊集中，從而有效地減少了圖的點(diǎn)數(shù)和邊數(shù)，降低了計(jì)算的復(fù)雜度。

樓層圖片文件片段和地圖描述文件片段分別如圖1和圖2。

1.1 地圖描述文件詳細(xì)描述

根元素park表示一個(gè)停車場(chǎng)，width和height屬性分別表示停車場(chǎng)長(zhǎng)度和寬度，停車場(chǎng)各個(gè)樓層長(zhǎng)度和寬度通常一樣。元素floor表示停車場(chǎng)中的一個(gè)停車樓層，每個(gè)停車樓層有一個(gè)唯一標(biāo)示id，停車樓層內(nèi)有l(wèi)ines、points和pillars，分別表示線路集合、線路的交叉點(diǎn)集合和柱子集合。每個(gè)交叉點(diǎn)元素point有唯一標(biāo)示id、x坐標(biāo)和y坐標(biāo)（在樓層圖片文件中的橫縱坐標(biāo)），每個(gè)線路元素line有唯一標(biāo)示id、線路長(zhǎng)度length、線路的起始點(diǎn)和終止點(diǎn)，每個(gè)柱子元素pillar有一個(gè)唯一標(biāo)示id、柱子的x坐標(biāo)和y坐標(biāo)（在樓層圖片文件中的橫縱坐標(biāo)）和該柱子所屬的線路（距離該柱子最近的線路），元素relation表示兩個(gè)停車樓層之間的連接線路，連接的端點(diǎn)為某樓層上的某個(gè)點(diǎn)。

此外柱子還有一些描述信息message，該信息描述了此柱子的位置坐標(biāo)和所屬的線路。該信息可以用于外部使用（如對(duì)其生成二維碼貼于實(shí)際停車場(chǎng)中對(duì)應(yīng)的柱子上，通過(guò)手機(jī)掃描二維碼即可獲得該柱子的相關(guān)信息）。

通過(guò)地圖描述文件，我們可以將停車場(chǎng)結(jié)構(gòu)抽象為圖的模型，進(jìn)而可以計(jì)算任意兩點(diǎn)之間的最短路徑，結(jié)合地圖文件將最優(yōu)線路展示給車主用戶。

2 基于地圖文件計(jì)算最短線路

本文地圖文件是針對(duì)于停車場(chǎng)反向停車而設(shè)計(jì)的。反向?qū)ぼ嚭诵募礊榇_定車主與車的位置及車主位置到車位置之間的最短線路的計(jì)算。確定了停車場(chǎng)中的兩個(gè)點(diǎn)以后既可以根據(jù)停車場(chǎng)地圖描述文件計(jì)算兩點(diǎn)之間的最短線路。停車場(chǎng)中兩個(gè)點(diǎn)通常由車主用戶使用手機(jī)掃描相應(yīng)的二維碼得到（每個(gè)二維碼所包含的信息是根據(jù)柱子的相關(guān)信息而生成）。根據(jù)兩個(gè)點(diǎn)（柱子信息）及描述文件計(jì)算最短線路的步驟如下：

1） 確定兩個(gè)點(diǎn)person、car（它們包含了柱子的相關(guān)信息）及停車場(chǎng)地圖描述文件，

2） 定義圖的鄰接矩陣matrix及圖的點(diǎn)集合points和邊集合lines

3） 解析停車場(chǎng)描述文件，根據(jù)point元素初始化圖的點(diǎn)集，根據(jù)line元素初始化圖的邊集

4） 將點(diǎn)person添加到點(diǎn)集中作為點(diǎn)集的第一個(gè)元素，同時(shí)根據(jù)點(diǎn)坐標(biāo)及其所屬線路line_person計(jì)算點(diǎn)person到線line_person之間的垂線段并將該垂線段添加的圖的邊集中

5） 將點(diǎn)car添加到點(diǎn)集中作為點(diǎn)集的最后一個(gè)元素，同時(shí)根據(jù)點(diǎn)坐標(biāo)及其所屬線路line_car計(jì)算點(diǎn)car到線line_car之間的垂線段并將該垂線段添加的圖的邊集中

6） 根據(jù)圖的點(diǎn)集合points和邊集合lines初始化圖的鄰接矩陣matrix，線路的長(zhǎng)度作為圖中邊的權(quán)值

7） 使用一種最短路徑計(jì)算方法（如迪杰斯特拉算法）計(jì)算從起始點(diǎn)（person作為起始點(diǎn)）到終止點(diǎn)（car作為終止點(diǎn)）的最短路徑，最短路徑上的點(diǎn)存儲(chǔ)在一個(gè)數(shù)組result_path中。

3 實(shí)驗(yàn)結(jié)果

針對(duì)上述地圖設(shè)計(jì)，該文設(shè)計(jì)并實(shí)現(xiàn)的停車場(chǎng)反向?qū)ぼ囓浖?duì)上述地圖設(shè)計(jì)進(jìn)行了驗(yàn)證。該軟件需要運(yùn)行在手機(jī)上，并要求手機(jī)具有攝像頭功能，本測(cè)試手機(jī)為華為榮耀3C Android[7-9]平臺(tái)手機(jī)。該文分別就起始點(diǎn)、終止點(diǎn)在同一停車樓層和起始點(diǎn)、終止點(diǎn)在不同停車樓層進(jìn)行了驗(yàn)證，試驗(yàn)時(shí)起始點(diǎn)和終止點(diǎn)均為隨機(jī)選取并進(jìn)行了多次試驗(yàn)。實(shí)驗(yàn)結(jié)果展示分別如圖3和圖4。

4 結(jié)論

本文提出了一種適用于反向?qū)ぼ嚨耐＼噲?chǎng)地圖設(shè)計(jì)，該設(shè)計(jì)主要是地圖描述文件的設(shè)計(jì)，該地圖描述文件可以轉(zhuǎn)化為圖的模型。結(jié)合二維碼存儲(chǔ)停車場(chǎng)柱子位置信息，本設(shè)計(jì)能夠通過(guò)手機(jī)計(jì)算并展示車主位置和停車位置之間的最短線路，從而可以有效地解決大型停車場(chǎng)車主用戶找車難問(wèn)題。

參考文獻(xiàn)：

[1] 王揚(yáng)，薛娟.智能停車場(chǎng)反向?qū)ぼ囅到y(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].無(wú)線互聯(lián)科技，2012（11）.

[2] 樊勇，任燕，司博章.一種新型停車場(chǎng)反向?qū)ぼ囅到y(tǒng)[J].物聯(lián)網(wǎng)技術(shù)，2013（2）.

[3] 科拓.車位引導(dǎo)|反向?qū)ぼ嘯EB/OL].http：//www.keytop.com.cn/

[4] 劉小晶，杜選.數(shù)據(jù)結(jié)構(gòu)（java語(yǔ)言描述）[M].北京：清華大學(xué)出版社，2011：192-232.

[5] 王桂平，王衍，任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京；北京大學(xué)出版社，2011.

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

[7] 王雅寧.輕松學(xué)android開發(fā)[M].北京：電子工業(yè)出版社，2013：1-331.

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

[9] 李寧. Android/Ophne開發(fā)完全講義[M].北京：中國(guó)水利水電出版社，2010.endprint

摘要：針對(duì)綜合體地下停車場(chǎng)空間龐大、結(jié)構(gòu)復(fù)雜等特點(diǎn)，停車、尋車已成為制約車主消費(fèi)體驗(yàn)的瓶頸，提出了一種面向地下停車場(chǎng)地圖結(jié)構(gòu)設(shè)計(jì)方案，能夠?qū)崿F(xiàn)多層停車場(chǎng)圖形抽象為一個(gè)圖模型，基于圖模型能夠快速計(jì)算尋車的有效最短路徑。設(shè)計(jì)方案集成于手機(jī)反向?qū)ぼ囓浖?，并通過(guò)實(shí)際部署的案例，驗(yàn)證地圖結(jié)構(gòu)設(shè)計(jì)的有效性和準(zhǔn)確性。

關(guān)鍵詞：停車場(chǎng)；反向?qū)ぼ?；最短路徑；二維碼；尋車軟件

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）36-8692-03

隨著社會(huì)的進(jìn)步、經(jīng)濟(jì)的發(fā)展，城市中大型商場(chǎng)、購(gòu)物中心等不斷出現(xiàn)，其停車場(chǎng)規(guī)模也不斷擴(kuò)大。由于停車場(chǎng)內(nèi)空間大、環(huán)境及標(biāo)志物類似、方向不易辨別，車主在返回停車場(chǎng)找車時(shí)，往往迷失方向，找不到自己的車輛。這不僅讓用戶浪費(fèi)了寶貴的時(shí)間，降低了用戶在停車場(chǎng)的體驗(yàn)，也降低了停車場(chǎng)的周轉(zhuǎn)效率。因此大型停車場(chǎng)找車難問(wèn)題成為近幾年人們不斷研究和急需解決的問(wèn)題。

近年來(lái)人們一直對(duì)停車場(chǎng)反向?qū)ぼ嘯1][2]方法進(jìn)行著不停地探索，并且已取得了一定的效果。目前主要解決方案有刷卡定位方式、條形碼取票定位方式、視頻識(shí)別定位方式[3]、指紋識(shí)別方式等。這幾種反向?qū)ぼ嚪绞蕉加幸恍┤秉c(diǎn)，刷卡定位、條形碼取票、指紋識(shí)別方式都需要車主用戶在特定的地方記錄位置信息并擁有或者索取位置憑證，視頻設(shè)別方式需要在停車場(chǎng)每個(gè)車位旁安裝一個(gè)視頻設(shè)別裝置，實(shí)施成本極高。此外，車主尋車時(shí)，必須在指定的尋車終端查詢車輛車位信息，不能隨行隨找，使用效果不是很理想。該文提出的停車場(chǎng)地圖設(shè)計(jì)能夠很容易的轉(zhuǎn)化為圖[4][5]的模型，從而為停車場(chǎng)反向?qū)ぼ囂峁┮环N更好的解決方案。

1 地圖設(shè)計(jì)

停車場(chǎng)通常包括若干停車樓層，每個(gè)停車樓層中有若干線路、柱子、停車位、電梯或樓梯出入口等。本設(shè)計(jì)中停車場(chǎng)地圖包含以下內(nèi)容：各個(gè)停車樓層的圖片文件（每個(gè)停車樓層一個(gè)圖片；該圖片展現(xiàn)了相應(yīng)停車樓層的結(jié)構(gòu)）、整個(gè)停車場(chǎng)地圖描述文件（XML[6]格式的文件）；一系列二維碼信息文件（二維碼存儲(chǔ)停車場(chǎng)地圖描述文件中柱子相關(guān)信息，通過(guò)二維碼可以確定停車場(chǎng)中的柱子，通常由尋車軟件讀取并使用）。停車場(chǎng)地圖描述文件描述了每個(gè)停車樓層及其大小、每個(gè)停車樓層包含的線路、各個(gè)線路之間的交叉點(diǎn)、每個(gè)樓層中的車位或者柱子（本設(shè)計(jì)采用柱子）、各個(gè)停車樓層之間的關(guān)聯(lián)點(diǎn)。

在根據(jù)地圖描述文件構(gòu)造圖時(shí)，線路交叉點(diǎn)作為圖的節(jié)點(diǎn)、線路（兩個(gè)交叉點(diǎn)之間的部分）作為圖的邊。由于停車場(chǎng)中柱子點(diǎn)很多，如果將每個(gè)柱子都視為一個(gè)位置點(diǎn)放在模型圖中的點(diǎn)集中，那么構(gòu)造的圖的頂點(diǎn)數(shù)和邊數(shù)會(huì)非常多，增加計(jì)算的復(fù)雜度。本設(shè)計(jì)中柱子點(diǎn)不包括在圖的點(diǎn)集中，而是在計(jì)算兩個(gè)位置（柱子）之間的最短路徑時(shí)，柱子動(dòng)態(tài)添加到圖的點(diǎn)集中，與柱子相關(guān)的邊動(dòng)態(tài)添加到圖的邊集中，從而有效地減少了圖的點(diǎn)數(shù)和邊數(shù)，降低了計(jì)算的復(fù)雜度。

樓層圖片文件片段和地圖描述文件片段分別如圖1和圖2。

1.1 地圖描述文件詳細(xì)描述

根元素park表示一個(gè)停車場(chǎng)，width和height屬性分別表示停車場(chǎng)長(zhǎng)度和寬度，停車場(chǎng)各個(gè)樓層長(zhǎng)度和寬度通常一樣。元素floor表示停車場(chǎng)中的一個(gè)停車樓層，每個(gè)停車樓層有一個(gè)唯一標(biāo)示id，停車樓層內(nèi)有l(wèi)ines、points和pillars，分別表示線路集合、線路的交叉點(diǎn)集合和柱子集合。每個(gè)交叉點(diǎn)元素point有唯一標(biāo)示id、x坐標(biāo)和y坐標(biāo)（在樓層圖片文件中的橫縱坐標(biāo)），每個(gè)線路元素line有唯一標(biāo)示id、線路長(zhǎng)度length、線路的起始點(diǎn)和終止點(diǎn)，每個(gè)柱子元素pillar有一個(gè)唯一標(biāo)示id、柱子的x坐標(biāo)和y坐標(biāo)（在樓層圖片文件中的橫縱坐標(biāo)）和該柱子所屬的線路（距離該柱子最近的線路），元素relation表示兩個(gè)停車樓層之間的連接線路，連接的端點(diǎn)為某樓層上的某個(gè)點(diǎn)。

此外柱子還有一些描述信息message，該信息描述了此柱子的位置坐標(biāo)和所屬的線路。該信息可以用于外部使用（如對(duì)其生成二維碼貼于實(shí)際停車場(chǎng)中對(duì)應(yīng)的柱子上，通過(guò)手機(jī)掃描二維碼即可獲得該柱子的相關(guān)信息）。

通過(guò)地圖描述文件，我們可以將停車場(chǎng)結(jié)構(gòu)抽象為圖的模型，進(jìn)而可以計(jì)算任意兩點(diǎn)之間的最短路徑，結(jié)合地圖文件將最優(yōu)線路展示給車主用戶。

2 基于地圖文件計(jì)算最短線路

本文地圖文件是針對(duì)于停車場(chǎng)反向停車而設(shè)計(jì)的。反向?qū)ぼ嚭诵募礊榇_定車主與車的位置及車主位置到車位置之間的最短線路的計(jì)算。確定了停車場(chǎng)中的兩個(gè)點(diǎn)以后既可以根據(jù)停車場(chǎng)地圖描述文件計(jì)算兩點(diǎn)之間的最短線路。停車場(chǎng)中兩個(gè)點(diǎn)通常由車主用戶使用手機(jī)掃描相應(yīng)的二維碼得到（每個(gè)二維碼所包含的信息是根據(jù)柱子的相關(guān)信息而生成）。根據(jù)兩個(gè)點(diǎn)（柱子信息）及描述文件計(jì)算最短線路的步驟如下：

1） 確定兩個(gè)點(diǎn)person、car（它們包含了柱子的相關(guān)信息）及停車場(chǎng)地圖描述文件，

2） 定義圖的鄰接矩陣matrix及圖的點(diǎn)集合points和邊集合lines

3） 解析停車場(chǎng)描述文件，根據(jù)point元素初始化圖的點(diǎn)集，根據(jù)line元素初始化圖的邊集

4） 將點(diǎn)person添加到點(diǎn)集中作為點(diǎn)集的第一個(gè)元素，同時(shí)根據(jù)點(diǎn)坐標(biāo)及其所屬線路line_person計(jì)算點(diǎn)person到線line_person之間的垂線段并將該垂線段添加的圖的邊集中

5） 將點(diǎn)car添加到點(diǎn)集中作為點(diǎn)集的最后一個(gè)元素，同時(shí)根據(jù)點(diǎn)坐標(biāo)及其所屬線路line_car計(jì)算點(diǎn)car到線line_car之間的垂線段并將該垂線段添加的圖的邊集中

6） 根據(jù)圖的點(diǎn)集合points和邊集合lines初始化圖的鄰接矩陣matrix，線路的長(zhǎng)度作為圖中邊的權(quán)值

7） 使用一種最短路徑計(jì)算方法（如迪杰斯特拉算法）計(jì)算從起始點(diǎn)（person作為起始點(diǎn)）到終止點(diǎn)（car作為終止點(diǎn)）的最短路徑，最短路徑上的點(diǎn)存儲(chǔ)在一個(gè)數(shù)組result_path中。

3 實(shí)驗(yàn)結(jié)果

針對(duì)上述地圖設(shè)計(jì)，該文設(shè)計(jì)并實(shí)現(xiàn)的停車場(chǎng)反向?qū)ぼ囓浖?duì)上述地圖設(shè)計(jì)進(jìn)行了驗(yàn)證。該軟件需要運(yùn)行在手機(jī)上，并要求手機(jī)具有攝像頭功能，本測(cè)試手機(jī)為華為榮耀3C Android[7-9]平臺(tái)手機(jī)。該文分別就起始點(diǎn)、終止點(diǎn)在同一停車樓層和起始點(diǎn)、終止點(diǎn)在不同停車樓層進(jìn)行了驗(yàn)證，試驗(yàn)時(shí)起始點(diǎn)和終止點(diǎn)均為隨機(jī)選取并進(jìn)行了多次試驗(yàn)。實(shí)驗(yàn)結(jié)果展示分別如圖3和圖4。

4 結(jié)論

本文提出了一種適用于反向?qū)ぼ嚨耐＼噲?chǎng)地圖設(shè)計(jì)，該設(shè)計(jì)主要是地圖描述文件的設(shè)計(jì)，該地圖描述文件可以轉(zhuǎn)化為圖的模型。結(jié)合二維碼存儲(chǔ)停車場(chǎng)柱子位置信息，本設(shè)計(jì)能夠通過(guò)手機(jī)計(jì)算并展示車主位置和停車位置之間的最短線路，從而可以有效地解決大型停車場(chǎng)車主用戶找車難問(wèn)題。

參考文獻(xiàn)：

[1] 王揚(yáng)，薛娟.智能停車場(chǎng)反向?qū)ぼ囅到y(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].無(wú)線互聯(lián)科技，2012（11）.

[2] 樊勇，任燕，司博章.一種新型停車場(chǎng)反向?qū)ぼ囅到y(tǒng)[J].物聯(lián)網(wǎng)技術(shù)，2013（2）.

[3] 科拓.車位引導(dǎo)|反向?qū)ぼ嘯EB/OL].http：//www.keytop.com.cn/

[4] 劉小晶，杜選.數(shù)據(jù)結(jié)構(gòu)（java語(yǔ)言描述）[M].北京：清華大學(xué)出版社，2011：192-232.

[5] 王桂平，王衍，任嘉辰.圖論算法理論、實(shí)現(xiàn)及應(yīng)用[M].北京；北京大學(xué)出版社，2011.

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

[7] 王雅寧.輕松學(xué)android開發(fā)[M].北京：電子工業(yè)出版社，2013：1-331.

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

[9] 李寧. Android/Ophne開發(fā)完全講義[M].北京：中國(guó)水利水電出版社，2010.endprint