Bonjour ,

je pense que cela revient à chercher pour chaque abscisse le point ayant la même abscisse et l'ordonnée la plus élevée .

Cordialement

Je ne suis pas sûr car il y a un sens aller et retour dont il faut tenir compte...

Voici un exemple de polygone dont je cherche à trouver les coordonnées de chaque point extérieur A, puis B, puis C, etc.

...

A oui , je pensais que tous les rectangles avaient leur origine en (0,0) et étaient imbriqués comme indiqué dans l'énoncé .
Sur le schéma , ils sont empilés ou entassés . Ce n'est  pas pareil et effectivement ça rend l'algorithme bien plus compliqué .
Par contre l'énoncé précise aussi  "aucun point des autres rectangles ne peut avoir de coordonnées inférieures" (à (0,0)?) .
Donc les rectangles  R5  et  R7   ne devraient pas apparaitre .

Ah oui, effectivement, je me suis fixé comme contrainte le fait de ne pas avoir de y et de x inférieurs à 0 afin que se soit moins compliqué.

Cependant, lorsque j'aurai trouver comment faire ainsi, je passerai à cette étape suivante.

Je n'ai pas écrit d'algorithme mais j'envisagerai la stratégie suivante

- ne se préoccuper que des côtés horizontaux .
       donc 8 rectangles donnent  16  côtés (8 bas et 8 hauts)
- ranger les données dans un tableau comme ci après par exemple avec des redondances pour faciliter les traitements .
- Eliminer les côtés non extrêmes  comme R1h et R2b  et ne garder que les côtés les plus bas et les plus hauts
- regrouper les côtés de même ordonnée et jointifs pour former des segments
      R2h et R3h  donnent  S1 (R2 xd , R3 xf , o)
      R6h  donne  S2(R6xd , R6xf , o)

Les extrémités de tous ces segments donnent les points recherchés .

Merci fm_31, j'avais commencé un fichier Excel sur lequel je fais des tests de formules

https://we.tl/nECBINLWMQ

Je me rends compte que ma stratégie est non seulement pas facile à mettre en oeuvre mais surtout incomplète . Et en regardant de près ce qui caractérise les points extérieurs , je pense qu'on peut faire bien plus simple .
En effet les points extérieurs ont des coordonnées uniques ou partagées avec deux autres coins .
Il suffit donc , pour chaque coin  c  ,de compter combien il y a d'autres coins ayant les mêmes coordonnées

  -  0  ou 2 autres coins : le coin  c  est extérieur .

Attention : cette stratégie comptabilise les points situés dans des cavités fermées comme des points extérieur .

Bonjour,

Il faut définir le contour "extérieur" en suivant un chemin comme suite de vecteurs.
Ayant un vecteur de départ que l'on sait "extérieur" et qui impose le sens de parcours global (sens aiguilles montre par exemple ) on détermine le vecteur suivant à gauche, tout droit, ou à droite.
Suivant direction et sens du vecteur courant le choix est alors fait par comparaison des points dont une des coordonnées correspond à l'extrémité du vecteur courant (algorithme pas difficile).
Pour le choix du vecteur initial il suffit de déterminer le rectangle enveloppe extérieure et un des rectangles dont un côté est sur cette enveloppe.

Voici un premier jet de l'algo que je vais vérifier, corriger et optimiser par la suite

On part du couple (x0;y0) = (0;0) car c'est le point extérieur de référence dont on peut être sûr qu'il est seul et unique

S'il existe un couple (xi;yi) = (x0;y0) appartenant à 2 des 3 colonnes différentes de celle du couple (x0;y0)

Alors

Si (x0;y0) appartient à la colonne bg et (xi;yi) appartiennent aux colonnes hd ou bd (alors on compare (x0;y0) aux (xi;yi) du rectangle de la colonne bd)
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bg ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et (xi;yi) appartiennent aux colonnes hd ou hg (alors on compare (x0;y0) aux (xi;yi) du rectangle de la colonne sg)
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sd ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et (xi;yi) appartiennent aux colonnes bd ou bg (alors on compare (x0;y0) aux (xi;yi) du rectangle de la colonne bg)
alors on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et (xi;yi) appartiennent aux colonnes bg ou sg (alors on compare (x0;y0) aux (xi;yi) du rectangle de la colonne bg)
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu'à arriver au point (0;0).

S'il existe un couple (xi;yi) = (x0;y0) appartenant à une des 3 colonnes différentes de celle du couple (x0;y0)

Alors

(Cas des bg)

Si (x0;y0) appartient à la colonne bg et (xi;yi) appartient à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bg ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bg et (xi;yi) appartient à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bd ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bg et (xi;yi) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bg ;
on réitère la boucle jusqu'à arriver au point (0;0).

(Cas des bd)

Si (x0;y0) appartient à la colonne bd et (xi;yi) appartient à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bd ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et (xi;yi) appartient à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bd ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et (xi;yi) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sd ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

(Cas des sg)

Si (x0;y0) appartient à la colonne sg et (xi;yi) appartient à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et (xi;yi) appartient à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et (xi;yi) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne bg ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

(Cas des sd)

Si (x0;y0) appartient à la colonne sd et (xi;yi) appartient à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et (xi;yi) appartient à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sd ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et (xi;yi) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sd ;
on réitère la boucle jusqu'à arriver au point (0;0).

S'il n'existe pas un couple (xi;yi) = (x0;y0) appartenant à une des 3 colonnes différentes de celle du couple (x0;y0)

Alors

S'il existe un ou plusieurs xi = x0

Alors

Si (x0;y0) appartient à la colonne bg et xi appartien(nen)t à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;max(yi<y0)) du rectangle Ri de la colonne bd ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et xi appartien(nen)t à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;max(yi<y0)) du rectangle Ri de la colonne bg ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et xi appartien(nen)t à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;max(yi<y0)) du rectangle Ri de la colonne bd ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et xi appartien(nen)t à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;min(yi>y0)) du rectangle Ri de la colonne sg ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

S'il existe un ou plusieurs yi = y0

Alors

Si (x0;y0) appartient à la colonne bg et yi appartien(nen)t à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (min(xi>x0);yi) du rectangle Ri de la colonne sd ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd et yi appartien(nen)t à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (min(xi>x0);yi) du rectangle Ri de la colonne sd ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg et yi appartien(nen)t à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;max(yi<y0)) du rectangle Ri de la colonne bg ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd et yi appartien(nen)t à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;min(yi>y0)) du rectangle Ri de la colonne sg ;
on réitère la boucle jusqu'à arriver au point (0;0).

S'il n'existe pas de yi = y0 et de xi = x0

Alors

Si (x0;y0) appartient à la colonne bg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle Ri de la colonne sg ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne bd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle R0 de la colonne bg ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sg
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle R0 de la colonne sd ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Si (x0;y0) appartient à la colonne sd
alors
on prend comme nouveau (x0;y0) le point (xi;yi) du rectangle R0 de la colonne bd ;
on enregistre l'ancien (x0;y0) comme point extérieur ;
on réitère la boucle jusqu'à arriver au point (0;0).

Bonjour.

Une simple question : les coordonnées des sommets des rectangles sont-elles toujours entières ?

Bonjour bbomaths,

les coordonnées des sommets des rectangles ne sont pas toujours entières.

Par ailleurs, dans mon exemple j'ai mis 9 rectangles mais il peut y en avoir moins comme plus et le polygone final peut être plus complexe comme plus simple (ex.un rectangle).

Dommage...

la stratégie que je t'ai proposé est bien plus simple et vraiment facile à implémenter  .

C'est tout à fait vrai fm_31, je vais la tester avec un Excel ce soir

Je ne suis pas sûr que  Excel   soit le mieux adapté pour ce genre d'algorithme (deux ou trois boucles imbriquées seulement)  . Moi j'écrirais d'abord l'algorithme puis le coderai en python .

Rebonsoir fm_31, oui c'est mieux en codant.

Par contre, quand je rentre dans les détails, j'ai du mal à bien me projeter, peux-tu rentrer dans les détails stp ?

Est-ce que ta stratégie fonctionne pour un cas biscornu comme sur l'image suivante ?

Autre remarque ; j'ai besoin d'avoir les points listés dans un ordre précis et je ne suis pas sûr qu'on les ait avec ta méthode non ?

Bonjour.

Graphique de départ :



Ce que je ferais (à la louche) :

1 / dresser 2 listes des segments horizontaux et verticaux délimités par les sommets des N rectangles.

2 / dresser 2 listes des abscisses et ordonnées des sommets (points noirs sur les axes).

3 / rechercher les extremums Xmin, Xmax, Ymin et Ymax pour délimiter la zone de travail.

4 / rechercher successivement les segments inférieurs de Ymin à Ymax et concaténer leur image projetée sur l'axe des x. Si 2 segments se touchent, les considérer comme un seul.

5 / tester si le segment des concaténations est complet entre Xmin et Xmax ?

-> oui : tous les segments inférieurs trouvés
-> non : y suivant

6 / même principe pour les 3 autres côtés.

Exemple :



puis :

puis :

c'est l'idée de base... le but est remplir le segment de concaténation au fur et à mesure en concaténant en tout ou en partie un nouveau segment horizontal.

Merci bbomaths, c'est très pertinent

J'ai testé ma stratégie , ce qui m'a amené à quelques ajustements mais elle reste simple à implémenter .

Bonjour,

Vu la figure colorée du 11-01-18 à 22:36,
il s'agit bien d'obtenir, dans l'ordre, les points qui forment le contour de l'extérieur blanc de tous les rectangles colorés ?

Dans ce cas, une précaution préalable est de vérifier que tout sommet de rectangle n'est pas sur un coté d'un autre rectangle
et dans ce cas scinder ce dernier en 2 rectangles.
On sera alors certain que le contour sera bien formé de segments (ou vecteurs) appartenant à des rectangles colorés.

Bonjour fm_31 et vham,

vham, il s'agit effectivement d'avoir dans l'ordre les points qui forment le pourtour de la figure finale.

Merci beaucoup fm_31, ta stratégie est très optimisée, vraiment bien joué. Est-ce que tu peux obtenir les points dans l'ordre aussi facilement que ce qui t'a permis de les obtenir dans le désordre ?

Obtenir les points dans l'ordre ne devrait pas être très compliqué . Je vais y réfléchir en partant des points dans le désordre . Est-ce qui si on donne une liste de segments (dans le désordre)  , ça pourrait convenir ?

Je vous avoue que l'idéal serait d'avoir les points et donc les segments dans l'ordre :s

Pour vous en dire un peu plus sur l'application de ce sujet, j'ai un algorithme qui génère des plans composés de rectangles accolés et je travaille sur la mise en place d'une étude quantitative automatisée de ces derniers.

J'ai alors besoin de séparer les murs intérieurs et extérieurs tout en trouvant les points extérieurs dans l'ordre.

Bonjour,

Je propose un algorithme qui donne les Points extérieurs dans l'ordre :
On suppose que l'on connait les coordonnées x,y des 4 sommets de chaque rectangle
le sens de parcours étant celui des aiguilles d'une montre

Le premier point de départ est le sommet le plus bas sur le coté le plus à gauche
(il est ensuite donné par la sortie de la routine précédente)
on suit le rectangle sur son coté-gauche,
s'il y a un point de même abscisse avant le sommet gauche-haut,
     on prend ce point comme nouveau départ pour un rectangle à suivre sur son coté-bas (ne se produit pas pour le premier coté parcouru)
     on mémorise le point
sinon
     le sommet gauche-haut est-il sur un coté-bas d'un rectangle ou un sommet bas-droit d'un rectangle ? (ne se produit pas pour le premier coté parcouru)
          Oui, on prend ce point comme nouveau départ pour un rectangle à suivre sur son coté-bas
          on mémorise le point
     Sinon  le sommet gauche-haut est-il un sommet bas-gauche d'un rectangle ?
          Oui,  on prend ce point comme nouveau départ pour un rectangle à suivre sur son coté-gauche
     Sinon on mémorise le sommet
     et on le prend comme nouveau départ pour un rectangle à suivre sur son coté-haut

il y a 4 routines de même nature en remplaçant les noms des cotés et des sommets circulairement,

Bonsoir vham,

Je pense que ton algo ressemble un peu à celui que j'ai proposé le 11 à 00h08

Bonjour,

Voir aussi le 10-01-18 11:17
L'essentiel est d'avoir une position courante comprenant
Le numéro du rectangle
Le côté du rectangle (direction suivie parmi les 4 possibles)
Et le point de départ (pas forcément un sommet du rectangle courant)

Reste à coder, PYTHON, VB.net, C++, autre?

Après avoir passé pas mal de temps à chercher une stratégie simple à partir de mes points dispersés , je suis revenu à l'ensemble des points avec une stratégie simple que j'ai commencé à implémenter et posterai dès que fini .

Elle est basée sur l'observation suivante :

à partir de n'importe quel point , le point suivant est soit en face , soit à droite , soit à gauche . Pas  de retour en arrière . Et le trajet sur lequel il est (unique) est celui qui comporte un nombre de points possibles impair . Et sur ce trajet , c'est le point le plus proche .

La liste des points obtenus comporte des points intermédiaires qu'il est assez facile de supprimer si nécessaire .

Voila l'implémentation de la stratégie donnée (première partie)

2° partie et résultat .
L'implémentation peut paraitre longue mais les 4 fonctions utilisées sont très semblables ainsi que les 4 blocs de la partie principale .

Bonsoir fm_31,

Désolé pour la réponse tardive, je viens de voir ton retour.

Merci beaucoup c'est très complet et très didactique.

Je vais tester l'algo en détail et m'appuyer dessus en voyant pour supprimer, comme tu l'as indiqué le 13, les points intermédiaires.

Complément pour ne laisser que les angles du contour .
J'ai rajouté un rectangle (r20) à la configuration d'essai pour la rendre plus exhaustive .

Bonjour,

il faut rendre hommage à fm_31 pour le développement de son programme...

J'ai un algorithme qui utilise les propriétés des dictionnaires (dictionary dans Python) et qui rend facile la détection des points du contour qui sont des points "isolés" (dont les coordonnées n'appartiennent qu'à un seul triangle)

il faut numéroter (O à 3) les Sommets de chaque rectangle tous dans le même sens.
Pour tout sommet on prend x comme clé et on forme un élément (y, numéro sommet, numéro rectangle) pour entrer dans une liste "valeur".
on entre dans un dictionnaire des x la liste des éléments ayant la même clé x, et on trie cette liste (suivant les y).
Même création éventuelle dans un dictionnaire des y en intervertissant x et y.
il est alors simple de sortir du dictionnaire les éléments "isolés"
(x, y, numéro sommet, numéro rectangle) triés suivant xy dans une liste,
(y, x, numéro sommet, numéro rectangle) triés suivant yx dans une autre liste.
En prenant dans chaque liste "élément précédent" ou "suivant", fonction du numéro de sommet, (4 possibilités) les sommets se rangent dans l'ordre sur le contour extérieur.

Un grand bravo et un grand merci à vous fm_31, vham et bbomath.

Vous êtes au top.

Il y toujours (ou presque) des solutions . Le tout est d'en trouver qui ne soient pas trop complexes à implémenter .
Bonne continuation .

Merci beaucoup. Bonne continuation.

Bonsoir,

Dans une présentation épurée, mais exécutable (code disponible par copier-coller)

Python 3. Rectangles définis par Bas gauche : x,y   haut droite : x,y
r=[[[0,0],[1,8]],  [[0,8],[2,9]],  [[1,5],[3,8]],  [[1,2],[2,5]],  [[2,3],[4,5]],  [[2,2],[5,3]],
   [[6,2],[9,3]],  [[1,1],[10,2]],  [[10,1],[12,3]],  [[5,0],[11,1]],  [[8,3],[9,6]],  [[6,6],[9,7]],
   [[8,7],[9,8]],  [[6,7],[8,8]],  [[5,5],[6,8]],  [[5,4],[7,5]],  [[5,8],[10,9]],  [[4,9],[10,10]],
   [[9,2],[10,8]]]
print(len(r)," rectangles")
#Il faut tester que le sommet droit-haut soit déclaré après le coin gauche-bas.
#Il faut vérifier que les rectangles ne s'interpénètrent pas. NON FAIT !
#***************************************************************************
# r contiendra les 4 points x,y des rectangles Dans l'ordre
# 0=gauche-bas, 1=gauche-haut, 2=droite-haut,3=droite-bas

def todico(dd,kk,vv):
    if kk in dd:
        vn=dd[kk]
        vn.append(vv)
        vn.sort()
        dd[kk]=vn
    else:dd[kk]=[vv]
dx=dict({})
for i in range(len(r)):
    r[i].insert(1,[0,0])
    r[i].append([0,0])
    r[i][1][0],r[i][1][1],r[i][3][0],r[i][3][1]=r[i][0][0],r[i][2][1],r[i][2][0],r[i][0][1]
    for j in range(4):
        todico(dx,r[i][j][0],[r[i][j][1],j,i])
def isolé(yenx,i):
    if i!=0:
        if yenx[i-1][0]==yenx[i][0]:
            return False
    if i!=len(yenx)-1:
        if yenx[i][0]==yenx[i+1][0]:
            return False
    return True
nxisolé=0
lix2,liy2=[],[]
for k in dx.keys():
    yenx=dx[k]
    for i in range(len(yenx)):
        if isolé(yenx,i):
            nxisolé+=1
            lix2.append([k,yenx[i][0],yenx[i][1],yenx[i][2]])
for i in range(len(lix2)):
    liy2.append([lix2[i][1],lix2[i][0],lix2[i][2],lix2[i][3]])
liy2.sort()
               
contour,n=[],0
point=lix2[0]
while n<len(lix2):
    contour.append([point[0],point[1]])
    n,nsommet=n+1,point[2]
    if nsommet==0:
        p=point[:]
        point=lix2[lix2.index(p)+1]
        if point[0]!=p[0]:
            point=lix2[lix2.index(p)-1]
    elif nsommet==1:
        p=[point[1],point[0],point[2],point[3]]
        point=liy2[liy2.index(p)+1]
        if point[0]!=p[0]:
            point=liy2[liy2.index(p)-1]
        point[0],point[1]=point[1],point[0]
    elif nsommet==2:
        p=point[:]
        point=lix2[lix2.index(p)-1]
        if point[0]!=p[0]:
            point=lix2[lix2.index(p)+1]
    elif nsommet==3:
        p=[point[1],point[0],point[2],point[3]]
        point=liy2[liy2.index(p)+1]
        if point[0]!=p[0]:
            point=liy2[liy2.index(p)-1]
        point[0],point[1]=point[1],point[0]
print("*********************************************************")
print("Contour de ",n," points ",contour)

Mon complément pour ne conserver que les angles du contour comporte une gestion des indices peu optimisée . Voici une version plus rationnelle qui supprime deux tests devenus inutiles .