Rectangle maximum dans un nuage de points
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.
calcul du barrycentre des points
Il faut calculer l'intersection de tous les points et considérer ce point comme le centre du carré
Rectangle maximum dans un nuage de point Typologie des rectangles
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.
Rectangle maximum dans un nuage de point première piste
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.
Rectangle maximum dans un nuage de point première piste (suite)
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.
Rectangle maximum dans un nuage de point première piste (réponse à tcb92)
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.