A novel approach for detecting intersections from GPS traces

Intersection detection is a critical aspect for both route planning and path optimization. In literature, intersections are detected mostly using the road users’ turning behaviors. This paper proposes to detect intersections using its definition of connecting at least 3 roads. We first detect the Longest Common Sub-Sequences (LCSS) between each pair of GPS traces using dynamic programming approach. Second, we partition the longest nonconsecutive subsequences into consecutive substrings. The starting and ending points of each common substring are connecting points where two GPS traces split to different directions after they share a series of common locations. At last, we estimate Kernel Density (KD) of the connecting points and find the local maximums on the density map as intersections. Experimental results show better performance of the proposed method.