The Algorithm Study Of Polygonal Shape Reconstruction

Processing a dot pattern or point set in the plane is a useful and important problem in pattern recognition. Dot patterns encountered in various problems include points in feature space, pixel in a digital image, physical objects like stars in the galaxy or spatial data.Suppose there is a series of discrete points in the plane, which we can not perceive the specific shape it want to express only depends on our visual system.The main problem that we want to study is how to reconstruct from these discrete points out a specific graphics that we can identify. To reconstruct a specific pattern,we need concave this graphic from the convex hull step by step, so that we can make more points back to the border, which can be set closer to the point to ask graphic representation of the real. Thus, the first task is to establish the convex hull of the set. Suppose a set of discrete points without boundary, we need to establish the convex hull boundary of the points set. We want to use Delaunay triangulation,because it is clear that the points set convex hull is a subset of the triangulation formed by Delaunay triangulation. So, just establish a suitable threshold and remove the extra edges to get the convex hull of the points set. In addition, I also design a proper circle to determine the convex hull of the points set by the chord formed by two points on the circle of the points set. If the input is a set of points with a boundary, it is necessary to detect the boundary. The main algorithms we will use are splitting algorithm, isolation algorithm, merging algorithm.To find the convex hull of the point set, we will concave the convex hull.When concave the convex hull, we need to remove an edge, and use the two endpoints with a set of point to construct two new edges. This requires to select the suitable edge and an appropriate dot every step. When selecting, we will combine the closeness criterion, length of edge criterion and two new angles criterion.Finally, we give the algorithm stop condition. If the condition is met, the algorithm stops. If the condition is not met, the algorithm loops.