Maximiser surface d'un quadrilatère

[fatal_error]

Hello all,

J'ai un polygone convexe (que j'appèle P) dont je connais les cordonnées (2D, entières)

Je cherche un quadrilatère (non croisé) qui maximise l'IoU.

Voir par ex la définition ici: https://www.pyimagesearch.com/2016/11/0 ... detection/
(iou = areaOverlap/areaUnion)

Pour l'instant j'ai une approche naïve:
Je prends 4 points parmi les points de P qui forment mon Q.
Je calcule l'aire de Q, et je garde le quadruplet pour lequel mon Q est le plus grand.
(iou = area(Q)/area(P))

Deux pb:
1. tous mes Q générés sont complètement inscrits dans P mais pe qu'il existe des quadrilatères avec qq sommets en dehors mais qui donnent un IoU plus grand

2. inefficient temporellement: si P a 100 pts, je dois tester 4M possibilités....

Auriez vs qqch de mieux?

[Ben314]

Salut,
Bon, déjà, ça :

(iou = area(Q)/area(P))

, j'espère que c'est une faute de frappe vu que, comme on nom l'indique, .
Ensuite, ce que j'essayerais de programmer, c'est, partant d'un quadrilatère donné Q=(ABCD), de regarder ce qui se passe si on déplace un des points, par exemple A, d'un "tout petit pas" dans une certaine direction.
Concernant les augmentation/diminution de surface que ça provoque sur et sur en fait, tout dépend de la façon donc le polygone P coupe les arrêtes [AB] et [AD] du quadrilatère Q.
Reste à voir si c'est facile à mettre en œuvre vu qu'il faut en permanence connaître les position des intersections du bord de P avec le bord de Q et que je pense que ça doit pas être malin du tout de les recalculer à chaque modification de la position d'un des 4 points A,B,C,D....

[danyL]

une idée au pif (pour limiter les nombres de points de P à traiter)
calculer le barycentre des points du polygone
et les distances entre chaque point et le barycentre

normalement d'un point au suivant, sa distance par rapport au barycentre varie peu
peut etre effectuer un traitement (lequel je ne sais pas) sur les variations de la distance et garder seulement les points 'significatifs' en entrée de ton programme

[fatal_error]

bj messieurs,

j'espère que c'est une faute de frappe vu que..

nan c'est pas une faute de frappe.
Dans le cas de mon approche naïve, Q est complètement compris dans P donc P inter Q = Q
et P union Q = P mais oui la formule est bien sûr fausse si on enleve le fait que Q est compris dans P.
Je voulais juste expliquer pourquoi je cherchais le Q le plus grand.

de regarder ce qui se passe si on déplace un des points, par exemple A, d'un "tout petit pas" dans une certaine direction.

j'ai un peu de mal à voir (en fait je vois pas du tout je dessine comme un abruti mais je connecte pas..) si:
je fixe B,C,D
je trouve A qui maximise iou (Amax)
est-ce que si (du coup) je fixe A(avec Amax), et je cherche cette fois B qui maximise iou, etc
une fois que j'ai déterminé Amax,Bmax,Cmax,Dmax j'ai bien mon maximum global?

une idée au pif (pour limiter les nombres de points de P à traiter)

actuellement c'est ce que je fais, j'utilise approxPolyDp de opencv (algo: https://en.wikipedia.org/wiki/Ramer%E2% ... _algorithm)

[Ben314]

Perso (et c'est ta première question), ça m'étonnerais plus que beaucoup que le quadrilatère ayant le plus grand IoU soit contenu dans Q, sauf cas très particulier pour Q (par exemple si Q est déjà un quadrilatère évidement...)

Sinon, concernant mon truc de déplacer A, pour Q et A,B,C,D fixés, si tu déplace A en le mettant en A' très proche de A, les modifs que ça produit sur les surfaces sont celles induites par les triangles AA'B et AA'C qui, vu que A' est proche de A sont "tout en longueur" et tu peut approximer la surface de la partie des triangles qui appartient à Q en regardant quels morceaux des segments [AB] et [A'B] sont dans Q.

En fait, dit de façon pédante, ça correspond à calculer la différentielle de la fonction qui, pour Q et B,C,D fixé, associe à A la valeur de l'IoU de P et de A. Le but est évidement de trouver une C.N.S. "visuelle" correspondant au fait que cette différentielle est nulle.

Si j'ai du temps, je regarderais ce que ça donne si on fait le calcul....