manière efficace de comprendre qu'une courbe est fermée ou non - algorithme, traitement d'image, géométrie computationnelle

Quel est le moyen efficace de comprendre qu'une courbe est fermée ou non?

peut-être un moyen est l'algorithme de remplissage par inondation et l'utiliserpour le vérifier: si votre crue laisse une zone de sélection prédéterminée, vous êtes en dehors de la forme. Sinon, si votre remplissage se termine, alors vous êtes dans la forme.

mais est-ce un moyen efficace?

tnx.

Réponses:

Regardez une courbe sous forme de graphique, les sommets sont des pixels et les arêtes se situent entre les pixels voisins. Le test est fait:

• Une courbe simple signifie que tous les sommets ont deux voisins et que le graphique est connecté.
• Plus les courbes simples non intersectées sont si tous les sommets ont deux voisins et que le graphe n’est pas connecté.
• La courbe 8 est si tous les sommets sauf un ont 2 voisins, celui-ci a 4 voisins et le graphique est connecté.
• ...

Les tests de connectivité graphique / sous-graphique et de partitionnement se font par traversée de graphique.

Pourriez-vous marcher le long de la courbe avec deux pointeurs séparés? Si c'est le cas, faites-le en configurant un pointeur pour qu'il traverse deux fois plus vite. Si la boucle est fermée, les pointeurs se chevaucheront à un point.

Cela devrait être O (n) ..

Disons que le degré de chaque pixel est le nombre de pixels dans son voisinage.

Parcourez votre tableau de pixels, si un pixel a un degré impair, la courbe n'est pas fermée.

Explication: Pour un pixel de degré pair, pour chaque chemin entrant, il existe un chemin qui le quitte. Ce n'est pas vrai pour les degrés impairs.