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

Area of Science:

• Computational Geometry
• Computer Graphics
• Geometric Algorithms

Background:

• Constructing simple polygons from point sets is a fundamental problem in computational geometry.
• Existing methods may have limitations in efficiency or applicability to various point distributions.

Purpose of the Study:

• To introduce and validate a novel algorithm, iterative inserting ordered points (IIOP), for constructing simple polygons from plane point sets.
• To demonstrate the algorithm's capability in forming valid simple polygons regardless of the number of points.

Main Methods:

• The iterative inserting ordered points (IIOP) algorithm orders points along a primary axis (e.g., x-axis).
• An initial polygon is formed using the first three points.
• Subsequent points are iteratively inserted based on line visibility criteria to maintain polygon simplicity.
• The process continues until all points are incorporated into the polygon.

Main Results:

• The IIOP algorithm was tested with sets of 20, 50, and 80 plane points.
• Experimental results confirmed that the algorithm successfully constructed simple polygons in all tested cases.
• Theoretical and experimental verifications support the algorithm's efficacy.

Conclusions:

• The iterative inserting ordered points (IIOP) algorithm provides a reliable method for constructing simple polygons from non-collinear point sets.
• The algorithm's effectiveness is demonstrated through successful polygon formation across different point set sizes.
• This contributes a viable approach to geometric polygon construction problems.