FR 2632751 A1 19891215 FR 8903094 A 19890309 "Procédé pour des représentations de réseaux routiers dans des mémoires de données, applicable à la circula- tion automobile en ville *' L'invention part d'un procédé pour -détermi- -5 ner-et stocker des données importantes pour une repré- sentation d'un réseau routier dans une mémoire de don- nées, qui est utilisée dans. un véhicule avec une navi- gation à l'estime pour trouver un but choisi. Dans les Bosch Technischen Berichten, volume 8/86, fascicule 1/2, pages 61 à 65, est décrit un pro- cédé pour la mise sous forme numérique et la mémorisa- tion de représentations de réseaux routiers destinées à un système autarcique de repérage pour des véhicules de service, tels que des véhicules de police, des vé- hicules de lutte contre l'incendie, ou autres. Ces représentations de réseaux routiers sont, dans le cas de ce document, stockées dans une matrice de mémoire sur une représentation de trame en deux dimensions par des ensembles de chiffres binaires appropriés, en étant par exemple obtenues par exploration optique et par scanner, à partir d'.un plan de ville ou bien de feuilles topographiques, Selon la densité des voies, la trame est alors choisie de façon que, d'une part, les besoins totaux de stockage de la matrice soient limités, et que, d'autre part, l'ensemble de chiffres binaires stockés, permette une association nette aux voies. Ce procédé présente l'inconvénient que pour la mise sous forme numérique d'un plan de ville, une dépense élevée de mémorisation est nécessaire. En outre, dans presque tous les cas, les données des plans de villes doivent alors être à nouveau relevées avant qu'elles puissent être stockées sous forme numérique, car les représentations de plans de villes utilisables pour des calculateurs, ou bien n'existent pas ou bien, à cause de prescriptions pour la protection des don- nées, ne peuvent pas être obtenues. Un autre inconvé- nient réside en ce qu'une telle représentation de ré- seaux routiers ne prévoit pas l'affectation de numéros d'habitation le long des voies, de sorte que l'intro- duction d'adresses de buts sous la forme de voies et de numéros d'habitation, n'est pas possible. En con- séquence, avec la navigation à l'estime connue, seul l'emplacement respectif des véhicules est indiqué.par la représentation du réseau routier ainsi mémorisé. Dans un autre procédé connu par le document WO 87/.D1 442, pour la détermination et l'introduction et le stockage dans une mémoire de données de naviga- tion d'emplacements et de buts, les coordonnées polai- res des points de départ et d'arrivée, sont détermi- nées avec un appareil de mesure spécial à partir de cartes quelconques et sont introduites, en même temps que l'échelle de la carte, par l'intermédiaire de tou- ches et d'affichages, dans.la mémoire correspondante du calculateur de navigation. Pendant le parcours de navigation, la direction et l'éloignement du but appe- lé, sont alors respectivement indiqués par la naviga- tion à l'estime. Cette solution présente toutefois l'inconvénient que, lors de la détermination et de l'introduction des points de départ et d'arrivée au -2632751 moyen de leurs coordonnées polaires, on doit procéder avec beaucoup de soin. Comme, en outre, lors de l'in- troduction des buts, l'adresse respective ne peut être souvent pas du tout relevée sur les plans de voies, ou bien ne peut l'être que par estimation, de tels buts ne peuvent pas être introduits de façon précise ni être abordés de façon précise par navigation à l'esti- me. L'invention a pour but de remédier à ces in- convénients et concerne à cet effet, un procédé carac- térisé en ce que: a) chaque voie de la représentation du réseau routier est munie d'un signe distinctif déposé dans la mé- moire de données, b) à partir d'une collection de données pour chaque voie de la représentation du réseau routier, sont successivement appelés, en tant que matériaux de données de points d'appui marquants, tels que ces centres de gravité d'habitations,-des raccordements de distribution, dont les coordonnées sont munies d'un numéro d'habitation qui leur est associé, et temporairement stockés, c) pour lisser la densité de points d'appui le long du tracé de la voie, à partir respectivement de trois points d'appui successifs choisis, le milieu entre respectivement le premier et le troisième point d'appui est déterminé et temporairement stocké, d) ensuite, le second point d'appui respectif est pro- jeté sur une droite entre le premier et le troisiè- me point d'appui et sa distance au milieu entre le premier et le troisième point d'appui est détarmi- née, e) la distance est comparée avec une valeur limite prédéfinie, f) le second point d'appui est supprimé avec ses don- nées dans la mesure o la distance est inférieure à la valeur limite, g) finalement, les points d'appui non supprimés sont sortis avec leurs données et avec le signe distinc- tif de la voie en tant que données importantes pour la mémoire de données. Avec la présente invention, on s'efforce de faciliter la navigation pour des véhicules automobiles par appel des rues et des numéros d'habitation du point de départ et du point d'arrivée, en déterminant à partir de recueils halogènes de données et en stoc- kant dans une mémoire de données un système de naviga- tion, un nombre limité de données importantes pour une représentation de réseaux routiers. Le procédé conforme à l'invention défini ci- dessus, présente l'avantage qu'en tenant compte des prescriptions de protection de données, on prépare à partir de recueils halogènes de données, un nombre, nécessaire pour la navigation, de points marquants de représentations de réseaux routiers, tels que par exemple les coordonnées de centres de gravité d'habi- tations, de raccordements de distribution, de prises d'eau, de vannes d'arrêt d'eau et de gaz, de façon que ces données soient associées à des voies et à des nu- méros d'habitations déterminés. En outre, grâce au procédé conforme à l'invention, la quantité de données à stocker peut être réduite de façon que même pour des représentations de réseaux routiers de grandes villes, les besoins en mémorisation utilisée puissent être couverts par des mémoires à semi-conducteurs, des dis- quettes, des bandes, des plaques CD, et des moyens analogues, qui puissent être logés dans le système de navigation d'un véhicule automobile. Un autre avantage à considérer est que les données ainsi obtenues des représentations de réseaux routiers, permettent une navigation fiable pour trouver les points d'arrivée, en ce que les points de départ et d'arrivée sont défi- nis par des voies et des numéros d'habitation et peu- vent être introduits de façon correspondante. D'autres caractéristiques de l'invention correspondent à des compléments avantageux et à des perfectionnements du procédé défini ci-dessus. Selon une autre caractéristique de l'inven- tion, tout d'abord, en partant d'une extrémité de la voie, les premiers trois points d'appui sont remaniés, et ensuite, en progressant respectivement d'un point d'appui, trois autres points d'appui sont sélectionnés pour le lissage de la densité des points d'appui, jusqu'à ce que le dernier point d'appui de la voie ait été appréhendé. Selon une autre caractéristique de l'inven- tion, le nombre des points d'appui importants de la voie est réduit à nouveau par un lissage du tracé de la voie, conformément à la demande de brevet P 37 44 531.6. Selon une autre caractéristique de l'inven- tion, avant lissage de la densité des points d'appui, le nombre des points d'appui importants de la voie est réduit par une pondération de points d'appui se si- tuant très près les uns des autres selon la demande de brevet P 37 44 533.2. Selon encore une autre caractéristique de l'invention, après la pondération et avant le lissage de la densité des points d'appui, le nombre des points d'appui importants de la voie est à nouveau réduit par une!inéarisation du tracé de la voie selon la demande de brevet P 37 44 531.6. Enfin, selon une autre caractéristique de l'invention, la valeur limite est une partie prédéfi- nie de la distance entre respectivement le premier et le troisième point d'appui. Un exemple de réalisation de l'invention est représenté sur les dessins ci-joints et va être exposé plus en détail dans la description ci-après: - la figure 1 est un diagramme fonctionnel du déroulement du procédé pour obtenir les données im- portantes d'un tracé de voie, - la figure 2 montre la représentation d'une voie avec des centres de gravité d'habitations comme points d'appui de cette voie, - la figure 3 est un diagramme fonctionnel pour la réduction des points d'appui à stocker de la voie en fonction de la répartition des points d'appui le long du tracé de la voie. Sur la figure 1 est représenté un diagramme fonctionnel qui montre le déroulement du procédé pour obtenir les données importantes pour une voie, à par- tir d'un recueil halogène de données d'un service to- pographique, ce recueil contenant les coordonnées de centres de gravité des habitations sur la voie choi- sie. On part alors de ce que pour la navigation selon des données d'un plan de ville, une base de données est nécessaire dans laquelle une représentation aussi simple que possible du plan de la ville doit être con- tenue. Les données doivent se présenter sous une forme compréhensible pour le système de navigation et être faciles à traiter. Il est nécessaire pour chaque voie individuelle, d'avoir des informations à partir des- quelles le tracé de la voie, sa position géographique, ainsi que des informations sur la répartition des nu- méros d'habitations le long de la voie, apparaissent sous une forme appropriée. Les informations sur les numéros d'habita- tions existants dans la voie, doivent permettre une conclusion en retour sur la position d'un numéro d'ha- bitation déterminé à l'intérieur de la voie. Dans le cas de voies courtes ou bien de places, le numéro d'habitation est en principe d'une importance réduite, car il importe somme toute uniquement, dans ce cas, de trouver la voie ou la place. Mais une plus grande im- portance s'attache aux numéros d'habitations lorsque dans des voies d'une grande extension superficielle, un point déterminé doit être abordé. Comme dans pres- que tous les services topographiques allemands, il existe pour les zones dont ils ont la charge, des re- cueils de données sur les parcelles de terrains et les centres de gravité d'habitations, ces recueils con- viennent particulièrement bien pour obtenir les don- nées importantes de représentations de réseaux rou- tiers dans des buts de navigation. Chacune des voies dans la représentation du réseau routier, les étapes de procédés représentées sur la figure 1 et décrites plus en détail ci-après, sont successivement traitées dans une installation électronique de traitement de données. Si toutes les voies sont appréhendées en même temps que leurs signes distinctifs, on obtient une mé- moire de données utilisable pour la navigation à l'es- time avec les données importantes de l'ensemble de la représentation du réseau routier. Après le démarrage 10 du programme, dans une - première étape 11 du procédé pour une voie sélection- née, les centres de gravité des habitations se situant sur cette voie, sont appelés à-partir du recueil halo- gène de données, et temporairement mémorisés. Dans l'étape 12 du procédé, des centres de gravité d'habi- tations très proches les uns des autres, sont pondérés pour obtenir un centre de gravité commun, de sorte qu'une partie des données initiales est supprimée. Dans l'étape 13 du procédé, l'ensemble des tracés de la voie est linéarisé en une ou en plusieurs sections, rectilignes partielles de façon que l'ensemble des ha- bitations à l'intérieur d'une largeur de bande prédé- finie, se situe à côté du tracé de la voie ainsi li- néarisée. Les points initiaux et terminaux de ces sec-- tions partielles rectilignes, sont mémorisés temporai- rement et les autres points intermédiaires peuvent être supprimes. Dans l'étape 14 du procédé, trois points d'appui successifs sont respectivement appelés, pour comparer entre elles les distances du point d'appui médian aux points d'appui voisins. Dans la mesure o les distances d'un point d'appui à ces deux points d'appui voisins, sont à peu près identiques à l'inté- rieur d'une valeur limite prédéfinie, le point d'appui médian est supprimé. Lors du parcours ultérieur de na- vigation, la position de ce point d'appui ainsi sup- primé, par exemple lors de l'introduction d'un point de départ et d'un point d'arrivée, doit être détermi- née par un calculateur de navigation avec la précision nécessaire, par interpolation entre les deux points d'appui mémorisés adjacents. Dans l'étape 15 du procédé, deux sections partielles successives linéarisées dans l'étape 13, sont respectivement lissées pour obtenir une nouvelle section partielle commune, lorsque le point de jonc- tion des deux sections partielles n'est pas éloigné de la nouvelle section partielle d'une distance supérieu- re à une valeur prédéfinie. Dans ce cas, le point se trouvant entre ces deux sections partielles successi- ves, est également effacé. Dans l'étape 16 du procédé, les points d'appui restant sont- maintenant déposés avec leurs coordonnées et les numéros d'habitations qui leur sont associés, en même temps que le signe distinctif de la voie, dans la mémoire de données du dispositif de navigation. Finalement, le programme est stoppé à l'étape 17. Un autre tracé de voies de la re- présentation du réseau routier, peut désormais être traité. Les étapes 11, 12, 13 et 15 du procédé re- présenté sur la figure 1, sont exposées plus en détail dans les demandes de brevet P 37 44 531.6 et P 37 44 533.2. La figure 2 montre schématiquement le tracé d'une voie 18 de la représentation de réseaux routiers à mémoriser. Sur cette figure, en outre, les points d'appui 19 de la vpie prévus pour obtenir les données importantes, sont représentés sous la forme de centres de gravité d'habitations dont les coordonnées ont été appelées à partir d'un recueil halogène de données de services topographiques ou analogues. Ces points d'ap- pui sont représentés sur la figure 2 avec leurs numé- ros d'habitations. Il y a lieu de veiller à-ce que, en dehors du nombre de points d'appui 19 avec leurs coor- données, il n'y ait pas d'autres informations disponi- bles sur la voie. Le tracé effectif de la voie ne doit pas être relevé à partir du recueil halogène de don- nées. Il ne peut, tout au plus, être pressenti qu'à partir de la position des centres de gravité d'habita- tions, et à partir de la répartition des numéros d'ha- bitations. Dans le tracé de voies représenté selon la figure 2, les constructions de bâtiments sont respec- tivement représentées au début et à la fin de la voie 18. A l'aide de cette représentation, on va exposer le procédé selon la figure 3, grâce auquel, les distances des habitations successives sont vérifiées de façon que, dans le cas d'unc densité de constructions rela- tivement uniforme, les points d'appui d'habitations se situant entre le premier et le dernier point d'appui sur la partie de voie comportant une uniformité de construction, soient supprimés, de sorte qu'ils n'ap- paraissent pas dans la mémoire de données. La position de ces points sera ultérieurement, lors des parcours de navigation, déterminée pour l'introduction du point d'arrivée ou pour l'introduction du point de départ, par interpolation linéaire entre les points d'appui mémorisés. Pour chaque nouvelle voie devant être intro- duite dans la réalisation de réseaux routiers à conce- voir, les étapes 11, 12, 13 du programme, selon le diagramme fonctionnel de la figure 1, sont tout d'a- bord parcourues. Ensuite, dans l'étape 14 du program- me, le sous-programme concernant le lissage de la den- sité des points d'appui selon la figure 3, est appelé. Après le démarrage 20, on vérifie tout d'abord dans l'étape 21 du programme, si la voie appelée comporte plus de deux points d'appui. Si ce n'est pas le cas, il n'y a pas lieu d'effectuer un lissage de la densité des points d'appui. En conséquence, on revient dans l'étape 22 au programme principal selon la figure 1. S'il existe, toutefois, pour la voie appelée trois points d'appui ou davantage, alors le point d'appui comportant le numéro d'habitation le plus petit est tout d'abord appelé dans l'étape 23 et il est mémorisé en tant que point de départ dans l'étape 24. Sur la représentation de la voie selon la figure 2, cela cor- respond au point d'appui avec le numéro d'habitation 1. Dans l'étape 25, le point d'appui avec le numéro d'habitation immédiatement plus élevé, ici le numéro d'habitation 2, est alors appelé et mémorisé temporai- rement. Dans l'étape 26, le point d'appui suivant com- portant dans ce cas, le numéro d'habitation 3, est ap- pelé et mémorisé temporairement en tant que point ter- minal. Dans l'étape 27, une droite est tirée mathéma- tiquement entre le point de départ et'le point termi- nal, et dans l'étape 28, le milieu A entre le premier et le troisième point d'appui est déterminé et mémori- sé temporairement. Dans l'étape 29, le point d'appui médian avec le numéro d'habitation 2, est projeté sur la droite entre le premier et le troisième point d'appui, comportant les numéros d'habitation 1 et 3, et ensui- te, dans l'étape 30, la distance b entre la projection 2' du point d'appui et le milieu A est déterminée. Dans l'étape 31, la distance b ainsi déterminée est comparée avec une valeur limite prédéfinie a, qui re- présente une mesure pour le manque de régularité enco- re admissible de la densité des constructions. Cette valeur limite a peut être, soit une valeur fixe allant de 10 à 20 mètres, soit, de préférence, dans le cas d'une densité de constructions plus réduite, être dé- terminée à partir d'une fraction allant de 10 à 15 % de la distance entre le point de départ et le. point terminal. Si la distance b déterminée dans l'étape 30 est supérieure à la valeur limite a, il n'y a pas de densité uniforme de constructions et le point d'appui médian ne doit pas être supprimé. Il est en conséquen- ce mémorisé dans l'étape 32 du programme. Si, par con- tre, la distance b est égale ou inférieure à la valeur limite a, les données du point d'appui médian sont supprimées, en ce sens qu'elles ne sont pas mémori- sées. Dans l'étape 13 du programme, ce second point d'appui est alors appelé avec le numéro d'habitation 2 directement en tant que nouveau point de départ. Dans l'étape 34 on vérifie s'il y a encore d'autres points d'appui de la voie. Tant que ceci est le cas, le programme revient, par l'intermédiaire de la boucle 35, à l'étape 25 du programme, le point d'appui comportant le numéro d'habitation 3 étant mé- morisé temporairement en tant que prochain point d'ap- pui et dans l'étape 26, le point d'appui comportant le numéro d'habitation 4 étant appelé en tant que nouveau point final. Avec les étapes 28 à 31 du programme, la distance de la projection sur la droite de liaison du second point d'appui, comportant cette fois le numéro d'habitation 3, au nouveau milieu calculé, est déter- minée et comparée avec la valeur limite a. La boucle avec les étapes 25 à 34 du programme se répète ainsi jusqu'à ce que, dans l'étape 34, on ne trouve plus au- cun point d'appui de la voie. Le dernier point termi- nal déterminé est également mémorisé dans l'étape 36 et dans l'étape 37 tous les points d'appui encore sub- sistants sont sortis pour le traitement complémentai- re. Dans l'étape 38, on retourne alors au programme principal selon la figure 1. La partie du procédé décrite avec le dia- gramme fonctionnel selon la figure 3, pour la réduc- tion des points d'appui importants à mémoriser lors de la représentation de la voie, en considération de la densité de constructions, peut éventuellement être parcourue également deux fois, et ceci de façon sépa- rée pour les points d'appui comportant des numérbs d'habitations pairs, et les points d'appui comportant des numéros d'habitations impairs. Ceci est notamment -avantageux lorsque la densité de construction est très différente d'un côté de la chaussée, en comparaison avec l'autre côté. Lors des parcours de navigation, la découverte de constructions par interpolation des points d'appui mémorisés, sur le côté droit ou sur le côté gauche de la chaussée, peut ainsi être encore améliorée. Dans le cas de l'exemple selon la figure 2, une telle densité de constructions différente entre le côté gauche et le côté droit de la chaussée, ne se présente pas, de sorte qu'on s'en tire, dans ce cas, avec un seul parcours du diagramme fonctionnel selon la figure 3. Dans la figure 2, il est en outre indiqué qu'au début de la chaussée 18, les distances des points d'appui comportant les numéros d'habitation 1 à 4, le long de cette chaussée 18, sont très différen- tes. La distance b de la projection 2' entre le point d'appui 1 et le point d'appui 3 sur la droite, est su- périeure à la valeur limite prédéfinie a. Le point. d'appui comportant le numéro d'habitation 2 ne doit, en conséquence, pas être supprimé. A l'extrémité de la voie 18, les points d'appui comportant les numéros d'habitations 80, 81 et 82 le long du tracé de la voie, ont, par contre, une distance relativement iden- tique entre eux. La distance b' par rapport au milieu A' du point d'appui projeté avec le numéro d'habita- tion 81' est inférieure à la valeur prédéfinie a. Le point d'appui avec le numéro d'habitation 81 est, en conséquence, supprimé lors du parcours de la partie du procédé correspondant à la figure 3. Après le parcours du diagramme fonctionnel selon la figure 3, ies points d'appui 19 de la voie 18 qui sont restés en excédent dans l'étape 37 du procé- dé, sont amenés à un lissage du tracé de la voie, con- formément au programme principal selon la figure 1, *dans l'étape 15 du procédé. Mais en variante de l'exemple de réalisation décrit, il est également possible, dans le' cadre de la présente invention, de réaliser la vérification et le lissage de la densité des points d'appui le long d'un tracé de voie, sans une pondération préalable des points d'appui et une linéarisation du tracé de la voie selon le diagramme fonctionnel de la figure 1. Ceci est notamment avantageux lorsque les voies des agglomérations et des villes ont un tracé rectiligne de bout en bout, ce qui est souvent le cas là o la configuration résulte d'une planification.sur la plan- che à dessin.. Grâce au procédé décrit, il est possible, d'une part, d'obtenir à partir d'un recueil halogène de données, suffisamment de données importantes pour la représentation des voies d'un réseau routier, de sorte qu'un but indiqué par la voie et le numéro d'ha- bitation peut être trouvé par un véhicule avec une na- vigation à l'estime. D'autre part, les données préle- vées à partir d'un recueil halogène de données sont sélectionnées par le procédé décrit de façon qu'ainsi, tout en tenant compte des prescriptions sur la protec- tion des données, on puisse se reporter à des recueils de données existants. Avec les données de représentations de ré- seaux routiers obtenues après mise en oeuvre du procé- dé décrit, données qui sont mémorisées définitivement dans une mémoire pour un dispositif de navigation dans des véhicules automobiles, les coordonnées de points de départ ou de points d'arrivée peuvent désormais, de façon connue, être déterminées pour suivre ensuite à l'aide de la navigation à l'estime, l'emplacement mo- mentané du véhicule et pour permettre d'atteindre un but. Le dispositif de navigation approprié à cet ef- fet, est également décrit en détail dans la demande de brevet P 37 44 531.6. REVENDICATIONS 1.- Procédé pour déterminer et stocker des données importantes pour une représentation d'un ré- seau routier dans une mémoire de données, qui est Uti- lisée dans un véhicule avec une navigation à l'estime pour trouver un but choisi, procédé caractérisé en ce que: a) chaque voie (18) de la représentation du réseau routier est munie d'un signe distinctif déposé dans la mémoire de données, b) à partir d'une collection de données pour chaque voie (18) de la représentation du réseau routier, sont successivement appelés, en tant que matériaux - de données de points d'appui marquants (19), tels que des centres de gravité d'habitation, des rac- cordements de distribution, dont les coordonnées sont munies d'un numéro d'habitation qui leur est associé, et temporairement stockés, c) pour lisser la densité des points.d'appui le long du tracé de la voie, à partir respectivement de trois points d'appui successifs choisis (19), le milieu (A, A') entre respectivement le premier et le troisième point d'appui (19) est déterminé et temporairement-stocké, d) ensuite, le second point d'appui respectif est pro- jeté sur une droite entre le premier et le troisiè- me point d'appui (19) et sa distance (b, b') au mi- lieu (A, A') entre le premier et le troisième point d'appui (19) est déterminée, e) la distance (b, b') est comparée avec une valeur limite (a) prédéfinie, f) le second point d'appui (19) est supprimé avec ses données dans la mesure o la distance (b, b') est inférieure à la valeur limite (a), g) finalement, les points d'appui (19) non supprimés sont sortis avec leurs données et avec le signe distinctif de la voie en tant que données importan- tes pour la mémoire de données. 2.- Procédé selon la revendication 1, carac- térisé en ce que tout, d'abord, en partant d'une ex- trémité de la voie (18) les premiers trois points d'appui (19) sont remaniés, et ensuite, en progressant respectivement d'un point d'appui (19), trois autres points d'appui sont sélectionnés pour le lissage de la densité des points d'appui, jusqu'à ce que le dernier point d'appui (19) de la voie (18) ait été appréhendé. 3.- Procédé selon l'une quelconque des re- vendications 1 ou 2, caractérisé en ce que le nombre des points d'appui importants (19) de la voie est ré- duit à nouveau par un lissage du tracé de la voie. 4.- Procédé selon l'une quelconque des re- vendications i à 3, caractérisé en ce qu'avant un lis- sage de la densité des points d'appui, le nombre des points d'appui importants (19) de la voie est réduit par une pondération de points d'appui (19) se situant très près les uns des autres. 5.- Procédé selon la revendication 4, carac- térisé en ce qu'après la pondération et avant le lis- sage de la densité des points d'appui, le nombre des points d'appui (19) importants de la voie est à nou- veau réduit par une linéarisation du tracé de la voie. 6.- Procédé selon l'une quelconque des re- vendications 1 à 5, caractérisé en ce que la valeur limite (a) est une partie prédéfinie de la distance entre respectivement le premier et le troisième point d'appui (19).