Discussion :

[Nehmé]

Salut,

Connaissant les coordonnées d'un ensemble de points dans le repère (XY), je cherche un algorithme permettant de trouver les 4 sommets du plus petit quadrilatère englobant ces points ou du quadrilatère approximant le mieux possible la surface formée par ces points.

Il existe des algorithmes permettant de trouver l'envellope convex d'un ensemble de points (Graham scan) mais le problème c'est que cette enveloppe n'est pas necessairement un quadrilatère.

- Les 4 sommets du quadrilatère recherchés peuvent faire partie de l'ensemble de points ou non, ca dérange pas.

toute suggestion, complète ou non est appréciée !

[souviron34]

toute suggestion, complète ou non est appréciée !

et tout effort de ta part, complet ou non, dans la recherche et l'exposé de ta pensée et de ta solution, est apprécié

[ToTo13]

Bonjour,

renseigne toi sur tout ce qui est : "bounding box" ou "oriented bounding box". c'est comme cela que ce nomme ton problème.

Tu peux utiliser l'enveloppe convexe pour diminuer le nombre de point dans la recherche de solution.
Ensuite l'axe principal permet d'avoir une bonne première boite pour initialiser la recherche.
Ensuite comme tu es en 2D, je te conseille une petite recherche exhaustive...

[Furikawari]

Commencer par une enveloppe convexe puis énumérer les quadrilatères passant par les sommets de l'enveloppe ? Même en 2D ça risque d'être violent.

Les algos bounding box construisent des rectangles ? Pour un quadrilatère quelconque ça change beaucoup de choses.

[pseudocode]

En premiere approximation, est-ce que les sommets du quadrilatere recherché ne seraient pas sur les 2 axes principaux (analyse PCA) ?

Il y a également le problème des quadrilateres non-convexe, mais je suppose que c'est hors sujet.

[Nehmé]

Merci pour vos réponses.

J'ai dejà réussi à trouver la bounding box orientée qui est effectivement un rectangle. J'ai fait ceci en faisant une rotation de points de 0 à 90 degrés avec un pas choisi. A chaque pas je trouve l'aire de la bounding box et une fois les 90 degrés parcourus je prends la bounding box ayant l'aire la plus petite et je la retourne de -theta à la position initiale des points.
Le problème que c'est un rectangle que j'ai ici et pour plusieurs cas c'est une mauvaise approximation.
C'est pourquoi je cherche un quadrilatère quelconque qui pourra s'adapter au cas et à la forme de l'enveloppe formée par les points.
J'ai cherché longtemps sur google et j'ai essayé de trouver une solution mais j'ai pas encore trouvé mieux que la bounding box orientée.
Je cherche pas une solution complète mais des idées...
Merci encore !

Il existe aussi l'idée du plus petit parallélogramme, mais c'est une solution limitée aussi et une mauvaise approximation pour plusieurs cas.

[Sylvain Togni]

Connaissant les coordonnées d'un ensemble de points dans le repère (XY), je cherche un algorithme permettant de trouver les 4 sommets du plus petit quadrilatère englobant ces points ou du quadrilatère approximant le mieux possible la surface formée par ces points.

Je ne comprend pas la fin.

Pour le plus petit quadrilatère englobant, cela me parait pas très difficile. Il est facile de voir que ce quadrilatère passe forcement par 4 des points (sinon il ne serait pas le plus petit). Du coup il suffit de tester toutes les combinaisons de 4 points et de retenir celle qui donne le plus petit quadrilatère englobant. Si c'est trop lent il doit avoir moyen d'utiliser des heuristiques pour éviter certaines combinaisons.

[JeitEmgie]

Salut,

Connaissant les coordonnées d'un ensemble de points dans le repère (XY), je cherche un algorithme permettant de trouver les 4 sommets du plus petit quadrilatère englobant ces points ou du quadrilatère approximant le mieux possible la surface formée par ces points.

Il existe des algorithmes permettant de trouver l'envellope convex d'un ensemble de points (Graham scan) mais le problème c'est que cette enveloppe n'est pas necessairement un quadrilatère.

- Les 4 sommets du quadrilatère recherchés peuvent faire partie de l'ensemble de points ou non, ca dérange pas.

toute suggestion, complète ou non est appréciée !

Suggestion donc :

le meilleur polygone qui englobe le polygone convexe est lui-même mais s'il a plus de côtés que ce qu'autorise l'énoncé du problème, il faut lui en enlever jusqu'au moment où l'on atteint le nombre de côtés autorisés (ici 4)

la suppression d'un côté se faisant en prolongeant les côtés adjacents jusqu'à leur intersection…
pour décider quels côtés on supprime, on choisit à chaque fois celui dont la suppression ajoute le plus petit triangle, le polygone convexe est donc modifié à chaque étape…

pour chaque triangle ajouté on a les 3 angles (180-a1, 180-a2 et a1+a2-180) et la dimension d'un côté, la surface est facile à calculer…

la condition pour pouvoir supprimer un côté est que la somme des angles intérieurs avec les côtés adjacents soient > 180°…

[Nehmé]

Suggestion donc :

le meilleur polygone qui englobe le polygone convexe est lui-même mais s'il a plus de côtés que ce qu'autorise l'énoncé du problème, il faut lui en enlever jusqu'au moment où l'on atteint le nombre de côtés autorisés (ici 4)

la suppression d'un côté se faisant en prolongeant les côtés adjacents jusqu'à leur intersection…
pour décider quels côtés on supprime, on choisit à chaque fois celui dont la suppression ajoute le plus petit triangle, le polygone convexe est donc modifié à chaque étape…

pour chaque triangle ajouté on a les 3 angles (180-a1, 180-a2 et a1+a2-180) et la dimension d'un côté, la surface est facile à calculer…

la condition pour pouvoir supprimer un côté est que la somme des angles intérieurs avec les côtés adjacents soient > 180°…

Merci pour ton idée, ca l'air intéressant !
Je vais voir ca plus en détails et je te donnerai des nouvelles.

[souviron34]

Ou alors je ne comprend rien du tout, mais il me semble que la réponse au problème initial est triviale :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
minx = INT_MAX
miny = INT_MAX
maxx = -minx
maxy = maxx
 
pour i = 0 jusqu'à i < N
 
   si x(i) < minx
      minx = x(i)
   fin si
   si x(i) > maxx
      maxx = x(i)
   fin si
   si y(i) < miny
      miny = y(i)
   fin si
   si y(i) < maxy
      maxy = y(i)
   fin si
 
fin pour
 
Sommet[1] = (minx, miny)
Sommet[2] = (maxx, miny)
Sommet[3] = (maxx, maxy)
Sommet[4] = (minx, maxy)

Suis-je complètement à côté de la plaque ??

[pseudocode]

Ou alors je ne comprend rien du tout, mais il me semble que la réponse au problème initial est triviale. Suis-je complètement à côté de la plaque ??

Tu as calculé l'AABB (axis-aligned bounding box) mais le PO cherche le plus petit quadrilatere couvrant (par forcement un rectangle, et pas forcément aligné avec les axes).

[souviron34]

ok mais une lègère variation (en ajoutant ds ifs croisés sur y quand on trouve le x min ou max) donnera les points, non ??

[Nehmé]

Suggestion donc :

le meilleur polygone qui englobe le polygone convexe est lui-même mais s'il a plus de côtés que ce qu'autorise l'énoncé du problème, il faut lui en enlever jusqu'au moment où l'on atteint le nombre de côtés autorisés (ici 4)

la suppression d'un côté se faisant en prolongeant les côtés adjacents jusqu'à leur intersection…
pour décider quels côtés on supprime, on choisit à chaque fois celui dont la suppression ajoute le plus petit triangle, le polygone convexe est donc modifié à chaque étape…

pour chaque triangle ajouté on a les 3 angles (180-a1, 180-a2 et a1+a2-180) et la dimension d'un côté, la surface est facile à calculer…

la condition pour pouvoir supprimer un côté est que la somme des angles intérieurs avec les côtés adjacents soient > 180°…

Salut JeitEmgie,

Après avoir essayer ton idée un peu plus en détails, je crois que c'est vraiment brillant !
Ceci me donne la réponse à ma question. Je n'ai pas encore regardé au niveau programation, donc je ne sais pas trop si ca serai long ou non. mais ce qui est sure c'est que ca serai plus long que trouver l'enveloppe convex puisqu'il faut commencer par là.
C'est sure que dans ce genre de problème il est toujours possible d'aller plus loin... Je me demande si selon la politique du forum je dois déclarer la discussion comme résolu ou laisser le sujet ouvert pour optimisation ?

Merci à tous

[JeitEmgie]

Salut JeitEmgie,

Après avoir essayer ton idée un peu plus en détails, je crois que c'est vraiment brillant !
Ceci me donne la réponse à ma question. Je n'ai pas encore regardé au niveau programation, donc je ne sais pas trop si ca serai long ou non. mais ce qui est sure c'est que ca serai plus long que trouver l'enveloppe convex puisqu'il faut commencer par là.
C'est sure que dans ce genre de problème il est toujours possible d'aller plus loin... Je me demande si selon la politique du forum je dois déclarer la discussion comme résolu ou laisser le sujet ouvert pour optimisation ?

Merci à tous

hélas…

le test avec le pentagone régulier comme enveloppe convexe montre que la solution optimale n'est pas trouvée…

mais l'idée générale va dans la bonne direction… (partir du polygone convexe et supprimer les côtés en trop…)

c'est la méthode de choix qu'il faut améliorer…

ceci devrait être mieux :

pour chaque sommet de l'enveloppe convexe il faut trouver la droite qui passe par lui et qui en remplaçant les 2 côtés qui se joignent en ce sommet, minimise la surface ajoutée…

cette droite est entre les 2 extrêmes qui sont les prolongements des 2 côtés : celui qui précède le premier côté du sommet examiné, et celui qui suit le deuxième côté de ce sommet…

si on examine le sommet S1 ente le côté C1 et le C2, avec a1 l'angle intérieur entre C1 et C2, l'angle b entre cette droite et le côté C1 au sommet S1 oscillera entre 0 et 180° - a1

et il faut minimiser la somme des surfaces des triangles T1 et T2 :
T1 ayant pour base C1 et angles adjacents 180°-a0 et b
T2 ayant pour base C2 et angles adjacents 180°-b-a1 et 180°-a2
en fonction de l'angle b…

(on remarquera que pour b=0° et b=180°-a1, on retrouve les triangles de la proposition initiale…)

[souviron34]

j'ajouterais que, plutôt que de rentrer dans la minimisation des surfaces et un calcul somme toute assez complexe, le simple fait de rajouter les intersections des côtés entre chaque sommet, et de reprendre l'élimination 1 par 1 devrait donner la solution...

Car il faut

1) que ce soit convexe
2) que ça englobe tout

Donc, chaque sommet de l'enveloppe convexe est dedans
De plus, comme l'a dit JeitEmgie, l'intersection des côtés donne le point minimal convexe entre ces 2 côtés.

Les sommets du quadrilatère sont donc forcément parmi ces N points.

On aurait donc :

• calcul de l'enveloppe convexe
• calcul et insertion des intersections 2 à 2
• elimination jusqu'à ne plus avoir que 4 sommets avec à chaque fois test : si sommet(i) intérieur à polygone(N - sommet(i)), suppression du sommet i.

[Zavonen]

On aurait donc :

* calcul de l'enveloppe convexe
* calcul et insertion des intersections 2 à 2
* elimination jusqu'à ne plus avoir que 4 sommets avec à chaque fois test : si sommet(i) intérieur à polygone(N - sommet(i)), suppression du sommet i.

Le problème est que le processus d'élimination des sommets est non déterministe, même à l'intérieur de l'ensemble des sommets 'éliminables', et que si on retient un critère de minimalité pour le choix de l'éliminé à chaque étape, rien ne prouve qu'on arrive à une optimisation après plusieurs itérations.