Brevet FR2822275A1 — publié le 20020920

Procédé pour rechercher un objet au sein d'un espace, procédé et système de cartographie vectorielle intégrant ce procédé de recherche, appareil électronique mettant en oeuvre ce procédé de cartographie vectorielle, et support de données de cartographie vectorielle obtenues avec un tel procédé La présente invention concerne un procédé pour rechercher un objet au sein d'un espace, ainsi qu'un système de recherche mettant en oeuvre ce procédé. Elle vise également un procédé et un système de cartographie vectorielle intégrant ce procédé de recherche, ainsi que des appareils électroniques mettant en oeuvre ce procédé de cartographie vectorielle et des supports de données de cartographie vectorielles obtenues avec un tel procédé En cartographie vectorielle, les objets présents dans un domaine sont décrits dans une matrice qui peut être de grande taille et dont le traitement peut être particulièrement consommateur de temps. De plus, lorsqu'il s'agit de rechercher des objets inscrits dans un sous-domaine du domaine principal, on est conduit à construire une extraction de la matrice principale. Plus généralement, le problème posé est la détermination d'un sousensemble d'objets contenus dans un sous-domaine d'un domaine contenant un ensemble d'objets sémantiquement homogènes et de géométrie variable, et la construction d'une matrice décrivant les objets appartenant à ce sousensemble. Soit un ensemble Q de N objets sémantiquement homogènes et de géométrie (forme et taille) variable. Ils sont distribués aléatoirement dans l'espace OXYZ où ils occupent un domaine A inscrit dans un parallélépipède compris entre (Xmin, Ymin, Zmin) et (Xmax, Ymax, Zmax), parallélépipède constituant les limites de l'encombrement A du domaine. En bidimensionnel, on pourrait désigner le domaine par le vocable territoire , inscrit dans un rectangle compris entre (Xmin, Ymin) et (Xmax, Ymax) Les N objets sont décrits par une matrice M qui pour chacun donne la forme par une liste de points (avec coordonnées) et des descriptifs topologiques (arêtes, faces, etc. ). En même temps, les coordonnées donnent la position de l'objet dans l'espace. Chaque objet a donc son propre encombrement élémentaire X représenté par un parallélépipède circonscrit. On peut naturellement faire les observations suivantes : - les encombrements élémentaires peuvent s'intersecter, - (Xmln, Ym, n, Zmin) et (Xmax, Ymax, Zmax) sont respectivement le minimum et le maximum d'au moins un parallélépipède élémentaire. Ceci est vrai s'il n'existe pas de définition géométriquement explicite du domaine A. Il est demandé de déterminer le sous-ensemble w des v objets contenus dans un sous-domaine 5 inscrit dans un parallélépipède compris entre (min, Ym. imin) et (Xmax, Ymax, zmax) à l'intérieur du parallélépipède circonscrivant A, et de construire la matrice p les décrivant, matrice qui se présentera comme une extraction de M. Selon le problème posé, par objet contenu dans 8 on peut entendre objet inclus complètement ou partiellement (objet touché par ou intersectant 8). On va maintenant décrire des méthodes d'accélération existantes : Si l'ordre de la description des objets d'a dans la matrice M est aléatoire, pour construire p il faut parcourir tous les N objets afin de vérifier pour chacun son appartenance à 8 et si oui, incrémenter chaque fois v. Pour accélérer la construction de l'extraction u, il est nécessaire de transformer M. Une première méthode d'accélération existante est le tri préalable. Trier préalablement les objets de M permet d'accélérer les recherches. La méthode la plus répandue est d'ordonner les objets par rapport au point (xmln, Ymln, Zmin) de leur parallélépipède élémentaire d'encombrement À. Ceci permet de diminuer le nombre de vérifications complètes d'appartenance, en éliminant d'emblée tous les objets dont ce point est supérieur au (Xmax, Ymax, Zmax) de 8 ; on peut appliquer une deuxième fois le procédé pour l'autre extrémité. L'appartenance est ensuite vérifiée sur les objets restants. Il existe plusieurs variantes de cette approche. On remarquera que même si l'on diminue la complexité de certaines vérifications (plus # est petit par rapport à A, plus la diminution est significative), tous les N objets de M doivent être parcourus. Afin de l'éviter, il faudrait utiliser une recherche dichotomique. Un deuxième type de méthodes d'accélération de la construction de l'extraction zu consiste en la décomposition du domaine A en E sousdomaines A ; appe) és tuites ou dalles, d'où le nom de tuilage (tiling en anglais). Les objets chevauchant une ou plusieurs tuiles (sous-domaines) seront coupés aux frontières et des informations supplémentaires (de connexion, pour assurer la continuité sémantique) seront enregistrées. La matrice M initiale sera donc décomposée en # matrices M ayant chacune N, objets. Evidemment, Z N i N Le domaine 8 recherché couvrira cr tuiles #1. L'efficacité de la méthode dépendra du nombre # de tuiles du domaine A initial et du rapport de taille entre 8 et les A,, donc entre cr et I. Par contre et malheureusement, plus on augmente #, plus on augmente le nombre d'objets coupés et donc la taille de M. A la fin, les objets éventuellement coupés pourront être reconstitués, rendant ainsi le tuilage transparent. Le tuilage apparaît immédiatement plus intéressant que le tri simple, d'autant plus que ce dernier peut être appliqué à chaque tuile. C'est la raison pour laquelle il est amplement utilisé, par exemple en cartographie. Il comporte cependant un inconvénient majeur qui réside dans la nécessité de couper des objets, donc d'augmenter le nombre total d'objets traités, et par conséquent de créer et d'utiliser des informations de frontière, tout ceci compliquant les algorithmes de traitement. L'objectif visé, par rapport à l'état de la technique, est d'accélérer le processus d'obtention de l'extraction sans modifier en aucune façon les objets, afin de ne pas en augmenter le nombre et par conséquent la taille de la matrice M contenant pour chaque objet une liste de points et des descriptifs topologiques. Pour atteindre cet objectif, on prend en considération l'information d'encombrement élémentaire de chaque objet, qui, soit est contenue initialement dans la matrice M, soit doit être calculée puis enregistrée dans la matrice, et on passe l'ensemble des objets au travers d'une pluralité de tamis aux mailles de plus en plus fines, de façon à obtenir des groupes d'objets calibrés. On propose ainsi un procédé pour rechercher un objet contenu dans un domaine 5 au sein d'un espace A contenant un ensemble d'objets décrits dans une matrice M initiale, comprenant une construction d'un sousensemble w d'objets contenus dans ledit domaine 5 par extraction d'une matrice fi à partir de la matrice M initiale. Suivant l'invention, le procédé comprend les étapes suivantes : - on crée un matriçage M de l'espace A en superposant une pluralité de matrices géométriques de normes p (tailles des mailles) différentes, représentant une couverture du domaine par un ensemble déterminé et homogène de sous-domaines similaires, chacune des mailles de chaque matrice géométrique étant identifiée par une valeur numérique spécifique et unique appelée code de matrice, - on détermine pour l'ensemble du matriçage M toutes les mailles incluses dans le domaine 5 ou intersectées par le domaine , et le nombre d'objets concernés comme la somme des nombres d'objets des mailles concernées, - on trie la matrice M par codes de matrice selon un ordre prédéterminé, par exemple décroissant, des normes p, et - on construit la matrice d'extraction fi décrivant les seuls objets concernés par lesdites mailles incluses dans le domaine 8 ou intersectées par le domaine 8. Il est à noter que le document US5030117 décrit un système numérique de génération cartographique, dans lequel les données cartographiques sont organisées selon une hiérarchie d'échelles successives, sous une forme pyramidale avec un faible nombre de tuiles (par exemple 4) au sommet et 416 tuiles à la base d'une pyramide comprenant par exemple 16 niveaux. Même si des figures de ce document, notamment les figures 8 et 13, montrent des superpositions de grilles ou de matrices, il ne s'agit pas pour autant d'un procédé de recherche d'objet selon une technique de tamis multiples . On connaît aussi par le document US5694534 un dispositif pour stocker une représentation de structures topologiques et des procédés pour construire et rechercher cette représentation. Le dispositif décrit comprend un support de stockage de données, une base de données stockée sur ce support et contenant des blocs porteurs de données représentant des caractéristiques topologiques de la structure représentée à un niveau donné de détail. Les données de chacun de ces blocs sont une représentation d'un porteur qui est un ensemble fermé incluant un objet topologique donné. Dans le procédé décrit, il s'agit de construire des chaînes connectées de cellules constituant des sous-complexes topologiques. Le concept de tamisage multiple à des fins de construction d'une matrice d'extraction n'est pas divulgué dans ce document. Dans le procédé de recherche selon l'invention, les objets peuvent par exemple être triés par codes de matrice croissants. Dans un mode de réalisation avantageux de l'invention, le procédé de recherche comprend en outre un stockage d'une liste des codes de matrice avec un pointeur sur le premier objet de chaque code. La sélection des objets peut par exemple être effectuée par un curseur qui parcourt la liste des codes de matrices. Suivant un autre aspect de l'invention, il est proposé un procédé de cartographie vectorielle, pour cartographier un territoire A comprenant un ensemble d'objets décrits par une matrice M ; mettant en oeuvre le procédé de recherche d'objet selon l'invention, caractérisé en ce qu'il comprend les étapes suivantes : - une détermination de la liste des mailles actives, comprenant un calcul de l'ensemble des codes de matrice correspondant aux mailles qui intersectent le domaine 5 de recherche, et - une sélection et un traitement éventuel des objets. Lorsque ce procédé est mis en oeuvre dans un domaine bidimensionnel, il comprend alors un matriçage selon une pluralité de matrices géométriques rectangulaires comportant des mailles régulières, chaque matrice géométrique présentant une norme différente incluant la longueur et la largeur des mailles de ladite matrice. Pour une mise en oeuvre en cartographie bi-dimensionnelle étendue à niveaux multiples, le procédé de cartographie vectorielle selon l'invention comprend alors les séquences suivantes : -l'ensemble initial n de N objets est décomposé en une pluralité de Z sous-ensembles Q d'objets de même niveau, avec (= 1 à Z, - la matrice M initiale est décomposée en Z matrices M, - on utilise le matriçage d'une façon indépendante pour chaque sous- ensemble. Suivant encore un autre aspect de l'invention, il est proposé un système de cartographie vectorielle, comprenant des moyens pour traiter des objets contenus dans un domaine 8 au sein d'un espace A contenant un ensemble d'objets décrits dans une matrice M initiale, comprenant une construction d'un sous-ensemble w d'objets contenus dans ledit domaine 8 par extraction d'une matrice J1 à partir de la matrice M initiale, caractérisé en ce qu'il comprend en outre : - des moyens pour créer un matriçage M de l'espace A en superposant une pluralité de matrices géométriques de normes p différentes, représentant une couverture du domaine par un ensemble déterminé et homogène de sousdomaines similaires, chacune des mailles de chaque matrice géométrique étant identifiée par un index spécifique et unique appelé code de matrice, - des moyens pour déterminer pour l'ensemble du matriçage M toutes les mailles incluses dans le domaine 8 ou intersectées par le domaine 5, et le nombre d'objets concernés comme la somme des nombres d'objets des mailles concernées, - des moyens pour trier la matrice M par codes de matrice selon un ordre prédéterminé, par exemple décroissant, des normes p, et - des moyens pour construire la matrice d'extraction /décrivant les seuls objets concernés par lesdites mailles incluses dans le domaine 0 ou intersectées par le domaine 8. D'autres avantages et caractéristiques de l'invention apparaîtront à l'examen de la description détaillée d'un mode de mise en oeuvre nullement limitatif, et des dessins annexés sur lesquels : - la figure 1 représente graphiquement le tamisage progressif effectué dans le procédé de recherche selon l'invention ; et - la figure 2 est un schéma illustrant le tri de la matrice des objets de l'ensemble d'objets par codes de matrice La méthode proposée dans le cadre du procédé de recherche d'objets selon l'invention vise à accélérer le processus d'obtention de l'extraction u sans modifier en aucune façon les objets, afin de ne pas en augmenter le nombre et par conséquent la taille de la matrice M. Pour cela elle prend en considération l'encombrement élémentaire À de chaque objet, information contenue dans la matrice M, et l'utilise pour organiser un tamisage progressif, à travers des tamis aux mailles)'de plus en plus fines. Comme en granulométrie, on obtient des groupes d'objets calibrés. Ainsi, en référence à la figure 1, si l'on considère un domaine A contenant des objets 1,2, 3,... i, j... N, sur lequel est appliqué un ensemble de grilles de normes p1, p2, p3,... pn, la grille de norme p1 va retenir l'objet 2, la grille suivante de norme p2 les objets j et N, tandis que la grille de norme p3 ne retient aucun des objets considérés, la grille ultime de norme pn recueillant finalement l'objet i et l'objet ponctuel 3. Si l'encombrement A de chaque objet n'existe pas déjà dans la matrice M, il doit être calculé. Cet encombrement peut d'ailleurs être enregistré dans la matrice M, et dans ce cas, la taille de M augmentera de cette information, mais pas le nombre d'objets. Pour un calibre donné, le tamis est une matrice géométrique représentant la couverture du domaine A par un ensemble déterminé et homogène de sous-domaines similaires, pas nécessairement égaux mais proches d'un encombrement normé p. Le recouvrement du domaine n'est pas obligatoirement strict dans le sens où si le domaine est effectivement complètement couvert, il peut y avoir par contre des intersections entre des sous-domaines (entre des mailles ). La matrice géométrique représentant le sous-ensemble décrit est appelée grille de norme p. Chacune des. p mailles de la grille est identifiée par une valeur numérique spécifique et unique appelée code de matrice de norme p, np. En superposant n grilles de normes p différentes on crée le matriçage M de profondeur n du domaine A. Il comprendra au total Y mailles : Y=. pl +. p2 +... +. Pn (3. 1) chacune identifiée par son code de matrice ##IJ, avec i = 1, # (la profondeur, de 1 àn) et j = 1,. p, (le nombre de la maille dans la grille de profondeur i, de 1 à .#l). La première grille est constituée en général d'une seule maille couvrant le domaine complet et recueille tous les objets qui, indépendamment de leur encombrement X, ne tombent jamais dans une maille plus fine, mais toujours à cheval à travers tout le tamis ; alors, évidemment, . pi = 1. Dans le cadre d'un matriçage M donné, il est possible-et relativement facile-de déterminer pour chaque objet de l'ensemble n la maille de norme p la plus petite qui le contient complètement (la norme sera toujours supérieure ou égale à l'encombrement : p X) et lui attribuer donc un code de matrice npj. On trie ensuite la matrice M des N objets de l'ensemble Q par codes de matrice, par exemple dans l'ordre décroissant des normes p. On obtient ainsi une description ordonnée des N objets dans la matrice M triée, allant des plus encombrants vers les plus petits . Pour une maille donnée, identifiée par son code de matrice, on aura n objets ; évidemment, l n = N et certains n peuvent être nuls. Le tri peut être illustré par le schéma de la figure 2. Pour la construction du sous-ensemble w des u objets contenus dans le domaine 8, et donc de l'extraction Il de la matrice M, on procède en deux étapes : A. On détermine pour l'ensemble du matriçage M (de profondeur n) toutes les mailles de toutes les grilles incluses dans et intersectées par 8. Pour chaque grille (de norme p,) on aura. pi mailles,. pi ~. ph de (3. 1) ; le nombre total de mailles concernées sera =-pl +. p2 +... +. pn (3. 2) et donc # # #. Le nombre d'objets concernés, N, est la somme des nombres d'objets des mailles concernées et donc aussi N N. Les inégalités sont d'autant plus fortes que 8 est petit par rapport à A. B. La matrice étant ordonnée comme dans le schéma ci-dessus (ou tout autre système d'indexation permettant d'accéder directement aux objets d'une maille, donc d'un code de matrice donné), on vérifie directement et seulement les objets concernés par les lIJ mailles retenues. Le problème posé initialement, à savoir déterminer le sousensemble w des v objets contenus dans le domaine 8 et construire la matrice u les décrivant, ne demande plus que l'examen des N objets (et non des N initiaux). Comme pour le tuilage, le tri peut être appliqué dans chaque maille. Le premier avantage majeur du matriçage par rapport au tuilage est qu'aucun des objets d'a n'est modifié, la taille de la matrice M de description restant donc inchangée. L'efficacité du matriçage dépend bien sûr de la finesse du maillage, donc de la profondeur n, tout comme l'efficacité du tuilage dépend de #, mais il n'y a plus d'obstacle à augmenter la profondeur. La seule condition évidente à respecter est Pn-= Pmin > 2min (3.3) Le choix de la profondeur optimale est fonction de la distribution des encombrements X des objets d'Q et de l'encombrement A de ce dernier, donc du domaine d'application du problème posé : - en astrophysique A est beaucoup plus grand que max et donc dès la deuxième grille on peut avoir une maille très fine ; n sera petit, voire limité à 2 ; - en cartographie, Xmax A et Xmax Xmin ; tout en respectant (3. 3), ri peut être important et sera choisi en fonction de la distribution des), toute autre contrainte égale par ailleurs. Dans le cas particulier des objets ponctuels, les objets d'encombrement nul (À = 0) sont des objets réduits à un point par rapport au domaine A. Ils sont en nombre variable selon le domaine d'application : très nombreux en astrophysique, moins nombreux en cartographie. Evidemment, la totalité de ces objets ponctuels se situera dans les mailles de la matrice la plus fine, la grille de profondeur #. I Il est à noter que si # contenait exclusivement de tels objets ponctuels, tuilage et matriçage seraient d'efficacité équivalente. On remarquera que le tri simple associé à une recherche dichotomique serait aussi très efficace. On donne maintenant un exemple d'implémentation du procédé de cartographie vectorielle bidimensionnelle. Les territoires (les domaines A), pour un ensemble donné Q de N objets, décrits par une matrice M, couvrent en moyenne l'étendue d'une région, voire d'un petit pays. L'encombrement A du domaine est la diagonale du rectangle [ (Xmin, Ymin), (Xmax, Ymax)] le circonscrivant. Les côtés du rectangle sont respectivement AX = Xmax-Xmin etAY = Ymax-Ymin. Chaque objet est circonscrit par un rectangle élémentaire [ (Xmin, ym) n), (Xmax, Yrnax)], dont la diagonale constitue l'encombrement À de l'objet. Le matriçage M est constitué par des grilles rectangulaires de mailles régulières assurant un recouvrement strict. La norme p, de la grille de profondeur i est donnée par la longueur (en X) et la largeur (en Y) des mailles : Pix x = #X / #ix et #ly = #Y / #iy (4. 1) Pour la grille de profondeur i, on aura donc. pi =) ix * y mailles rectangulaires. Une suite de n valeurs pour #IX et pour) y donne le matriçage M de profondeur n du domaine A. Dans l'exemple d'implémentation présenté, on a imposé, pour des raisons de concision, que tous les codes de matrice np. j soient codés sur un seul octet. Pour la simplicité, on a choisi un nombre de mailles égal selon les deux directions) =) ix =) iy avec la suite de valeurs ) = {1, 2,3, 7, 13} (4.2) de profondeur n = 5 et qui pour la grille de la première profondeur comporte une seule maille égale au territoire. L'utilisation d'une suite de nombres premiers entre eux garantit que les frontières de deux mailles de profondeurs différentes ne se superposent jamais. Ainsi, un objet dont l'encombrement est inférieur à celui d'une maille de profondeur i mais dont la géométrie ne permet pas de lui attribuer une maille à cette profondeur (parce qu'il se trouve à cheval sur au moins deux mailles de cette profondeur), a toutes les chances de se voir attribuer une maille à la profondeur immédiatement inférieure (i-1). Quel que soit le domaine d'extraction, le nombre de mailles non-actives (i. e. n'intersectant pas le domaine) croît avec la profondeur (cette croissance n'est bien entendu pas nécessairement stricte). II en résulte qu'un système de maillage est d'autant plus efficace que la proportion d'objets placés dans des mailles des plus grandes profondeurs est importante. Le nombre total de mailles Y est '1'= 12 + 22 + 32 + 72 + 13 = 232 (4. 3) avec des codes de matrice indexables sur un octet, de 0 à 231. La correspondance maille/index se fait de la façon suivante : profondeur 5 : grille 13 x 13 : 0 à 168 profondeur 4 : grille 7 x 7 : 169 à 217 profondeur 3 : grille 3 x 3 : 218 à 226 profondeur 2 : grille 2 x 2 : 227 à 230 profondeur 1 : grille 1 x 1 : 231 A l'intérieur d'une même grille, les mailles sont triées par x croissant puis par y croissant, comme l'illustre le tableau 1 suivant. L'extraction proprement dite se décompose en deux étapes : - une détermination de la liste des mailles actives. - une sélection et le traitement éventuel des objets. La détermination des mailles actives consiste simplement à calculer l'ensemble des codes de matrice correspondant aux mailles qui intersectent le domaine 5 de recherche (en l'occurrence un rectangle). Dans le fichier, les objets sont triés par codes de matrice croissants. Une liste des codes de matrice avec un pointeur sur le premier objet de chaque code est également stockée dans le fichier. La sélection des objets est effectuée par un curseur qui parcourt la liste des codes de matrices. Profondeur 5 : 13 x 13 12 25 38 51 64 77 90 103 116 129 142 155 168 11 24 37 50 63 76 89 102 115 128 141 154 167 10 23 36 49 62 75 88 101 114 127 140 153 166 9 22 35 48 61 74 87 100 113 126 139 152 165 8 21 34 47 60 73 86 99 112 125 138 151 164 7 20 33 46 59 72 85 98 111 124 137 150 163 6 19 32 45 58 71 84 97 110 123 136 149 162 5 18 31 44 57 70 83 96 109 122 135 148 161 4 160 3 159 2 158 1 131 144 157 0 13 26 39 52 65 78 91 104 117 130 143 156 Profondeur 4 : 7 x 7 175 182 189 196 203 210 217 174 181 188 195 202 209 216 173 180 187 194 201 208 215 172 179 186 193 200 207 214 171 178 185 192 199 206 213 170 177 184 191 198 205 212 169 176 183 190 197 204 211 Profondeur 3 : 3 x 3 220223226 219222225 218221224 Profondeur 2 : 2 x 2 228230 227229 Profondeur 1 : 1 x 1 231 TABLEAU 1 Lorsque le curseur rencontre un code actif, celui-ci parcourt alors l'ensemble des objets de ce code. Seuls les objets vus par le curseur sont traités". Le traitement lui-même peut à son tour effectuer un tri car les objets sélectionnés par le curseur n'intersectent pas nécessairement le domaine 8 (le fait que la maille à laquelle est associé un objet intersecte le domaine 5 est une condition nécessaire mais non suffisante). Ce second tri est, par nature, plus lourd car il nécessite une lecture de chaque objet, puis un calcul d'intersection avec le domaine 8. On comprend alors l'intérêt du tri préalable effectué par le curseur grâce au système de matriçage. On va maintenant décrire un exemple d'application du procédé de cartographie vectorielle en pseudo-tridimensionnel ou bidimensionnel étendu (dit à niveaux ). Dans certains domaines d'application, comme la cartographie routière (à destination des applications d'orientation et navigation routières), il n'est pas nécessaire d'opérer sur un ensemble d'objets en 3D (avec le Z pour tous les points), dont la matrice M est forcément plus volumineuse que celle de l'ensemble des mêmes objets représentés en plan (en 2D). En effet, pour résoudre par exemple le problème d'une correcte représentation graphique 2D, il suffît de connaître la position verticale relative des objets : il suffit en somme de savoir qui passe par dessus qui (le problème dessus/dessous ). On introduit alors la notion de niveau : un niveau est constitué par l'ensemble des objets se situant à une même position verticale relative. Le procédé de cartographie vectorielle, lorsqu'il est mis en oeuvre dans une application pseudo-tridimensionnelle ou bidimensionnelle étendue, comprend alors les séquences suivantes : - L'ensemble initial Q de N objets est décomposé en Z (nombre total de niveaux identifiés) sous-ensembles Q d'objets de même niveau, avec # = 1 à Z - La matrice M initiale est décomposée en Z matrices M. - On utilise le matriçage précédemment décrit d'une façon indépendante pour chaque sous-ensemble. Autrement dit, l'ensemble initial est d'abord trié par niveaux et ensuite par encombrements, avec les grilles correspondantes ; ceci permet d'ailleurs l'utilisation de matriçages différents par niveaux. L'utilisation du matriçage dans le procédé de recherche d'objets appartenant à un sous-ensemble se fait en deux phases distinctes : - une première phase comprenant : - une définition du matriçage M même, c'est-à-dire le choix des grilles, - un tri des objets de l'ensemble par ordre croissant ou décroissant de leur code de matrice npj, avec i = 1, n (la profondeur, de 1 à n) et j = 1,. p, () e nombre de la maille dans la grille de profondeur i, de 1 à. p,). - une seconde phase comprenant : - une étape A de recherche des mailles actives , en l'occurrence, des codes de matrice actifs), c'est à dire qui sont concernées par o, - pour chaque code de matrice np,, actif, une étape B de recherche des objets correspondants et de vérification, pour eux seulement, de l'appartenance à ô. Est donné ci-après un exemple d'implémentation de codes de matrices en langage C++ pour la seconde phase du procédé. Afin de comprendre les extraits de codes qui suivent, on donne ci-dessous la définition de quatre types et structures utilisés : //Types typedef TGFJNT32 long ; typedef TGF~UINT32 unsigned long ; II Structures typedef struct { TGFJNT32 x ; TGFJNT32 y ; } TGFLONGPOINT ; typedef struct { TGFLONGPOINT min ; TGF~LONGPOINT max ; } TGFLONGRECT ; La classe CGFMatrixHandler contient toutes les méthodes utiles aux calculs liés aux codes de matrices. La méthode qui suit permet de déterminer la liste des codes de matrice actifs (étape A) par rapport à un domaine (ici un rectangle). Le tableau de booléens mMatrixCodesList, donnée membre de la classe, est dimensionné par le nombre total de codes de matrice. //Given inRect, compute list of"active" matrix codes bool * CGFMatrixHandler : : GetMatrixCodesList (TGFLONGRECT inRect) { Il Get global territory (domain) TGF ~LONGRECT territory = GetTerritory () ; //ResefmMar/xCocfesL/sf. GefMbMafr/xCodes refums fofa/num & eroma/x codes memset (mMatrixCodesList, false, GetNbMatrixCodes () *sizeof (boo))) ; // Now set"active"codes to"true" TGFLONGRECT currentMatrixSquare ; TGF~UINT32 w, h, col, line, res, currentcode = 0 ; I/GetCount () retums matrix's"deepness" (number of levels) for (TGF-UINT32 i=O ; i currentMatrixSquare. max. y = currentMatrixSquare. min. y + h ; for (Iine=O ; line I/50, currentCode is"active" if (RectintersectsRect (currentMatrixSquare, inRect)) mMatrixCodesList [currentCode] = true ; currentCode++ ; currentMatrixSquare. min. y += h ; currentMatrixSquare. max. y += h ; } currentMatrixSquare. min. x += w ; currentMatrixSquare. max. x += w ; } } return mMatrixCodesList ; } La classe CGFCursor permet d'accéder aux objets concernés (première partie de l'étape B), en utilisant un filtre sur les codes de matrices. La méthode Next() permet d'accéder à l'objet suivant dans le fichier compte tenu de ce filtre. CGFCursor : : CGFCursor (bool * inMatrixValues) mMatrixCodes (inMatrixValues) { mCurMatrixCode = GetMatrixHand ! er ()- > GetNbMatrixCodes ()-1 ; mCurMatrixCodelndex = (TGF-UINT32)-1 ; mCurMatrixCodeObjectsCount = (TGFJUINT32)-1 ; mCurObjectinMatrixCode = (TGFUINT32)-1 ; mCurObjectOffset = (TGFU UINT32)-1 ; mCurObjectSize = 0 ; mlnitialized = taise ; } Il Return offset of next object in file or (TGF UINT32)-1 if none TGF-UINT32 CGFCursor : : Next () { for ( ; ;) { Il Move on to the next object for ( ; ;) { I/Calculate the offset of this object. If current object's I/offset is-1, then we are at the beginning of a matrix code Il and we don't need to increment the previous offset to get to Il the current one. if (mCurObjectOffset ! = (TGF-UINT32)-1) Il Next object in current matrix code if (++mCurObjectinMatrixCode > = mCurMatrixCodeObjectsCount) break ; I/Compute the next object's position mCurObjectOffset += mCurObjectSize ; } else { mCurObjectinMatrixCode = 0 ; mCurObjectOffset = GetFirstObject ! nNthMatrixCode (mCurMatrixCodelndex) ; } return mCurObjectOffset ; } Il Move on to the next matrix code NextMatr ! xCode () ; } } bool CGFCursor : : NextMatrixCode () { Il Reset the current object offset so that the Next () method H knows that it should start at the beginning of the matrix code. mCurObjectOffset = (TGFUUINT32)-1 ; mCurObjectSize = 0 ; mCurObjectinMatrixCode = (TGF-UINT32)-1 ; mCurMatrixCodeObjectsCount = (TGF~UINT32)-1 ; Il Handle the case where we are filtering on a matrix codes'list if (mMatrixCodes) { for ( ; ;) { Il Get the next code if (++mCurMatrixCodelndex > = GetMatrixCodesCount ()) { mCurMatrixCodelndex = (TGFUINT32)-1 ; mCurMatrixCode = GetMatrixHandter ()- > GetNbMatrixCodes ()-1 ; return false ; } TGF ~UINT32 code = GetNthMatrixCode (mCurMatrixCodelndex) ; Il If this code is activated in the array, update variables if (mMatrixCodes [code]) { mCurMatrixCode = code ; mCurMatrixCodeObjectsCount = GetObjectCountlnNthMatrixCode(mCurMatrixCodelndex) ; return true ; } } } Not filtering on matrix codes : get the next code if (++mCurMatrixCodelndex > = GetMatrixCodesCount ()) { I/Does not exist mCurMatrixCodelndex = (TGF~UINT32)-1 ; mCurMatrixCode = GetMatr ! xHand) er ()- > GetNbMatrixCodes ()-1 ; return taise ; } mCurMatrixCode = GetNthMatrixCode (mCurMatrixCodelndex) ; mCurMatrixCodeObjectsCount = GetObjectCountl nNth MatrixCode (mCu rMatrixCodel ndex) ; return true ; } L'accès aux objets intersectant un rectangle rect (deuxième partie de l'étape B), s'effectue alors de la façon suivante : { TGFLONGRECT rect, domain ; TGF~UINT32* matrixLevelList ; // Set rect and get file's domain and matrixLeveiList CGFMatrixHandler * mtxHdl = new (CGFMatrixHandler (domain, matrixLevelList)) ; CGFCursor * iter = new (CGFCursor (mtxHdl- > GetMatrixCodesList (rect))) ; while (iter- > Next () (TGF-UINT32)-1) { I/Read current object at offset iter- > GetCurObjectOffse Il Check if abject intersects rect (its matrix code does but not Il necesseraly the abject itself). // If so, process object } } Une mise en oeuvre pratique du procédé de recherche selon l'invention peut être de réaliser la première phase une fois pour toutes pour un domaine donné, avant de le charger dans un appareil ou équipement de lecture, surtout si l'on envisage une exploitation suivie du domaine. La seconde phase est toujours exécutable chaque fois qu'une recherche est demandée et peut donc être de préférence installée de façon permanente dans le terminal d'exploitation. Les extractions p ainsi obtenues par mise en oeuvre du procédé de cartographie vectorielle selon l'invention peuvent être stockées dans tout type de supports d'information et intégrées dans des appareils électroniques, tels que des équipements de communication et/ou de navigation. Bien sûr, l'invention n'est pas limitée aux exemples qui viennent d'être décrits et de nombreux aménagements peuvent être apportés à ces exemples sans sortir du cadre de l'invention. REVENDICATIONS 1. Procédé pour rechercher un objet contenu dans un domaine au sein d'un espace à contenant un ensemble d'objets décrits dans une matrice M initiale, comprenant une construction d'un sous-ensemble w d'objets contenus dans ledit domaine ô par extraction d'une matrice p à partir de la matrice M initiale, caractérisé en ce qu'il comprend les étapes suivantes : - on crée un matriçage M de l'espace A en superposant une pluralité de matrices géométriques de normes p différentes, représentant une couverture du domaine par un ensemble déterminé et homogène de sous-domaines similaires, chacune des mailles de chaque matrice géométrique étant identifiée par un index spécifique et unique appelée code de matrice, - on détermine pour l'ensemble du matriçage M toutes les mailles incluses dans le domaine 8 ou intersectées par le domaine 5, et le nombre d'objets concernés comme la somme des nombres d'objets des mailles concernées, - on trie la matrice M par codes de matrice selon un ordre prédéterminé, croissant ou décroissant, des normes p, et - on construit la matrice d'extraction u décrivant les seuls objets concernés par lesdites mailles incluses dans le domaine 8 ou intersectées par le domaine 8. 2. Procédé de recherche d'objet selon la revendication 1, caractérisé en ce que les objets sont triés par codes de matrice croissants ou décroissants. 3. Procédé de recherche d'objet selon l'une des revendications 1 ou 2, caractérisé en ce qu'il comprend en outre un stockage d'une liste des codes de matrice avec un pointeur sur le premier objet de chaque code. 4. Procédé de recherche d'objet selon l'une des revendications précédentes, caractérisé en ce que la sélection des objets est effectuée par un curseur qui parcourt la liste des codes de matrices. 5. Procédé de recherche d'objet selon la revendication 4, caractérisé en ce que, lorsque le curseur rencontre un code actif, ledit curseur parcourt alors l'ensemble des objets de ce code, seuls les objets balayés par ledit curseur étant traités. 6. Procédé de recherche d'objet selon la revendication 5, caractérisé en ce que le traitement des objets sélectionnés comprend un second tri pour exclure dudit traitement ceux des objets sélectionnés par ledit curseur qui n'intersectent pas nécessairement le domaine o. 7. Procédé de recherche d'objet selon la revendication 6, caractérisé en ce que le tri comprend une lecture de chaque objet, puis un calcul d'intersection avec le domaine 5. 8. Procédé de recherche d'objet selon l'une quelconque des revendications précédentes, caractérisé en ce qu'il comprend : - une première phase (1) comportant : - une définition d'un matriçage M, un tri des objets de l'ensemble d'objets par ordre croissant ou décroissant de leur code de matrice bp,,, avec i = 1, n (profondeur) et j = 1,'po (nombre de la maille dans la grille de profondeur i). - une définition du matriçage M comprenant un choix des grilles ; -- un tri des objets de l'ensemble par ordre croissant ou décroissant de leur code de matrice np, j, avec i = 1, II (profondeur) et j = 1, ph (nombre de la maille dans la grille de profondeur i), et - une seconde phase (2) de recherche des v objets contenus dans le domaine de recherche a formant le sous-ensemble w, comprenant : - une recherche des mailles actives (des codes de matrice actifs), qui sont concernées par le domaine de recherche o. - pour chaque code de matrice mop, actif, une recherche des objets correspondants et une vérification, pour lesdits objets correspondants seulement, de l'appartenance au domaine de recherche o. 9. Procédé de recherche d'objet selon l'une quelconque des revendications précédentes, caractérisée en ce que la phase (1) de définition et de tri d'objets est réalisée une fois pour toutes dans un domaine donnée, les résultats de ladite phase (1) de définition et de tri d'objets étant chargés dans un appareil de lecture, et en ce que la phase (2) de recherche est exécutable chaque fois qu'une recherche est demandée. 10. Procédé de recherche d'objet selon la revendication 9, caractérisé en ce que la phase (2) de recherche est implémentée sous la forme d'un programme exécutable stocké au sein d'un terminal d'exploitation. 11. Procédé de cartographie vectorielle, pour cartographier un territoire A comprenant un ensemble d'objets décrits par une matrice M ; mettant en oeuvre le procédé de recherche d'objet selon l'une des revendications précédentes, caractérisé en ce qu'il comprend les étapes suivantes : - une détermination de la liste des mailles actives, comprenant un calcul de l'ensemble des codes de matrice correspondant aux mailles qui intersectent le domaine de recherche, et - une sélection et un traitement éventuel des objets. 12. Procédé de cartographie vectorielle selon la revendication 11, mis en oeuvre dans un domaine bidimensionnel, caractérisé en ce qu'il comprend un matriçage selon une pluralité de matrices géométriques rectangulaires comportant des mailles régulières, chaque matrice géométrique présentant une norme différente incluant la longueur et la largeur des mailles de ladite matrice. 13. Procédé de cartographie vectorielle selon la revendication 11 mis en oeuvre en cartographie bi-dimensionnelle étendue à niveaux multiples, caractérisé en ce qu'il comprend les séquences suivantes : l'ensemble initial n de N objets est décomposé en une pluralité de Z sous-ensembles Q d'objets de même niveau, avec = 1 à Z, - la matrice M initiale est décomposée en Z matrices M, on utilise le matriçage d'une façon indépendante pour chaque sous- ensemble. 14. Système de cartographie vectorielle, comprenant des moyens pour traiter des objets contenus dans un domaine au sein d'un espace A contenant un ensemble d'objets décrits dans une matrice M initiale, comprenant une construction d'un sous-ensemble w d'objets contenus dans ledit domaine 5 par extraction d'une matrice p à partir de la matrice M initiale, caractérisé en ce qu'il comprend en outre : - des moyens pour créer un matriçage M de l'espace A en superposant une pluralité de matrices géométriques de normes p différentes, représentant une couverture du domaine par un ensemble déterminé et homogène de sousdomaines similaires, chacune des mailles de chaque matrice géométrique étant identifiée par un index spécifique et unique appelé code de matrice, - des moyens pour déterminer pour l'ensemble du matriçage M toutes les mailles incluses dans le domaine 5 ou intersectées par le domaine 5, et le nombre d'objets concernés comme la somme des nombres d'objets des mailles concernées, - des moyens pour trier la matrice M par codes de matrice selon un ordre prédéterminé, croissant ou décroissant, des normes p, et - des moyens pour construire la matrice d'extraction u décrivant les seuls objets concernés par lesdites mailles incluses dans le domaine ou intersectées par le domaine 8. 15. Appareil électronique, notamment équipement de communication et/ou de navigation, mettant en oeuvre le procédé de cartographie vectorielle selon l'une des revendications 11 à 13.