Approximation of irregular polylines by means of a straight-line graph

In this work we introduce an algorithm to approximate the external shape of an irregular polyline containing some cycles and interlacements. The output consists of a counterclockwise closed walk still containing only some cycles that, with the addition of one more step, can be “opened” in a suitable way to produce a Hamiltonian circuit. Moreover, the time cost of the algorithm is explained and the data structures introduced are described. The proposed algorithm applies to the polyline described by all the input data points as well as the polyline returned using a simplification/reduction method. We also describe how the entire algorithm, or some part of it, can be applied to the output of some well-known reduction methods to solve particular problems which may arise. We carried out a first implementation of the algorithm in MATLAB for its capability to provide both numerical and graphical tools within the same programming language as well as specific features offered by its Toolboxes and by the community of its users. We shall refer to it when reporting some of the results.