chti pb:
 
-jai une image representant la france et il y a un chti points pour chaque village/ville (env 30 000 pt (un truc de ce genre gros en tout cas )  
-bon maint je veux dans une fenetre a cote afficher le nom du village et les infos le concernant des que je passe mon pointeur de souris dessus ou a coté
 
quel est selon vous la solution la plus rapide pour associer une coord de souris a une ville?  
et aussi l'algo de detection de la ville la plus proche.

PS: le chalenge reside a rester rapide sans faire exploser la memoire.

Je fait un truc du genre mais c'est hyper lourd (carte de la france avec des map area générées en php avec un bdd qui contient pour chaque commune les coordonnées des limites de cette dernières (36000 communes, ça représente à peu près 36000*50 points)
Le pauvre pc il suit pas si je trace toute la carte (même un département c'est dur!)
Donc ça m'interesse aussi!

pour le stockage y 'a les collections en java pour les tableau de grande capacité...

au debut je commencais avec des tables de hash ca allais mais la memoire giclais trop de points
apres jais essaye avec du stockage en fichier et de l'indexation
lent et pb kan on bouge rapidement la souris  
 
 
 
ps la je voit en C ou VB (C pour moi VB pour un pote(originaire du pb))

Pour info, elle fait quelle taille ta carte (en pixels) ?

15 000 * 15 000   (non serrieusement c'eszt a moi de decider ca donc peut la fiare grande ou petite mais faut ke les points tiennent dedans ca c'est sur)
 
scrolling rulezzzz

15 000 x 15 000!    
si ta carte est en 256 couleurs, ça fait quand même 255Mo rien que pour l'image, tu m'étonne que ta mémoire ne tienne pas le coup.  
 
je pense que tu devrais diviser ta carte en sous parties à la manière des atlas routiers. En plus, ça façilitera grandement ton problème je pense.

on met ca en monochrome  
et le pb nest pas la l'immage c'est pour que ce soit plus parlant le pb c'est aller chercher la ville ki faut et les infos la concernant en fonction de la position du curseur de souris donc l'image on s'en tappe  
 
et pis pas besoin de 255MO de memoire vive pour afficher une image de 15 000x 15 000 pixel - de 1 mo sufise keke ko en fait
ben oui pour une  
bmp par ex:
 
->ouverture du fichier
->lSeek 54 (pour sauter aux valeurs de pixels)
->tant que lecture pas finit
    ->read de 3 (pour de la couleur 24 bit)
    ->putpixel de ce qui est read
->fermeture du fichier
voila a aucun moment je stocke quoi que ce soit (a par le buffer de lecture)  
 
donc NO COMMENT sur ta reponse.......  
de plus stoker limmage dans sa totalite te servirais a RIEN du TOUT pour ce pb  
 
la theorie c'est bien mais la pratique c'est mieux

-image monochrome et les points des villes ils sont en couleurs ?
 
-et les coordonnées des villes tu les a ou y faut les trouvé ?

ben essaye un B arbre ...
c une espece d'arbre special grosses données.
le truc est que l'arbre est optimisé au niveau de la recherhce
et resisde tt le tps sur le disk
 
demande a Leto II de t'expliquer

en fait y' a une solution a deux ballles c'est d'utiliser un "masque" representant les zones de sensibilité des chaque ville. Comme tu as 30 000 villes environ, il te faut 30 000 couleurs environ.  
 
Ben il te suffit de preparer un masque avec en fait pour chaque ville sa zone coloriée autour d'elle. Avec une couleur different pour chaque ville. Comme le masque n'est jamais affiché tu t'en fou des couleurs. Genre couleur 0 pour la ville 0, couleur 1 pour la ville 1, ... .
 
La difficulté dans ton cas c'es de preparer le masque. MAis une fois que c'est fait, tu recupere les coordonnées de la souris, et tu vas lire la couleur du pixel correspondant et tu as ton numero de ville, alors tu vas dans ta bdd et c'est fait !!!
 
Pour réaliser les zones tu peux le faire à la main (bonne chance) ou tu peux developper un petit programme qui va le faire tout seul : diagramme de delaunay (c'est magique !!!) ca te permet d'obtenir une excellent partitionnement des zones autour de chauqe ville !!! En gros ca consiste à tracer entre chaque ville la droite qui les separent (Si ville A et B, c'est la droite perpendiculaire à (AB) et passant par le milieu de [AB] ).
Mais a mon avis le traitement est monstrueux !!! MAis y'a moyen de l'optimiser à fond !!!

le diagramme delaunay la je suis dacord pour trouver la ville la plus proche par rapport a la souris (si c'est ce que je pense)
 
par contre le coup des masques        
je sait les coord en X,Y de chaque ville c'est pour ca ke rien a foutre de l'image   (cettais pour aider a la comprehension du pb)  
 
le coup du B arbre ... kesako je connais pa !! (enfin peu etre une solution)  
 
LETO II une explication plz pour eclairer le shmilblick

Un Delaunay pour 36000 points, ça doit pas être trop long.
Dans le temps j'avais fait un Delaunay en O(n^2) et il tournait
avec 5000 points (c'était il y a 2 ans en caml non compilé). Mais comme tu peux calculer un diagramme de Delaunay en 2 dimension en O(n ln n) (ce qui est optimal), 36000 points c'est jouable sans trop de problème.

Un B-arbre c'est un arbre à degré très élevé (genre 1000).
Donc un arbre où les noeuds ont des degrés voisins de 1000, il te suffit d'une hauteur de 2 pour avoir 1 million de fils.
Ainsi dans un arbre trié, il te suffit de lire le contenu de 2 noeuds pour accéder à l'élément.
Reste à appliquer ça à ton problème ...

donc c'est bon  
pour selectionner le point le plus proche on utilise dellaunay ...
 
 
 
mais pour savoir quel est la ville associee a ce point on utilise quoi ???  
(le B tree en attente)

daccord pour le b-tree mais reste 2 question
 
- ca vas rentrer en memoire ca? 30 000 nom de ville + description....  
 
- comment tu navigue la dedans? pour trouver rapidement la ville shouaitée

 
ça dépends de la taille de la description, si c'est du genre nom+nb d'habitants+superficie de la commune, ça devrait aller, mais si c'est plus complet, la meilleure solution est de passer par une base de données.

Pour la mémoire y a pas de problème, tu gardes les villes sur disque. C'est l'avantage du B-tree, comme tu ne dois lire que deux noeuds, tu n'as que deux accès disque à faire (ce qui est rapide de nos jours).
Par contre je vois tjrs pas comment agencé Delaunay + B tree pour faire un bon algo...

 
de toute facond tu n'as pas besoin de le faire pour les 36 000 points. Si tu prends lille ca sert a rien de le faire avec MArseille, parce que y'a plusieurs milier de ville plus proches. Donc pour le delaunay, il peut etre optimisé facilement.

 
Moi non plus !!! en fait moi je proposais delaunay juste pour segmenter une fois pour toute ta carte. Apres delaunay tu n'en a plus besoin !!!
 
Tu peux me filer les coordonnees des villes que tuas pour que je puisses faire quelques tests ?

et finalement c'est qu'un tableau de 60 sur 60 pour les coord.

ben ouais mais faut tapper dans la bonne case en fonction d'ou se trouve ton pointeur de souris  
 

tu veux le fichier de coord desole j'en ais pas .. prend des points au hasard
 
 

 
mais je vais pas perdre en vitesse? toute facon des que je sait le nom de la ville affiche c'est plus un pb peux tout faire apres
 

 
c'est vrais ca .. mais reste a savoir kel sont les points a  utiliser pour le delaunay ..
 
ex: je suis au voisinnage de lille  
comment je sait que ca ne sert a rien de prendre en compte marseille ? avec mes yeux facile mais le programme lui comment je lui fait savoir??

Qui te dit que les deux premières villes que tu vas avoir ne sont pas Lille et Marseille ? tu peux pas faire des simplifications de ce genre

Au fait pour être exact, c'est pas une triangulation de Delaunay que l'on veut, c'est un diagramme de Voronoï. Bon, ça revient un peu au même parce que les deux trucs sont duals l'un de l'autre (dans un certain sens ...). Bon, je me tais maintenant ...

L'utilisation d'un gros fichier (style 50Mo) qui ne sera pas chargé en mémoire peut-il te convenir ? Si oui, il y a une solution hyper simple à ton problème.
 
A+

Heu ... un fichier de 10Mo va largement suffire, ça ira ?
 
A+

koulip31 a écrit a écrit : 15 000 * 15 000   (non serrieusement c'eszt a moi de decider ca donc peut la fiare grande ou petite mais faut ke les points tiennent dedans ca c'est sur)   scrolling rulezzzz

 
 
fais des divisions par departement voir region ca bouffera moins de memoire !!

J'espère avoir bien compris le problème.
Bon je me lance quand même.
 
Tes coordonnées vont jusqu'à 15000 pixels, si on considère que la plus grande cordonnée correspond à 1000 km, on a environs une résolution de 67m / pixels.
 
Si on divise tes coordonnées par 6 (ou plus si c'est possible), on tombe à une résolution de 400 m / pixels, ce qui est largement suffisant pour ce que l'on veut faire (vérifier qu'il n'y a pas 2 points plus proches que 400m).
 
On va donc découper ta carte en zones de 6 X 6 pixels soit un tableau de 2500 X 2500 (15000/6). Normalement dans toutes les zones, il ne doit y avoir que 0 ou 1 point.
 
Dans un premier temps, il faut faire un programme, qui prendra le temps qu'il faut, pour initialiser une fois pour toute un tableau de 2500 X 2500 entiers 16 bits non signés dans un fichier binaire (ici nommé ZONES) de 12.5 Mo comme suit :
 
Il suffit de mettre dans les cases du tableau le numéro de la ville (1 à 30000) a qui appartient la zone 6 X 6 correspondante. Il sera possible d'y mettre 0 pour dire que la case n'appartient a personne, ou d'autres valeurs pour désigner que la case est dans une mer ou un pays étranger...
 
Avec le numéro de la ville (lseek num ville X taille enreg), il suffira d'aller dans le fichier (ici nommé VILLES) qui contient les infos des villes (coordonnées exactes pour mettre le point en sur brillance, nom de la ville ...). Si Ce dernier n'a pas des enregistrements de taille fixe (texte par exemple), dans ton fichier 2500 X 2500 tu peux mettre des entiers 32 bits (la taille du fichier doublera simplement) qui correspondent à l'offset des infos de la ville dans ton fichier VILLES.
 
L'utilisation de cela sera très simple, il suffira de diviser les coordonnées du point recherché par 6 (i=x/6 et j=y/6), avec lseek j*2500+i, il faudra récupérer dans le numéro de la ville : int (ou offset : long) dans le fichier ZONES et d'aller chercher les infos dans le fichier VILLES. Cela sera très rapide.
 
Si tu as un système de zoom, il sera ridicule d'afficher les infos d'un petit bled lorsque toute la carte de France est affichée ! Pour cela il suffit de faire plusieurs fichiers ZONES qui seront utilisés selon le zoom courant : par exemple au lieu de diviser par 6, diviser par 100 et initialiser le tableau du fichier ZONES (45 ko) avec les villes de plus de 10000 ha si tu as cette info...
 
Bon voila, bien que les explications soient un peu longues et confuses, ça sera très simple à mettre en oeuvre, rapide à l'exécution et ne demande qu'un minimum de mémoire. Le programme qui sert à initialiser le tableau dans le fichier ZONES n'est pas trop difficile à faire, il y a plusieurs algorithmes possibles... mais cela sera peut-être une autre histoire.
 
A+