ефективний спосіб зрозуміти, що крива закрита чи ні - алгоритм, обробка зображень, обчислювальна-геометрія

який ефективний спосіб зрозуміти, що крива закрита чи ні?

можливо, одним із способів є алгоритм заповнення потоком і його використанняЩоб перевірити його, якщо заливка залишила заздалегідь визначений обмежувальний прямокутник, ви перебуваєте поза формою. В іншому випадку, якщо ваша заливна заливка закінчиться, тоді ви перебуваєте у формі.

але чи це ефективний спосіб?

tnx.

Відповіді:

Подивіться на криву як на графік, вершини - на пікселі, а ребра - на сусідні. Тестування виконується:

• Проста крива, якщо всі вершини мають двох сусідів, а граф пов'язаний.
• Більш не перетинаються прості криві, якщо всі вершини мають двох сусідів, а граф не підключений.
• 8 крива, якщо всі вершини, крім однієї, мають 2 сусіди, одна з яких має 4 сусіди, а граф пов'язаний.
• ...

Тестування підключення та розбиття графів / підграфів здійснюється шляхом обходу графіка.

Чи можете ви пройти по кривій з двома окремими покажчиками? Якщо так, зробіть це і встановіть один покажчик, щоб пройти двічі швидше. Якщо цикл закритий, покажчики будуть перекриватися в одній точці.

Це має бути O (n).

Дозволяє сказати, що ступінь кожного пікселя - це кількість пікселів у його околиці.

Пройдіть піксельний масив, якщо будь-який піксель має непарну ступінь, то крива не закривається.

Пояснення: Для пікселя з рівним рівнем, для кожного шляху, що входить, є шлях, який залишає його. Це не стосується непарних градусів.