Constructing 2D Shapes by Inward Denting

摘要

Constructing a two dimensional shape from a given set of point sites is a well-known problem in computational geometry. We present a critical review of the existing algorithms for constructing polygonal shapes from given point sites. We present a new approach called 'inward denting' for constructing polygonal shapes. We then extend the proposed approach for modeling polygons with holes. We also present experimental investigations of the quality of the solutions generated by the proposed algorithm. For obtaining experimental results we implemented the proposed algorithm in Java programming language. The experimental results show that the perimeter of the generated shape is at most 33% more than the length of the minimum spanning tree.