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.