Кібернетика та комп'ютерні технології (Mar 2025)
Equipartition Algorithm for a Flat Parametric Curve Based on the Intersection Between it and a Moving Circle
Abstract
Introduction. The problem of discretization of continuous geometric objects is one of the most common problems of computational geometry. Many applications in all different fields, such as computer vision, robotics, signal processing, curve simplification in computer graphics applications, geographic information systems, and digital manufacturing applications, are based on the discretization and segmentation of plane curves, which are basic geometric objects. These methods mainly aim to solve the problem of dividing the curve into segments with the same characteristics or to minimize a predetermined error. The condition of partitioning the curve into points when the lengths of the chords connecting the segments are equal is an additional factor interesting from the point of view of practical applications. It allows, for example, to simplify the reproduction of a curve on CNC machines thanks to the constancy of the tool feed speed [1] or the reproduction of the movement of an object based on a video recording [2]. The purpose of the paper is to develop new algorithms for partitioning flat parametric curves under the condition of equality of chords (chord length connecting segments of the partition) given the two outside points included in the first and last segment and given a number of segments. Results. The problem of partitioning a curve in a parametric vector form on the Euclidean plane into segments equal in chord length having the formulation of [23, 24] was considered. A method of partitioning a flat parametric curve into equal-chord segments by crossing a circle of constant radius with the subsequent movement of the circle's center to the intersection point is proposed. The problem of the multivalued solution of the intersection equation was considered, which complicates the application of this method. This circumstance limits the use of circular partitioning by the lower limit of the values ??of the number of segments. The proposed algorithm was presented in pseudocode and described. It consists of the following procedures: the procedure for the initial initialization of the radius of a circle based on a partition with a uniform distribution by a parameter, procedures for partitioning the curve by a circle for different directions of the circle`s move (direct, reverse, two-way); the procedure for obtaining an equal-chord partition with a specified tolerance of determining the chord length. For the real curve`s example, experiments were conducted on its equipartition by this algorithm, implemented in the Julia programming language. It was established that with an increase in the degree of discretization of the value of the curve, the number of iterations required to achieve the specified accuracy stabilizes. This leads to a linear dependence of the partition execution time with an increase in the number of segments. It was found that when the accuracy of the partition is increased, the number of iterations increases slightly compared to the increase in accuracy. Conclusions. As a result of the research, it was found that the proposed algorithm is quite suitable for the equal chord segmentation of flat parametric curves in a wide range of segment values. The two-way version of the algorithm was the most promising for real applications, as it is more stable and flexible. This version is suitable for parallel execution by two processes or threads. The two-threaded version showed the best performance of all the algorithm versions. The disadvantages of the presented algorithm should include, first of all, the limitation of the lower limit of number of segments because with a small number of them, the radius of the partition circle increases, which leads to the presence of several intersection options and the need to analyze these options. Another disadvantage is that obtaining the points by way of the intersection requires solving the nonlinear equation, which depends on the representation of the curve and can be pretty tricky, even for numerical methods.
Keywords
