Discussion :

[aj3309]

Bonjour,
Sur un fond de carte rectangulaire j'ai une vingtaine de points sur lesquels je veux faire un click de souris pour afficher les informations relatives à ce point.
Je ne veux pas que la zone d'affichage recouvre des points de la carte pour cela je recherche l'algorithme pour trouver
le plus grand rectangle de la carte qui ne contient aucun point.
Ensuite je m'appuierai sur le centre de ce rectangle pour placer ma zone d'affichage.
Je veux faire cela par programme car j'ai beaucoup de cartes à traiter.

[tbc92]

Ah.. problème original et intéressant.
Il y a peut-être quelques questions complémentaires à éclaircir avant d'avancer dans le dur.

On a un fond de carte, disons un quadrillage (0 à 100)x(0 à 70), un rectangle plus large que haut.
On a une vingtaine de points dans ce rectangle. (les obstacles)

On clique quelque part dans ce fond de carte, sur le point (a,b). On suppose que ce point (a,b) ne coïncide avec aucun des 20 points obstacles, mais ce point (a,b) peut être coincé entre 2 ou 3 points obstacles tout proches.
On cherche un rectangle qui CONTIENT le point(a,b) et avec la surface la plus grande possible.
Le point (a,b) n'est pas forcément au centre du rectangle cherché, il doit juste être dans le rectangle.
Et si le point (a,b) est à la 'périphérie' des 20 points, c'est cool, on peut aller jusqu'aux bords du fond de carte. Par exemple, si les 20 obstacles sont dans une ellipse au centre de l'écran, si on clique sur le point (a,b)=(78,52) à la frontière de cette ellipse, on peut aller jusqu'à l'angle(100,70)
C'est la seule contrainte ?
Si on se retrouve avec un rectangle de 5 pixels de large, et 50 pixels de haut, c'est bon ?
Et en terme d'inclinaison, j'imagine qu'on veut un rectangle 'horizontal/vertical', pas un rectangle orienté à 45° par exemple... pour se faufiler entre les points ?

[aj3309]

Merci pour cette première réponses. Voici les précisions demandées.
Pour être concret mon nuage de points est constitué par les adresses sur la carte d'un groupe de personnes qui veulent covoiturer mais ne se connaissent pas.
Ces 300 personnes font partie de mon club de randonnée
En amont pour chacune des 300 personnes j'ai constitué des cartes des 20 personnes domicilés au plus près de cette personne.
En cliquant sur un des 19 points de la carte une personne pourra voir les information pour éventuellement contacter une personne.
Pour ne pas produire de solutions inutilisables je compte mettre un paramètre (LargeurMini, HauteurMini).
Le rectangle recherché est horizontal pour présenter les informations d'une manière simple.
Le rectangle d'affichage sera légèrement plus petit que le rectangle trouvé pour bien visualiser les points qui se trouvent sur les bords du rectangle trouvé.
Pour construire le jeu d'essai , je procède a l'envers en plaçant 4 rectangles identiques et symétriques dans les 4 quartiers du rectangle de la carte
et je place les points sur les bords des 4 rectangles , et j'attends l'algorithme qui me retrouvera ces 4 rectangles a partir des 20 points.
Mes fonds de carte obtenus automatiquement par programme sur les sites de l'IGN font 800X1200 pixels.
Pour cette recherche du rectangle ayant la plus grande surface possible je veux faire une recherche à priori sans partir d'un point précis ,
c'est à dire un rectangle qui ne cache aucun point.
Cet algorithme doit fonctionner sans interaction avec un utilisateur.
Par la suite j'envisage d'exclure le point de l'utilisateur pour lequel je construis la carte
car ce n'est pas grave que le point de son domicile soit caché par le rectangle d'information ,
en principe il sait ou il habite et ce qu'il recherche c'est le domicile d'un éventuel covoitureur.
De plus par construction le domicile de l'utilisateur pour lequel je construis la carte est dans une position proche du centre de la carte,
cela devrait permettre à l'algorithme de trouver un meilleur rectangle.

[Guesset]

Bonjour,

Une proposition sans réflexion trop approfondie (ça fait mal à la tête ):

• Trier les points par x croissant (non strictement) et en secondaire par y croissant. Tout autre ordre serait aussi valide
• Pour chaque point chercher le prochain point, donc à droite (évtiter les points sur la même verticale car ce sont des rectangles hors bords que nous cherchons), noter Xmax=X et Ymin=Y ou Ymax=Y selon que Y < Ymax (initialisé à très grand) ou Y > Y mini (initialisé à très petit)
• Continuer jusqu'à avoir des valeurs pour pour Ymin et Ymax.
• Continuer jusqu'à rencontrer un point (X',Y') dont Y' est entre Ymin et Ymax. Calculer la surface (X'-X)*(Ymax-Ymin). Correction : Il reste 2 possibilités de poursuivre selon Ymin, Ymax=Y' ou Ymin=Y', Ymax. Non il n'y pas de choix, seul le couple Ymin, Ymax qui encadre le Y d'origine est à étudier Donc pas d'arborescence.
• Continuer selon ce processus en mémorisant la surface la plus grande (et ses coordonnées bien sûr). Il convient sans doute de se fixer un ratio limite pour éviter d'avoir un logement du type des petites annonces de Pierre Darc : appartement de 25 mètres de long sur 1 mètre de large. Cela réduira mécaniquement la profondeur de l'arborescence recherche.

Remarque : Le fait de partir dans un sens ne devrait pas faire perdre les rectangle optimaux à gauches qui auront déjà été trouvés à partir de leur point le plus à gauche.

Ce qui est intéressant me semble-t-il, c'est que les rectangles ne sont pas déterminés par les coins mais par des points situés sur leurs cotés. L'utilisation du ratio est non seulement utile mais nécessaire sinon, entre deux points consécutifs, nous avons un rectangle de surface infinie (pas de haut ni de bas). Attention le ratio r s'applique aussi bien à X/Y qu'à Y/X.

Salutations

[mach1974]

Il faut calculer l'intersection de tous les points et considérer ce point comme le centre du carré

[aj3309]

Merci pour vos premières idées je vais les intégrer dans ma réflexion.
Pour mieux cerner le problème j'ai tenté de faire une typologie des rectangles solution que je vous livre :
1 Les rectangles qui s'appuient sur 1 point et 3 côtés de la Carte (1 en entier et 2 partiellement) ,
je pense que ces rectangles sont au nombre de 4 car par construction je n'ai pas de points sur les 4 côtés de la Carte
2 Les rectangles qui s'appuient sur 2 points et 2 côtés de la Carte ( partiellement) ,
je pense que ces rectangles sont au nombre de 4 car par construction je n'ai pas de points sur les 4 côtés de la Carte et que j'ai au moins 8 points.
3 Les rectangles qui s'appuient sur 3 points et 1 côtés de la Carte ( partiellement) , pour l'instant je n'arrive pas a dénombrer ces rectangles.
4 Les rectangles qui s'appuient sur 4 points et aucun côté.
Bien entendu parmi tous ces rectangles solution je choisirai celui qui a la plus grande surface.
Pouvez-vous me critiquer cette typologie et éventuellement me l'affiner.

[tbc92]

Dans cette histoire, j'ai l'impression qu'on cherche un compromis.
On veut un rectangle plutôt grand, plutôt bien placé (proche d'un point cible donné, vers le centre de la carte), et plutôt équilibré (c'est à dire adapté pour écrire un texte sur 2 ou 3 lignes, donc en on va préférer un rectangle de 200x50 (200 en horizontal x 50 en vertical) plutôt que 310 x 33, même si le 2ème est plus grand en surface.
C'est ce que je pensais au début.
Maintenant, j'ai l'impression que le rectangle solution idéal est presque toujours vers le bord de la carte.

[Guesset]

Bonjour,

En résumé, on cherche le plus grand rectangle sans point qui soit plus long que haut (rY*dX > rX*dY pour un ratio r = rX/rY > 1). Avec certainement une hauteur supérieure à une valeur minimale ne serait-ce pour pouvoir y écrire.

Ratio r minimal recherché ? Hauteur minimale recherchée ?

Selon ces critères, il y aura plus ou moins de cas à étudier. Attention : des critères trop contraignants pourraient interdire de trouver une solution.

Salutations

[aj3309]

Bonjour,
Une première piste pour l'algorithme que je recherche.
Les 19 abscisses des points de covoitureurs déterminent 20 segments d'abscisse sur lesquels in n'y a pas de points covoitureurs.
Il en est de même pour les 19 ordonnées.
A partir de cela on obtient 20X20 soit 400 zones qui ne contiennent pas de points de covoitureurs mais qui en ont sur leurs bords.
Sur les rangées horizontales puis verticales il faut recoller les zones consécutives qui n'ont pas de points de covoitureurs sur leur bord commun.
Il faut éliminer les zones dont la largeur est inférieur à une largeur mini et celles pour lesquelles la hauteur est inférieure à une hauteur mini.
Il faut ensuite calculer pour chaque zone qui restent le ratio largeur hauteur et éliminer celles qui ont un ratio inférieur a un ratio mini.
Pour terminer on calcule la surface des zones, un tri va donner le classement et déterminer le rectangle maximum
sachant qu'il peut y avoir plusieurs zones à la première place.
Avant de me lancer dans la programmation je vais essayer de peaufiner cet algorithme car je sais que tout peut arriver même le pire.

[Guesset]

Bonjour aj3309,

...Avant de me lancer dans la programmation je vais essayer de peaufiner cet algorithme car je sais que tout peut arriver même le pire.

Un peu d'optimisme, le pire est seulement probable

Je me demande s'il ne faudrait pas aussi un ratio dX/dY maximal. Récupérer, par exemple, une zone qui fait toute la largeur sur une hauteur peu importante (mais suffisamment pour que la surface l'emporte) conduit à un texte qui sera très large, se faufilant entre les points. Cela peut être acceptable tout en haut ou tout en bas, comme un titre ou une légende, mais pas, me semble-t-il, en plein milieu de carte.

Si la méthode heuristique sans arborescente donne vite de bons résultats, elle ne peut garantir l'optimum.

Salut

[tbc92]

Les 400 zones que tu vas définir ainsi sont beaucoup plus petites que ce que tu pourras faire au final.
Pour le vérifier, prend un papier quadrillé. Sélectionne un carré 20x20 ; Sur chacune des 19 lignes verticales , tu poses un point, en faisant en sorte qu'il y ait un seul point par ligne horizontale.
A l'arrivée, ça te définit effectivement un quadrillage de 400 cases : 400 petits carreaux 1x1.
Alors que dans les faits, il y a plein d'endroits où tu as des rectangles 6x2 ou 7x3 ou même plus grands qui sont vides.

Du coup, proposition :
- On se limite à explorer 50x50 centres possibles pour notre rectangle (c'est une proposition ... ça paraît largement suffisant).
- On vise des rectangles avec un certain profil ( 3 fois plus large que haut, ou 4 fois plus large que haut)
Pour chacun des 50x50 centres possibles, on calcule le rectangle le plus grand qu'on peut mettre à cet emplacement, avec une excentricité de 3 ou de 4 ; on reviendra plus bas sur cette étape.
- on conserve au final la position qui correspond à ce rectangle le plus grand. Avec éventuellement un raffinement, on privilégie un rectangle proche du centre, plutôt qu'un rectangle dans un coin, à surface à peu près identique.

Pour trouver le rectangle le plus grand, de centre imposé, avec une excentricité 3 (... et on peut remplacer 3 par ce qu'on veut dans la formule)
- On a choisi un centre, c'est le point (x0,y0) ; par construction, on va tester différents centres.
- Les 19 points sont les Points (xI,yI)
- Pour chacun des 19 points, on calcule
R = min ( (x0-xI)/racine(3) , (y0-yI)*racine(3) )
- On calcule ce R pour chacun des 19 points, et on garde le R minimal.
- Pour ce centre (x0, y0), on peut dessiner un rectangle de centre (x0,y0), de grand axe R*Racine(3) et de petit axe R/Racine(3), et qui ne touche aucun des 19 points.

[aj3309]

Bonjour,
Je n'ai pas encore étudié toutes vos propositions mais vos notions de ratio ou de profil de rectangle ont attiré toute mon attention.
Je veux afficher les informations suivantes dans le rectangle recherché.
Une première ligne avec Nom Prénom Numéro de téléphone.
Une deuxième ligne avec Adresse.
Une troisième ligne avec Code postal Commune.
En balayant le fichier des 300 covoitureurs et connaissant la police utilisée je peux calculer la largeur maximum des 3 lignes,
avec les caractéristiques de la police j'obtiens la hauteur minimale.
A partir de tout cela je peux calculer le ratio idéal ou ratio cible.
En appliquant ce ratio cible a chaque rectangle , je détermine la surface utile de ce rectangle et j'utilise cette surface utile
pour trouver le plus grand rectangle.

[aj3309]

Bonjour,
tbc92 tu as raison mon algorithme des 400 zones est totalement faux , j'en ai honte.
Voici un algorithme que j'espère un peu moins mauvais.
Par construction les 19 points des covoitureurs sont a l'intérieur de la carte,
c'est à dire qu'il n'y a pas de points sur les bords de la carte.
Pour chacun de ces 19 points il y a 4 rectangles vides autour de ce point.
Un au-dessus.
Un en-dessous.
Un à gauche.
Un à droite.
Les coordonnées des coins de ces rectangles sont simples à trouver en partant des coordonnées du point que l'on traite.
On s'appuie a chaque fois sur le précédent ou le suivant dans la liste des coordonnées complétée
par les coordonnée fixes des bords (X = 0 et X = Largeur de la carte , Y = 0 et Y = Hauteur de la carte).
Une fois cette liste établie on la passe dans les filtres d'exclusion cités précédemment.

[Guesset]

Bonjour,

L'approche récursive me semble exhaustive. Un petit dessin (je suis toujours surpris par la taille qu'ils prennent à l'import) pourrait être utile :

Le principe est de partir d'un bord latéral de la surface, puis des différents points du premier au dernier, en progressant vers l'autre bord (donc une fois de la gauche vers la droite et une autre de la droite vers la gauche). A chaque fois que l'on rencontre un point on calcule la surface depuis l'abscisse de départ Xo avec la hauteur du rectangle en cours et l'abscisse du point rencontré (pointillés bleus), on enregistre si plus grand, puis le point rencontré scinde la recherche en 2 sous-recherches et ainsi de suite (selon les n° figurant sur le dessin).
Le dessin montre une recherche à partir du bord gauche. Le tracé en pointillé vert représente le plus grand rectangle trouvé (à vue de nez). En rose les exclusions (ratio ou hauteur minimale). A ce propos, il semble que les derniers échanges fassent plutôt état d'un rectangle minimal (longueur maxi des lignes de texte x hauteur d'une ligne de texte multipliée par le nombre de ligne. Donc en résumé, plutôt dXmin et dYmin qu'un ratio. Cela simplifierait les contrôles.

Correction : le nombre d'itérations est plutôt 2(n+1)² soit 882 pour 20 points

La profondeur de récurrence n'est pas très élevée. Dans un carré elle serait de l'ordre de racine(n) soit entre 4 et 5. Mais avec un rapport L/H = 3/2 la profondeur de récurrence moyenne est de 5.47 donc essentiellement entre 5 et 6. Dans l'exemple, elle est au maximum de 6.

[Flodelarab]

Bonjour

Et on obtient quoi quand on fait ça ? Si on sélectionne le rectangle 11, c'est faux, car on peut étendre le rectangle vers le haut et vers le bas.

[tbc92]

Autre piste.
Reprenons le début donné par AJ3309 hier à 8h36.
Les 19 Points définissent un quadrillage 20x20 : 20 lignes horizontales x 20 colonnes.

On a ce quadrillage 20x20, et les 19 'obstacles' sont à certains sommets de ce quadrillage.
On va faire une boucle sur ces 20 lignes.
Pour chaque ligne, on va tester ce qui se passe si on prend k carreaux de cette lignes, de la colonne C à la colonne C+k-1 (on va donc faire 2 boucles, une sur C et l'autre sur k).
Le rectangle obtenu ainsi (pour une ligne L, pour les colonnes C à C+k-1) est valide (tout rectangle qui ne contient aucun sommet du quadrillage est valide), et on regarde jusqu'où on peut l'étendre en ajoutant des lignes au dessus, puis en dessous.
Pour L,C et k donné, on trouve donc le plus grand rectangle possible qui fait exactement cette largeur (colonnes C à C+k) et qui contient cette portion de la ligne L
Et en bouclant sur tous les cas L,C,k, on trouve la solution optimale.
Et ça ne pose pas trop de problème de qualifier chaque rectangle en disant : ok, sa surface est grande, mais il a une forme inadaptée (très haut mais pas assez large) ou une position inadaptée (trop loin du centre ...) .

[Guesset]

Bonjour Flodelarab,

Et on obtient quoi quand on fait ça ? Si on sélectionne le rectangle 11, c'est faux, car on peut étendre le rectangle vers le haut et vers le bas.

Je n'explique jamais assez précisément

Ce n'est qu'une vue d'une étape de recherche (ici à partir du bord gauche). Dans ce cas, chaque rectangle se prolonge vers le-dit bord gauche : ce nouveau rectangle ne comporte aucun point (j'ai choisi de ne représenter que les rectangles générateurs car c'est un peu confus autrement).

Ensuite on réitère, toujours vers la droite, à partir du premier point, puis du second etc. A chaque fois les carrés générateurs se prolongent vers le point de départ.

Mais ce n'est pas fini, on refait la même chose de droite à gauche.

On a environ 2(n+1)² étapes élémentaires. Si le PO n'avais pas indiqué une direction horizontale privilégiée, il aurait fallu faire la même chose de bas en haut et de haut en bas soit 2 fois plus d'étapes (à vérifier).

Le programme est instantané (à l'échelle humaine ) et il ne fait que 300 lignes dont la plupart sont les déclaration d'environnement.

Le trait ne sert à rien, c'est une animation qui me permet de vérifier que le tri nécessaire des points est correct.

Salut

[Guesset]

Bonjour,

Je me posais la question de l'exhaustivité de l'algorithme proposé et je me suis aperçu qu'un seul balayage suffit.

En effet, prenons un rectangle quelconque déterminé par 4 points d'arrêt sur chacun de ses cotés. Si je place un début de scan sur l'un d'entre eux il sera bloqué sur celui d'en face en ayant été raboté au passage par les points les plus proches se situant de part et d'autre de la trajectoire. Je retrouve bien le rectangle cherché.

L'important est que tout rectangle vide tangent 4 points est révélé à partir de n'importe quel scan : G->D, D->G, H->B ou B->H. En résumé, un seul scan global, c'est à dire partant d'un coté puis de chaque point (soit n+1 scans élémentaires) suffit. Je peux alors supprimer le scan D->G (ou l'autre G->D) et le nombre d'étapes se divise par 2 (cela rejoint le post initial , hormis l'arborescence ).

Il y a exhaustivité mais également unicité On ne retrouve pas 2 fois le même rectangle (je ne parle que des rectangles étendus (les plus grands) jusqu'à la première abscisse du scan, les autres ne sont que des outils de visualisation du process). Supposons que j'ai deux fois le même rectangle, il a le même coté gauche ce qui dans un scan G->D signifie qu'il est sur le même scan élémentaire. Comme les étapes ne se recouvrent pas latéralement, ils ne peuvent être que dans la même séquence de recherche. CQFD. Ce qui signifie qu'il y a (n+1)² rectangles vides tangents en y incluant d'éventuels rectangles plats (dX ou dY = 0) pour les points alignés.

Salutations

[unanonyme]

quid de ce que le plus rectangle n'a pas les bords parallèle aux bords de la fenêtre mais qu'il est penché ?

Par exemple, si la surface à deux nuages de point majoritairement en haut à droite et en bas à gauche.

[Guesset]

Bonjour unanonyme,

quid de ce que le plus grand rectangle n'a pas les bords parallèles aux bords de la fenêtre mais qu'il est penché ?.

Ce n'est pas la question du PO. Peut être faudrait il ouvrir un autre fil ?

La forme pourrait être également un simple parallélépipède (pour un texte en italique ) ?

Beaucoup de problèmes différents peuvent être engendrés à partir de celui-ci.

Salut