In order to meet the demand of indoor location service, a new iterative closest point (ICP) algorithm based on K-means clustering is proposed to construct a structured two-dimensional indoor map. Based on the clustering analysis of the point cloud data obtained by the two dimensional laser scanner, the data of each frame is clustered, and the cloud data is pre-registered by the translation of the geometric center. The global optimal solution is obtained by the accuracy registration of the cloud data after clustering and pre-registering. Compared with the traditional ICP algorithm, the improved ICP algorithm can obtain higher accuracy registration results when the point cloud data is collected by a single 2D laser scanner. Experiments show that the algorithm has the advantages of strong robustness and high registration accuracy, which can help to construct the indoor map quickly and accurately under the single sensor.