АЛГОРИТМ РІВНОХОРДОВОГО РОЗБИТТЯ ПЛОСКОЇ ПАРАМЕТРИЧНОЇ КРИВОЇ НА ОСНОВІ ПЕРЕТИНУ З КОЛОМ

Анотація

У статті розглядається задача рівнохордового розбиття плоских параметричних кривих, яка полягає у визначенні послідовності точок на кривій так, щоб евклідові відстані (хорди) між сусідніми точками були рівними. Рівнохордова дискретизація є важливою для систем автоматизованого проєктування, числового програмного керування, робототехніки та комп’ютерної графіки, оскільки забезпечує стабільні геометричні й технологічні властивості траєкторій порівняно з параметрично рівномірним або дуговим дискретизуванням. Метою роботи є розроблення ефективних алгоритмів рівнохордового розбиття плоских параметричних кривих у класичній постановці – за фіксованими кінцевими точками та заданою кількістю сегментів – з урахуванням багатозначності розв’язків, що виникає при перетині кривої з колом. Запропонований підхід ґрунтується на послідовному перетині кривої з рухомим колом фіксованого радіуса. Починаючи з одного або обох кінців кривої, центр кола розміщується в поточній точці розбиття, а наступні точки визначаються як точки перетину кривої з колом у заданому напрямку. Для обробки не опуклих кривих і кривих з точками перегину всі можливі розв’язки рівняння перетину організовуються у вигляді деревоподібної структури, де кожна гілка відповідає альтернативній траєкторії розбиття. Оптимальний варіант визначається шляхом мінімізації різниці між довжиною залишкового сегмента та радіусом кола. У роботі досліджено два підходи до визначення радіуса кола: метод рівномірного перерозподілу похибки між сегментами та оптимізаційний підхід, у якому радіус є мінімумом одновимірної цільової функції. Експериментальні дослідження на плоских кривих Безьє різного порядку підтверджують стабільну збіжність алгоритмів і майже лінійну обчислювальну складність у практичних сценаріях. Запропонований метод не потребує чисельного інтегрування довжини дуги, легко узагальнюється на просторові криві та є перспективним для подальших досліджень.