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

Hongyun Zhang, Quanhua Zhao and Yu Li

PLOS ONE, 2020, vol. 15, issue 3, 1-21

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.

Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0230342 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 30342&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0230342

DOI: 10.1371/journal.pone.0230342

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().