Plus petit quadrilatère quelconque englobant un ensemble de points en 2D

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 !

Citation:

---

Envoyé par Nehmé

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é :D

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...

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.

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.

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.

Ca veut dire quoi, le plus petit quadrilatère ?
Celui dont l'aire est minimale ? Celui dont le périmètre est minimal ? C'est pas forcément la même chose. Je me trompe ?

je suis d'accord que dans certain cas c'est pas pareil, mais c'est pas important pour moi. L'important c'est que ce quadrilatère approxime le mieux possible l'enveloppe convexe. Dans mon cas le quadrilatère ayant l'aire la plus proche de l'aire de l'enveloppe convexe est le meilleur, mais pour d'autres applications le critère de périmètre serait plus pertinent. De toute façon, que ce soit basé sur le périmètre ou l'aire ça me conviendrai !

Merci

Citation:

---

Envoyé par Nehmé

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.

Faut pas oublier aussi la forme du quadrilatère. sinon avec un rectangle on peut obtenir la même air ou le même perimètre. En gros le quadrilatère engloppant tous les points et ayant la plus petite air ou perimètre et le meilleur. Tu peux immaginer 4 ammortisseurs soudés ensembles sur leurs sommets et que tu veux les placer le mieux possible autour de l'enveloppe formée par les points.

Le quadrilatère passant par 4 points n'est pas souvent le plus petit. fait le pour un hexagonne et tu verras.

Citation:

---

Envoyé par 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.

---

Je ne suis pas sure de qu'est ce que c'est les 2 axes principaux d'un ensemble de points ?

Citation:

---

Envoyé par Nehmé

Le quadrilatère passant par 4 points n'est pas souvent le plus petit. fait le pour un hexagonne et tu verras.

---

Lequel ? Il y en a une infinité !

Par contre le plus petit quadrilatère englobant passe forcement par au moins 4 points (de l'enveloppe convexe, d'ailleurs).

Citation:

---

Envoyé par Sylvain Togni

Lequel ? Il y en a une infinité !

Par contre le plus petit quadrilatère englobant passe forcement par au moins 4 points (de l'enveloppe convexe, d'ailleurs).

---

en pièce jointe un hexagone et un exemple de quadrilatère englobant. trouve moi un meilleur passant par 4 points de l'hexagone

Petit soucis sémantique peut-être, parce que pour moi ce quadrilatère passe par 4 points (par 6 plus exactement).

Citation:

---

Envoyé par Sylvain Togni

Petit soucis sémantique peut-être, parce que pour moi ce quadrilatère passe par 4 points (par 6 plus exactement).

---

Ok je comprend ce que tu veux dire !
les segment du plus petit quadrilatère passe par 4 points mais les sommets de ce quadrilatère ne font pas necessairement partie de l'ensemble de points.

ok oui à première vue je crois que je suis d'accord.

Problème intéressant. Je pense qu'avant de commencer à réfléchir sur un algo il faudrait se demander si notre quadrilatère a plus de contraintes que de passer par 4 points de l'enveloppe convexe. Et encore faudrait déjà démontrer ce dernier mathématiquement.

Comme autre contrainte on pourrait penser qu'il passe par une arête ou deux de l'enveloppe convexe, etc. Mais comme je suis nul en topologie je ne pourrais pas vous aider plus que ça :D.

Citation:

---

Envoyé par TanEk

il faudrait se demander si notre quadrilatère a plus de contraintes que de passer par 4 points de l'enveloppe convexe.

---

Contre-exemple: un "cercle" (ou du moins un polygone regulier avec beaucoups de cotés). Les sommets du quadrilatere englobant ne sont pas des points du "cercle".

Citation:

---

Envoyé par pseudocode

Contre-exemple: un "cercle" (ou du moins un polygone regulier avec beaucoups de cotés). Les sommets du quadrilatere englobant ne sont pas des points du "cercle".

---

TanEk veut dire que les segments du quadrilatère passe par 4 points du cercle ou du polygone et non pas que les sommets du quadrilatère conside avec 4 des sommets du polygone par exemple... on en a dejà en parler dans les messages précedent. regarde ds la page 1 l'exemple de l'hexagone

Citation:

---

Envoyé par Nehmé

TanEk veut dire que les segments du quadrilatère passe par 4 points du cercle ou du polygone et non pas que les sommets du quadrilatère conside avec 4 des sommets du polygone par exemple...

---

Ah... ok. Je n'avais pas compris, désolé. :oops:

Citation:

---

Envoyé par 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 !

---

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°…

Citation:

---

Envoyé par JeitEmgie

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.