A scan matching method based on the area overlap of star-shaped polygons

We illustrate a method that performs scan matching by maximizing the intersection area of the scans. The intersection area is a robust parameter that is less prone to measurement errors with respect to alternative techniques. Furthermore, such technique does not require to associate each point of one scan to a point of the other one like in some popular algorithms. The relative pose that maximizes the overlap is estimated iteratively. Since the scans are represented by star-shaped polygons due to visibility properties, their intersection can be computed using an efficient linear-time traversal of the vertices. Then, the relative pose is updated under the hypothesis that the combinatorics of intersection is left unchanged and the procedure is repeated until the scans are aligned with sufficient precision.