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

PLoS One. 2020 Mar 13;15(3):e0230342. doi: 10.1371/journal.pone.0230342. eCollection 2020.

Abstract

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.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Computers / statistics & numerical data*
  • Image Processing, Computer-Assisted / methods*
  • Models, Theoretical*

Grants and funding

This work was supported by Young Scientists Fund of National Natural Science Foundation of China (No.41301479); University Innovation Talent Support Program of Liaoning Province (No.LR2016061); General Project of Science, and Technology Research of Education Department of Liaoning Province (No. LJCL009); and the grant recipient of all the funds are Quanhua Zhao. Quanhua Zhao provides the main idea of the research and responsible for the revision of the manuscript.