Generation of simple polygons from ordered points using an iterative insertion algorithm

• Published in: PloS one 2020-03, Vol.15 (3), p.e0230342-e0230342
• Main Authors: Zhang, Hongyun, Zhao, Quanhua, Li, Yu
• Format: Article
• Language: English
• Subjects: Algorithms; Computer and Information Sciences; Engineering and Technology; Geometry; Methods; Physical Sciences; Polygons; Remote sensing; Research and Analysis Methods
• ISSN: 1932-6203; 1932-6203
• DOI: 10.1371/journal.pone.0230342

To construct a simple polygon from a set of plane points, we propose an iterative inserting ordered points (IIOP) algorithm. Using a given a set of ordered non-collinear points, a simple polygon can be formed and its shape is dependent on the sorting method used. To form such simple polygons with a given set of plane points, the points must first be ordered in one direction (typically, the x-axis is used). The first three points in the set are used to form an initial polygon. Based on the formed polygon, new polygons can be iteratively formed by inserting the first point of from among the remaining set of points, depending on line visibility from that point. This process is carried out until all the points are inserted into the polygon. In this study, we generated 20, 50, and 80 plane points and used the proposed method to construct polygons. Experimental results show that these three polygons are all simple polygons. Through theoretical and experimental verification, we can concluded that when given a set of non-collinear points, a simple polygon can be formed.