On-line Path Search Algorithm Based on Spatial Block Path Cache
Yang Zhou · Jisuanji gongcheng · 2010
In order to construct a high efficiency path finding engine for the on-line map service,a shortest path search algorithm based on spatial block path cache and index is presented.A road network resample processing is proposed to obtain a road network density image and a block algorithm based on ISODATA clustering is presented to calculate the road network spatial block region.The path cache between road network block regions is calculated to reduce the path finding node number between block regions.An index algorithm to the path cache is designed.A bi-direction path search algorithm based on the path cache and path search in block region is presented.Experimental result of on-line path search shows higher efficiency comparing with the traditional path search algorithms which can reduce the on-line path calculation time less than 0.2 s for a city level road network.It can also obtain load balance of the map application server.