To improve the registration of point clouds scanned by 3D laser in terms of accuracy and efficiency, and solve the registration problems when data points are missing and out of order, based on the invariant characteristics of global and local structure features of point clouds, an initial registration algorithm using global structure features and a fast and accurate registration algorithm using local structure features are proposed. First, the global structure feature and the initial registration method are defined. The validity of the initial registration is strictly proved when the data point is lost. Then, we propose a way to partition the spatial region and find out the corresponding points of the two point clouds in the spatial region. Finally, the two clouds achieve precise registration through the corresponding points found. In the processes of simulation and experiment, the proposed algorithm can effectively perform accurate and rapid registration of missing and scattered point clouds. It has obvious advantages in efficiency and accuracy than other algorithms.