Docking of Polygons Using Boundary Descriptor

摘要

We show that the polygon docking problem can be divided into two subproblems, partial matching of periodic strings and line segment intersection detection. And we show that the docking problem of a pair of polygons is solved in O(n~2) times, where n is the number of edges of polygons. Using this result, we show that construction of an object from a collection of polygons whose elements have no numerical error on the expression of the lengths of edges and the angles between two connecting edges can be solved in O(k~3n~2) times for k polygons where the maximum number of edges of polygonal-elements is n.