On va itérativement supprimé 1 segment.
Supposons que nous avons 3 segment entre les points A, B et C et D.
On va rassembler les points B et C en un seul (disons X)
![Decouper un polygone a partir d'une image Sans_t10](https://i.servimg.com/u/f37/16/62/42/75/sans_t10.png)
2 questions:
1) comment positionner X
2) comment choisir B et C (parmis tous les segments possibles)
Pour ça on définis une erreur.
Une droite, c'est l'ensemble des points qui minimise (en atteignant 0) une quadrique (équation de degré 2 en x et y)
L'idée géniale, c'est de ce dire qu'une quadrique peut en coordonnée homogène se représenter comme une matrice Q et l'équation s'écrire:
Minimiser : X' Q X où X = (x,y,1) (et X' est la transposé de X)
Un propriété intéressante est que X'AX + X'BX = X'(A+B)X
Etre à l'intersection de deux droite, c'est minimiser la somme de deux erreurs quadratiques.
Ainsi le point B minimise l'erreur associé à la somme des quadriques associés à AB et BC (noté Q[B])
Ainsi le point C minimise l'erreur associé à la somme des quadriques associés à BC et CD (noté Q[C])
On construit X de sorte à minimiser X'(Q[B] + Q[C])X.
On pose Q[X] = Q[B] + Q[C]
Donc X minimise X' Q[X] X
Donc, on passe de (B,Q[B]) , (C,Q[C]) à (X,Q[X]). On vient de supprimer 1 segment et de calculer la quadrique de X.
Ensuite on itère.
On choisit BC de sorte que si on calculait X, l'erreur serais la plus petite possible.
Il y a des propriété intéressantes. On peut montrer que minimiser l'erreur (trouver X et l'erreur) d'une quadrique peut s'obtenir en inversant la matrice et en prenant 3 des composante de la matrice.
Si tu veux, on peut faire un petit projet github qui réalise les étapes 1,2 et 3.