лгоритм
Є також варіант, де розгалуження не відбувається, де вибирається тільки початкова точка, а кінець визначається автоматично. У цьому випадку, якщо зустрілося розгалуження, вибирається група по найменшому відхиленню від ширини. Якщо таких груп кілька, то з них вибираємо групу по найменшому відхиленню вектори напрями, тобто по наявності в ній такої точки x, такий що кут між вектором (pr; p) і (p; x) мінімальний, де x належить об'єднанню цих груп. Якщо таких груп кілька, то вибирається будь-яка.
Зміна стосуються пунктів б) і в). Кінцева крапка не вибирається:
) Попередня обробка зображення здійснюється аналогічно, за виключення застосування алгоритму утоньшения ліній, т.к. в даному алгоритмі товщина лінії існує.
) Визначення графіка.
Користувач клацанням миші визначає початкову точку графіка. Нагадаємо, що графік після фільтрації може бути тільки чорного кольору. Вважаємо, що початкова точка вказує або початку графіка або деяке інше місце без перетинів з іншими графіками. Далі алгоритм працює таким чином:
б) Для групи маємо поточний малюнок. Для групи маємо попередню точку (pr). Назвемо шириною групи кількість елементів у групі. Тепер обчислимо ширину (w) і радіус (r) як (w div 2) +1. Виберемо середню у порядковому значенні точку (p) з групи. Введемо для цієї групи шлях trace, який є впорядкованим списком точок. Додаємо p в trace. Формуємо групи тим же способом що і в попередньому пункті. Якщо немає ні однієї групи, то в цьому випадку алгоритм закінчується і фіксується trace для даної групи.
Зафарбовуємо точки білим в радіус-квадраті радіусом r - 1 для поточного малюнка. Тут можливі варіанти:
) Якщо група одна і її ширина не перевершує w, то виберемо середню в ній крапку і додамо її в trace, також присвоїмо p значення цієї точки. Оновлюємо значення радіуса r=(w div 2) +1 і потім повторюємо алгоритм.
) Якщо група одна і її ширина перевершує w, то збільшуємо r на 1 (так як потенційно маємо перетин) і повторюємо алгоритм.
) Якщо груп більше однієї, то вважаємо, що перетинання знайдено. Вибираємо групу по найменшому відхиленню від ширини, а якщо таких груп кілька, то з них вибираємо по найменшому відхиленню вектори напрями, тобто по наявності в ній такої точки x такий, що кут між вектором (pr; p) і (p; x) мінімальний, де x належить об'єднанню цих груп. Якщо таких груп кілька, то вибирається будь-яка група.
Потім в ній виберемо середню точку і додамо її в trace. Потім присвоюємо p значення цієї точки і оновлюємо значення радіусу і ширини
=(w_new div 2) +1, w=w_new
де w_new - ширина обраної групи.
Повторюємо алгоритм.
в) У підсумку маємо 1 шлях або 2 шляхи (trace). Поєднуючи їх, отримуємо загальний шлях. Результатом визначення графіка є спільний шлях.
Описаний алгоритм вимагає менше обчислень, однак створює більший ризик неправильного визначення шляху, особливо при перетинах з перешкодою під гострим кутом. Обчислювальна ефективність є перевагою, якщо побічних відгалужень багато (якщо графік, наприклад, нанесений на сітку). У цьому випадку алгоритм значно швидше працює і ефективно фільтрує невірн...
