Discussion :

[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é]

[QUOTE=souviron34;3646784]en ajoutant ds ifs croisés sur y quand on trouve le x min ou maxQUOTE]

merci pour ta réponse.
Je ne comprend pas ta phrase !

[souviron34]

si tu fais :

Code :

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

1
2
3
4
5
6
7
 
   si x(i) < minx
      si y(i) < miny
         minx = x(i)
         miny = y(i)
      fin si
   fin si

tu trouveras le point le plus à gauche avec le y le plus petit

Si tu fais la même chose avec les 4 "coins", tu trouveras les 4 points les plus extrêmes (c.a.d. remplissant les conditions : le point ayant le plus petit x ET le plus petit y, le point ayant le plus grand x ET le plus petit y, etc etc.).

Mais effectivement ça ne donnera pas forcément le quadrilatère englobant.. Enfin je ne crois pas..

Sinon comme on l'a suggéré, des algos plus complexes. Sans doute à base d'enveloppe convexe.

Un autre moyen serait de partir du AABB (comme l'a si joliment précisé pseudocode ), et de chaque sommet lancer un rayon pour atteindre le premier point...

Ou de prendre l'enveloppe convexe, et tenter d'enlever les sommets 1 à 1 jusquà arriver à 4, en vérifiant si la nouvelle ligne (sommet i-1, sommet i+1) fait que le sommet i est à l'intérieur ou à l'extérieur du polygone.

[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

[Zavonen]

Et encore faudrait déjà démontrer ce dernier mathématiquement.

Cela me parait simple par l'absurde si le nuage est fini (donc compact):
Soit ABCD un quadrilatère englobant minimal, et supposons qu'il ne contienne aucun point du nuage. On peut alors déplacer B sur [BC] en direction de C sans rencontrer de point du nuage ce qui contredit la minimalité de ABCD.
Ceci est par contre faux pour des nuages infinis. Un contre exemple est facile à trouver (Prendre pour nuage l'ensemble de tous les points constituant l'intérieur d'un carré).

[TanEk]

Cela me parait simple par l'absurde si le nuage est fini (donc compact):
Soit ABCD un quadrilatère englobant minimal, et supposons qu'il ne contienne aucun point du nuage. On peut alors déplacer B sur [BC] en direction de C sans rencontrer de point du nuage ce qui contredit la minimalité de ABCD.
Ceci est par contre faux pour des nuages infinis. Un contre exemple est facile à trouver (Prendre pour nuage l'ensemble de tous les points constituant l'intérieur d'un carré).

Oui c'est pas bête. Tu as une idée sur l'autre proposition : le quadrilatère passe par une arête (ou deux) du polygone englobant ?

[Zavonen]

le quadrilatère passe par une arête (ou deux) du polygone englobant ?

Le polygone englobant est forcément inclus au sens large dans tout quadrilatère englobant, et contient au minimum un sommet S du polygone englobant. Si S est le seul point du nuage appartenant au quadrilatère on peut réduire la quadrilatère par une homothétie de centre S et de rapport k<1 en un quadrilatère contenant encore tous les points du nuage. Le quadrilatère contient donc forcément un second point, mais (a priori) pas nécessairement sur le même côté.

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

[souviron34]

je ne vois pas très bien ce que tu appelles "non déterministe"..

C'est assez déterministe si un sommet est dans le polygone restant. On doit donc pouvoir simplifier grandement, et j'aurais tendance à penser arriver au max à environ 8 sommets.

Là on peut effectivement tenter chacune des combinaisons et déterminer le plus petit, mais je pense que encore ne fois le même style d'algo que le Gift-Wrapping (ou son principe plutôt), permettrait de s'en sortir en une passe : on ne garde que les sommets pour lesquels les angles sont les 4 max.

En gros ce que disait JeitEmgie

[souviron34]

une autre idée :

une fois le polygone convexe déterminé (avec les intersections incluses), on en détermine le point le plus bas à droite, par exemple (point de départ du Gift-Wrapping).

on a donc (y1,x1).

On suit le polygone jusquà ce que y ré-augmente OU x dépasse le milieu du domaine des x, parmi les sommets. On a donc (y2,x2).

On continue jusquà ce que x ré-augmente OU y ré-augmente.


Ou bien :

on détermine le barycentre du polygone convexe (avec les intersections incluses).
Pour tout ce qui est partie haute (y < y barycentre), on prend les 2 points les plus extrêmes (y le plus faible ET x le plus petit, y le plus faible ET x le plus grand).
On fait la même chose pour la partie basse.

Non ?? ça marcherait pas, ça ??

[pseudocode]

Toutes ces méthodes permettent de trouver un quadrilatère couvrant... Mais qu'en est-il de l'optimalité de la solution ?

[Nehmé]

Une fois les intersections des cotés trouvées, calculer les surface ne prend qu'une simple equation: aire = 1/2*abs[(xb-xa)(yc-ya)-(xc-xa)(yb-ya)]
et donc c'est plus simple de trouver la surface que de re parcourir les points pour chercher des min et max ou barycentre.

Ce qui serai bien, c'est partant des 2 vecteurs directeurs des cotés qu'on veut intersecter, faire un calcul direct ( sans passer par l'intersection ) qui permet de donner un résultat proportionnel à la surface du triangle qui sera former si on intersecte ces 2 cotés. une fois les 2 cotés donnant la plus petite surface localisés, on calcule leur intersection et on élimine les 2 autres points.
J'avais pas bien compris le critère d'angle de JeitEmgie , peut être c'est la réponse à cette question ! un petit croquis sur paint serai génial !

[Furikawari]

edit : je suis trop vieux pour ça

[Nehmé]

Ta formule de calcul d'aire pour un quadrilatère quelconque me semble beaucoup trop simple...

C'est l'air du triangle ajouté !

[Furikawari]

Oui j'avais mal lu...
Je pense qu'il n'est pas très compliqué d'écrire un programme linéaire qui permette de trouver l'optimal (après tout, au pire on a 8 variables). Même si pour ce problème il DOIT exister une solution plus satisfaisante...

[TanEk]

Le polygone englobant est forcément inclus au sens large dans tout quadrilatère englobant, et contient au minimum un sommet S du polygone englobant. Si S est le seul point du nuage appartenant au quadrilatère on peut réduire la quadrilatère par une homothétie de centre S et de rapport k<1 en un quadrilatère contenant encore tous les points du nuage. Le quadrilatère contient donc forcément un second point, mais (a priori) pas nécessairement sur le même côté.

Peut-être mais :

• peut-être que le plus petit quadrilatière englobant n'est pas unique, il peut en exister plusieurs
• s'il en existe plusieurs, peut-être qu'il y en a toujours un qui passe par une arête ou deux du polygone englobant ?
• si ceci est vérifié, ça ne simplifierait-il pas le problème ?

Désolé si mes remarques et questions n'ont aucun intérêt . Au cas où...