2025, issue 1, p. 12-31
Received 11.11.2024; Revised 21.12.2024; Accepted 25.03.2025
Published 28.03.2025; First Online 30.03.2025
https://doi.org/10.34229/2707-451X.25.1.2
Equipartition Algorithm for a Flat Parametric Curve Based on the Intersection Between it and a Moving Circle
Oleg Frolov 
Simon Kuznets Kharkiv National University of Economics, Ukraine
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
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: pseudocode, iteration, computational complexity, segmentation, chord, intersection equation.
Cite as: Frolov O. Equipartition Algorithm for a Flat Parametric Curve Based on the Intersection Between it and a Moving Circle. Cybernetics and Computer Technologies. 2025. 1. P. 12–31. https://doi.org/10.34229/2707-451X.25.1.2
References
1. Shpitalni M., Koren Y., Lo C.C. Realtime curve interpolators. Computer-Aided Design. (1995). 26(11). P. 832–838. https://doi.org/10.1016/0010-4485(94)90097-3
2. Panagiotakis C., Tziritas G. Snake terrestrial locomotion synthesis in 3D virtual environments. The Visual Computer. 2006. 22. P. 562–576. https://doi.org/10.1007/s00371-006-0035-1
3. Ramer U. An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing. (1972). 1(3). P. 244–256. https://doi.org/10.1016/S0146-664X(72)80017-0
4. Douglas D., Peucker Th. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer. 1973. 10(2). P. 112–122. https://doi.org/10.3138/FM57-6770-U75U-7727
5. Phisannupawong T., Damanik J.J., Choi H.L. Aircraft Trajectory Segmentation-based Contrastive Coding: A Framework for Self-supervised Trajectory Representation. arXiv preprint. 2024. https://doi.org/10.48550/arXiv.2407.20028
6. Rutkowski W.S. Shape segmentation using arc/chord properties. Comput. Graphics Image Processing. 1981. 17(2). P. 114–129. https://doi.org/10.1016/0146-664X(81)90020-4
7. Phillips T.-Y., Rosenfeld A. A method of curve partitioning using arc-chord distance. Pattern Recognition Letters. 1987. 5(4). P. 285–288. https://doi.org/10.1016/0167-8655(87)90059-6
8. Marji M., Klette R., Siy P. Corner Detection and Curve Partitioning Using Arc-Chord Distance. IWCIA 2004. Lecture Notes in Computer Science. 2004. 3322. P. 512–521. https://doi.org/10.1007/978-3-540-30503-3_37
9. Kolesnikov A. ISE-bounded polygonal approximation of digital curves. Pattern Recognit. Lett. 2012. 33(10). P. 1329–1337. https://doi.org/10.1016/j.patrec.2012.02.015
10. Williams C. M. An efficient algorithm for the piecewise linear approximation of planar curves. Computer Graphics and Image Processing. 1978. 8(2). P. 286–293. https://doi.org/10.1016/0146-664X(78)90055-2
11. Dunham J. G. Optimum uniform piecewise linear approximation of planar curves. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1986. 8(1). P. 67–75. https://doi.org/10.1109/TPAMI.1986.4767753
12. Horst J., Beichl I. Efficient piecewise linear approximation of space curves using chord and arc length. Proceedings of the SME Applied Machine Vision '96 Conference. 1996. https://tsapps.nist.gov/publication/get_ pdf.cfm?pub_id=820563 (accessed 13.08.2024)
13. Kalaivani S., Ray B.K. A heuristic method for initial dominant point detection for polygonal approximations. Soft Computing. 2019. 23. P. 8435–8452. https://doi.org/10.1007/s00500-019-03936-1
14. Hu R., Watt S. Optimization of point selection on digital ink curves. Proc. 13th International Conference on Frontiers in Handwriting Recognition, Bari, Italy, Sept. 18-20. 2012. P. 525–530. https://doi.org/10.1109/ICFHR.2012.252
15. de Figueiredo L. H. Adaptive sampling of parametric curves. Graphics Gems V. 1995. P. 173–178. https://doi.org/10.1016/B978-0-12-543457-7.50032-2
16. Zhong W., Luo X., Chang W., etc. A real-time interpolator for parametric curves. International Journal of Machine Tools and Manufacture. 2018. 125. P. 133–145. https://doi.org/10.1016/j.ijmachtools.2017.11.010
17. Wei J., Sun C., Zhang X. J., etc. An efficient and accurate interpolation method for parametric curve machining. Scientific Reports. 2022. 12. 16000. https://doi.org/10.1038/s41598-022-20018-9
18. Han X.T., Zhu K.F., Wang X.B. A hash approach to refine CNC computation of arc length and parameter of NURBS with high efficiency and precision. International Journal of Precision Engineering and Manufacturing. 2024. 25. P. 1243–1256. https://doi.org/10.1007/s12541-024-00976-y
19. Chalkis, A., Katsamaki, Ch., Tonelli-Cueto, J. On the error of random sampling uniformly distributed random points on parametric curves. Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation (ISSAC 22). 2022. P. 273–282. https://doi.org/10.1145/3476446.3536190
20. Pagani L., Scott P.J. Curvature based sampling of curves and surfaces. Computer Aided Geometric Design. 2018. 59. P. 32–48. https://doi.org/10.1016/j.cagd.2017.11.004
21. Hernández-Mederos V., Estrada-Sarlabous J. Sampling points on regular parametric curves with control of their distribution. Computer Aided Geometric Design. 2003. 20 (6). P. 363–382. https://doi.org/10.1016/S0167-8396(03)00079-7
22. Frolov О.V., Losev M.U. Modeling of asymptotically optimal piecewise linear interpolation of plane parametric curves. Radio Electronics, Computer Science, Control. 2021. 3. P. 57–68. https://doi.org/10.15588/1607-3274-2021-3-6
23. Lopez M.A., Reisner S. A note on curves equipartition. arXiv preprint. 2008. https://doi.org/10.48550/arXiv.0707.4298
24. Panagiotakis C., Athanassopoulos K., Tziritas G. The equipartition of curves. Computational Geometry. 2009. 42 (6–7). P. 677–689. https://doi.org/10.1016/j.comgeo.2009.01.003
25. Panagiotakis C., Tziritas G. Any dimension polygonal approximation based on equal errors principle. Pattern Recognit. Lett. 2007. 28. P. 582–591. https://doi.org/10.1016/j.patrec.2006.10.005
26. Wang X.-R., Wang Z.-Q., He P., etc. The high-energy micro-arc spark—computer numerical control deposition of planar NURBS curve coatings. Int J Adv Manuf Tech. 2016. 87. P. 3325–3335. https://doi.org/10.1007/s00170-016-8698-x
27. Divide. https://docs.mcneel.com/rhino/8/help/en-us/commands/divide.htm (accessed 20.10.2024)
28. Frolov O. Equipartition algorithm for a flat parametric curve based on the intersection between it and a moving circle, Oct 2024. https://github.com/froleg/equipartition (accessed: 11.11.2024)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)