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