Avant de poser ma question, je vais planter le décor :
---------------------------
J'ai un algo qui génère une map (carte geophysique) avec pour chaque point (ou case) de la carte, une information sur sa hauteur (info codée sur un octet signé car j'indique aussi les hauteurs en dessous du niveau de la mer). Un seul octet suffit pour les besoins.
Un des criteres de la carte est d'etre extremement grande (disons au minimum un carré de plus de 10000 cases de coté : ce qui donne ici une taille en mémoire de plus de 100Mo pour l'exemple)
Donc pour éviter d'avoir à stocker tous ces Mo pour rien, je génère un nombre discret de points de référence à partir desquels je vais "interpoler" la carte (en l'occurence j'utilise un algo de ponderation par l'inverse de la distance au carré : voici un lien sur cet algo pour ceux qui désirent avoir plus d'infos : http://fr.wikipedia.org/wiki/Pond%C3%A9ration_inverse_%C3%A0_la_distance)
Pour une map de 10000 cases de coté, le nombre de points est d'environ 35000 (donc plus que 35ko en mémoire et on a TOUTE la carte : pfiouu ça va déjà mieux pour les petites neurones du PC ;-) )
Quand je souhaite n'afficher une partie de la map (et c'est ce qui est le cas lorsque l'on parcourt un monde dans un jeu, on a pas en mémoire la totalité de la carte mais juste une partie), je vais rechercher les points de référence concernés et lancer l'interpolation.
---------------------------
Mon souci est dans la recherche des points de référence : en fait je ne sais pas comment les organiser dans la mémoire et comment les parcourir pour minimiser les temps de traitements.
Ma premiere implémentation a été de parcourir tout le tableau, calculer les distances au carré par rapport à la case à interpoler puis de prendre les N plus proches pour alimenter l'algo : bien sur c'est horriblement ridicule comme solution surtout quand le nombre de points de ref est grand.
2° etape, je parcours toujours TOUT le tableau des points de référence, mais cette fois je ne calcule plus la distance que si ce point est "relativement proche" de la case à interpoler. On limite qq calculs : c pas mal mais ça ne me satisfait pas encore du fait que l'on parcourt tout le tableau.
---------------------------
Etape suivante à laquelle j'ai pensé, etait d'organiser ma liste de points de référence en Quad-Tree pour les parcourir plus vite mais je ne sais pas trop si c'est une bonne solution ou non.
---------------------------
Bref ma question est simple :
pour mon exemple ici, quelle est selon vous la meilleure méthode d'organisation en mémoire et de parcourt pour minimiser les temps de traitements ??
Merci par avance
)