2025, випуск 1, c. 12-31
Одержано 11.11.2024; Виправлено 21.12.2024; Прийнято 25.03.2025
Надруковано 28.03.2025; Вперше Online 30.03.2025
https://doi.org/10.34229/2707-451X.25.1.2
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Алгоритм рівноланкового розбиття плоскої параметричної кривої на основі її перетину з рухомим колом
О.В. Фролов 
Харківський національний економічний університет імені Семена Кузнеця, Харків
Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Проблема дискретизації неперервних геометричних об’єктів – це одна з найпоширеніших проблем обчислювальної геометрії. Ця проблема має велику кількість застосувань в усіх різних сферах, таких як комп’ютерний зір, робототехніка, обробка сигналів, спрощення кривих у застосунках комп’ютерної графіки, геоінформаційних системах та застосунках для цифрового виробництва, засновані на дискретизації та сегментації плоских кривих, які є базовими геометричними об’єктами. Основна мета методів дискретизації полягає у тому, щоб вирішити задачу розбиття кривої на сегменти з однаковими характеристиками або мінімізувати заздалегідь визначену помилку. Умова розбиття кривої точками при рівності довжин хорд стягуючих сегменти є додатковим фактором цікавим з точки зору практичних застосувань. Вона дозволяє, наприклад, спростити відтворення кривої на станках із ЧПУ завдяки сталості швидкості подачі інструмента [1], або відтворення руху об’єкта за відеозаписом [2].
Мета роботи. Розроблення нових алгоритмів розбиття плоских параметричних кривих за умови рівності ланок (довжин хорд стягуючих сегменти розбиття) при поданих двох крайніх точках, що входять до першого та останнього сегменту, та заданої кількості сегментів.
Результати. Розглядалась задача розбиття кривої, заданої у параметричній векторній формі на евклідовій площині, на рівні за довжиною хорди сегменти у «класичному» формулюванні [23, 24]. Запропоновано метод розбиття плоскої параметричної кривої на рівні за хордою сегменти перетином кола сталого радіусу з наступним переміщенням центру кола у точку перетину. Було розглянуто проблему багатозначності розв’язку рівняння перетину, що ускладнює застосування цього методу. Ця обставина обмежує застосування розбиття колом нижньою границею значень кількості сегментів. Було представлено у псевдокоді і описано запропонований алгоритм, а саме: процедуру первісної ініціалізації радіусу кола на основі розбиття з рівномірним розподілом за параметром; процедури розбиття кривої колом для різних напрямів переміщення кола (прямий, зворотний, двосторонній); процедуру отримання рівноланкового розбиття із заданою точністю визначення довжини хорди. На прикладі реальної кривої лінії проведено експерименти із її розбиття алгоритмом, реалізованим на мові програмування Julia. Встановлено, що із збільшенням ступеня дискретизації кривої значення кількості ітерацій, необхідних для досягнення заданої точності, стабілізується. Це призводить до лінійної залежності часу виконання розбиття зі збільшенням кількості сегментів. Виявлено, що при підвищення точності розбиття відбувається незначне у порівняння із зростанням точності збільшення показника кількості ітерацій.
Висновки. У результаті проведених досліджень встановлено, що запропонований алгоритм цілком придатний для сегментації плоских параметричних кривих за умови рівності довжин хорд у широкому діапазоні значень кількості сегментів. Для реальних застосувань найбільш перспективною виявився двосторонній варіант алгоритму, як більш стабільний та гнучкий. Цей варіантf алгоритму дозволяє виконувати розбиття паралельно двома процесами або потоками. Версія з двома потоками продемонструвала найкращі показники часу виконання серед всіх версій алгоритму. До недоліків представленого алгоритму слід віднести, насамперед, обмеження нижньої границі значень кількості сегментів, адже при їх невеликої кількості збільшується радіус кола розбиття, що призводить до наявності декількох варіантів перетину та необхідності аналізу цих варіантів. Недоліком також є те, що для отримання точок розбиття на основі перетину з колом необхідно розв’язувати нелінійне рівняння, яке залежить від представлення кривої, і може бути досить складним, навіть, для чисельних методів.
Ключові слова: псевдокод, ітерація, обчислювальна складність, сегментація, хорда, рівняння перетину.
Цитувати так: 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
Список літератури
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 (звернення: 11.11.2024)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна