Navigation system using corridor maps
Abstract
A procedure for displaying a map (212) on a mobile client device (202), the procedure comprising: The storage of map data on a server (206), the map data comprising information of the vectors that delineate characteristics in the map; The determination of a route (1730) from a starting point to a destination within an area of the map, the route comprising a sequence of segments of the route (1632), each segment of the route being provided with a length and an angle respective heading; The definition of a map of the corridor on the server, the map of the corridor comprising a plurality of segments of the map, each segment of the map containing a respective segment of the route and having a respective magnification level and an orientation determined by the length and the heading angle of the respective segment of the route; The downloading of the vector information in the map segments from the server to the client device; and The generation on the client device of a succession of images of the map segments as the user travels along the route.

Term
Term ended
Projected expiry passed 29 April 2023, 3.4 years ago.
- Priority
- Filed
- Published
- Projected expiry
- Today
11 claims: 7 independent, 4 dependent
- 1ES 2 425 555 T3 REIVINDICACIONES 1. Un procedimiento para la visualización de un mapa (212) en un dispositivo cliente móvil (202), el procedimiento comprendiendo:El almacenaje de datos de mapas en un servidor (206), los datos de los mapas comprendiendo información de los vectores que delinean características en el mapa;La determinación de una ruta (1730) desde un punto de inicio hasta un destino dentro de un área del mapa, la ruta comprendiendo una secuencia de segmentos de la ruta (1632), cada segmento de la ruta estando provisto de una longitud y un ángulo de rumbo respectivos;La definición de un mapa del corredor en el servidor, el mapa del corredor comprendiendo una pluralidad de segmentos del mapa, cada segmento del mapa conteniendo un segmento respectivo de la ruta y que tiene un nivel de ampliación respectivo y una orientación determinados por la longitud y el ángulo de rumbo del respectivo segmento de la ruta;La descarga de la información del vector en los segmentos del mapa a partir del servidor al dispositivo cliente;y La generación en el dispositivo cliente de una sucesión de imágenes de los segmentos del mapa a medida que el usuario viaja a lo largo de la ruta.
- 2El procedimiento según la reivindicación 1 en el que la descarga de la información de los vectores comprende la descarga de los segmentos del mapa uno después de otro en secuencia a medida que el usuario viaja a lo largo de la ruta.
- 3El procedimiento según la reivindicación 1 o 2 en el que la definición del mapa del corredor comprende recortar cada uno de los segmentos del mapa de modo que se incluyan dentro del segmento del mapa las características en el mapa que quedan dentro de una distancia previamente determinada de cada uno de los segmentos de la ruta.
- 4El procedimiento según la reivindicación 3 en el que las características incluidas dentro del segmento del mapa comprenden encrucijadas que forman intersección con la ruta y en el que la generación de la sucesión de las imágenes comprende, en el dispositivo cliente, la detección de una desviación del usuario de la ruta y, en respuesta a la desviación, la visualización de un recorrido hacia la ruta en una de las encrucijadas.
- 5El procedimiento según cualquiera de las reivindicaciones anteriores en el que la determinación de la ruta comprende:La recepción de una entrada en el dispositivo cliente que indica un tipo de punto de interés buscado por un del dispositivo cliente;La identificación de nombres de uno o más puntos de interés del tipo indicado en una base de datos a la que accede el servidor;y La devolución de los nombres de uno o más puntos de interés al dispositivo cliente, de modo que permita al usuario seleccionar uno de los puntos de interés como el destino.
- 6El procedimiento según cualquiera de las reivindicaciones anteriores y que comprende la determinación de una ubicación del usuario utilizando un dispositivo que proporciona ubicaciones asociado con el dispositivo cliente y en el que la generación de la sucesión de las imágenes comprende la indicación de una ubicación del usuario en los segmentos del mapa.
- 7El procedimiento según la reivindicación 6 y que comprende, en respuesta a la ubicación del usuario, instruir al usuario para que realice maniobras específicas a lo largo de la ruta mediante por lo menos una de ambas, proporcionar direcciones verbales al usuario y la visualización de mapas de maniobra en el dispositivo cliente.
- 8El procedimiento según cualquiera de las reivindicaciones anteriores en el que la información de los vectores comprende coordenadas de los vectores de las características en el mapa en un marco de referencia previamente determinado y en el que la descarga de la información de los vectores comprende:La determinación de un rumbo de viaje del usuario en por lo menos uno de los segmentos de la ruta sobre la base de la ubicación del usuario;ES 2 425 555 T3 La transformación en el servidor de las coordenadas del vector de las características en por lo menos uno de los segmentos del mapa que contiene el por lo menos uno de los segmentos de la ruta en un marco de referencia girado, el cual está aproximadamente alineado con el rumbo;y La descarga al dispositivo cliente desde el servidor de la información de los vectores que comprende las coordenadas transformadas de los vectores de las características en el por lo menos uno de los segmentos del mapa, de modo que el dispositivo del cliente genera una imagen del por lo menos uno de los segmentos del mapa en el marco de referencia girado.
- 9El procedimiento según cualquiera de las reivindicaciones anteriores y que comprende:La recepción en el servidor, mientras el usuario viaja a lo largo de la ruta, de información dinámica con respecto a un cambio en las condiciones del viaje en una proximidad de la ruta;La sumisión de una petición desde el dispositivo cliente al servidor de información actualizada con respecto a la ruta, la petición especificando, sobre la base de la ruta descargada y la ubicación del usuario, uno o más de los segmentos de la ruta todavía no atravesados por el usuario;y La determinación en el servidor, sobre la base de los segmentos de la ruta especificados por el dispositivo cliente y de la información dinámica recibida por el servidor, una ruta modificada hacia el destino;en el que la definición del mapa del corredor comprende la modificación del mapa del corredor en respuesta a la ruta modificada.
- 10Un aparato para la visualización de un mapa (212) en un dispositivo cliente móvil (202) el aparato comprendiendo:Una memoria (714, 720);y Un servidor de cartografía (206), el cual está adaptado para almacenar datos de mapas en la memoria, los datos de los mapas comprendiendo información de vectores que delinean las características en el mapa, el servidor estando adicionalmente adaptado para determinar una ruta (1730) desde un punto de inicio hasta un destino dentro de un área del mapa, la ruta comprendiendo una secuencia de segmentos de la ruta (1632), cada segmento de la ruta estando previsto de una longitud y un ángulo de rumbo respectivos, y para definir un mapa del corredor en el servidor, el mapa del corredor comprendiendo una pluralidad de segmentos del mapa, cada segmento del mapa conteniendo un segmento respectivo de la ruta y provisto del nivel de la ampliación y la orientación respectivos determinados por la longitud y el ángulo del rumbo del respectivo segmento de la ruta y para descargar la información de los vectores en los segmentos del mapa al dispositivo cliente, de modo que se cause que el dispositivo cliente genere una sucesión de imágenes de los segmentos del mapa a medida que el usuario del dispositivo cliente viaja a lo largo de la ruta.
- 11Un producto de soporte lógico de ordenador para la visualización de un mapa (212) en un dispositivo cliente móvil (202), el producto comprendiendo un medio legible por ordenador en el cual están almacenadas instrucciones de programas, instrucciones las cuales, cuando son leídas por un ordenador (206), causan que el ordenador acceda a datos de mapas en una memoria (714, 720), los datos de los mapas comprendiendo información de los vectores que delinean características en el mapa y para determinar una ruta (1730) desde un punto de inicio hasta un destino dentro de un área del mapa, la ruta comprendiendo una secuencia de segmentos de la ruta (1632), cada segmento de la ruta estando provisto de una longitud y un ángulo de rumbo respectivos y para definir un mapa del corredor en el servidor, el mapa del corredor comprendiendo una pluralidad de segmentos del mapa, cada segmento del mapa conteniendo un segmento respectivo de la ruta y provisto de un nivel de ampliación y una orientación respectivos determinados por la longitud y el ángulo de rumbo del segmento respectivo de la ruta y para descargar la información de los vectores en los segmentos del mapa al dispositivo cliente, de modo que cause que el dispositivo cliente genere una sucesión de imágenes de los segmentos del mapa a medida que el usuario del dispositivo cliente viaja a lo largo de la ruta.
Independent claims11
321 paragraphs in 16 sections, as filed
ES 2 425 555 T3
DESCRIPTION
Navigation system using corridor maps
FIELD OF THE INVENTION
The present invention relates to data display and distribution systems and methodologies and more particularly to map data display systems and methodologies.
BACKGROUND OF THE INVENTION
A variety of systems are known in the art to provide drivers with electronic vehicle routing maps and navigation aids. These systems are typically coupled to a location-location device in the vehicle, such as a global location system (GPS) receiver. The GPS receiver automatically determines the current location of the vehicle, to be displayed on the map and used in determining routing instructions.
In-vehicle navigation systems fall into two general categories: on-board systems, in which map data is stored electronically in the vehicle (typically on optical or magnetic media); and off-board systems, in which the map data is provided by a remote mapping server. These systems typically use a client program that runs on a smart cell phone or a personal digital assistant (PDA) in the vehicle to retrieve information from the server over a wireless link and display maps and provide navigation instructions to the driver.
Various off-board navigation systems are described in the patent literature. For example, US patent US 6,381,535 describes improvements required to convert a portable radiotelephone into a mobile terminal capable of functioning as a navigation aid system. Requests for itineraries from the mobile terminal are transmitted to a centralized server via a radio-relay link. The server calculates the requested itinerary and transmits the itinerary to the mobile terminal in the form of straight lines and arc segments that concern the data constituting the itinerary. The server also evaluates the possibility of the vehicle deviation from its route and transmits the relevant segments of the route data of the possible deviation in an area close to the main route.
Other off-board navigation systems are described in Patent Cooperation Treaty (PCT) publications WO 01/01370 and WO 01/27812; in American patents US 6,038,559, 6,107,944, 6,233,518, 6,282,489, 6,320,518, 6,347,278, 6,381,535, 6,462,676, 6,493,630 and 6,526,284; and in American patent application publication US 2001/0045949.
US 2001/001847 A1 discloses a navigation system having a server and a mobile client. A map used in this system is divided into segments prior to receipt of a requested route and is therefore independent of the requested route.
SUMMARY OF THE INVENTION
Embodiments of the present invention provide improved methods and systems for off-board navigation and mapping. These methods and systems allow rich, dynamic information to be downloaded quickly and efficiently from a mapping server over a low speed wireless link to a client device, typically a personal digital assistant (PDA) or a cellular phone. Wireless links of this type are typically characterized by bandwidths below 10 kbits per second (kbit / s). Novel data processing procedures, on both the server and client sides of the interaction, enable the client to display maps to the user with improved speed and clarity, despite limited communication bandwidth and limited capabilities client device display.
In one aspect of the present invention, map data is stored on the server and downloaded to the client in the form of vector data. In response to a route request from the client, the server determines a route from a starting point to a destination specified by the client. Typically, the starting point is the customer's current position, while the destination is a customer-specified location or point of interest on the map. The route calculated by the server comprises a sequence of route segments, each of which has a respective length and heading angle. The server then defines a corridor map, made up of a sequence of map segments, each containing one or more of the route segments. The magnification level and orientation of each map segment is determined by the length and heading angle of the respective route segment, so generally different segments have different magnification levels and heading angles. The map segments are downloaded from the server to the client device (in the form of vector data) in succession, as the client travels along the path.
ES 2 425 555 T3
Building and downloading the corridor map in this way presents the user of the client device with a sequence of maps that are easy to understand and follow, while minimizing the computational power and memory required for the process of generating the maps in the client device. Each segment map is roughly oriented according to the customer's current direction of travel, with a level of detail that roughly corresponds to the complexity of the currently ordered driving maneuvers.
There is provided, according to an embodiment of the present invention, a method for displaying a map on a mobile client device, the method including:
Storing map data on a server, map data including vector information delineating features on the map;
Determining a route from a starting point to a destination within a map area, the route including a sequence of route segments, each route segment being provided with a respective length and heading angle;
The definition of a corridor map on the server, the corridor map including a plurality of map segments, each map segment containing a respective route segment and provided with a respective magnification and orientation level determined by the length and the heading angle of the respective route segment;
Downloading the vector information in the map segments from the server to the client device; Y
The generation on the client device of a succession of images of the map segments as the user travels along the route.
Typically, downloading the vector information includes downloading the map segments one after the other in sequence as the user travels along the route and the definition of the corridor map includes the definition of the map segments. map so that the map segments downloaded in the sequence include approximately equal amounts of data.
Additionally or alternatively, the definition of the corridor map includes cropping each of the map segments so as to include within the map segment the features on the map that fall within a predetermined distance of each of the route segments. . In one embodiment, the features included within the map segment include crossroads that intersect the route and where the image sequence generation process includes, at the client device, the detection of a user deviation from the route and, in response to the deviation, the display of a route back to the route at one of the junctions.
In a further embodiment, determining the path includes receiving an input at the client device, the input including a string of user-entered characters; transferring the chain from the client device to the server; finding one or more destination names in a database accessed by the server, in response to a rough match between the string and the destination names; and returning the one or more names of the destination to the client device, allowing the user to select one of the names of the destination as the destination.
In yet another embodiment, determining the route includes receiving an input at the client device indicating a type of point of interest sought by a user of the client device; the transfer of the indicated type of the point of interest from the client device to the server; the identification of the names of one or more points of interest of the type indicated in a database accessed by the server; and returning the names of the one or more POIs to the client device, allowing the user to select one of the POIs as the destination.
In one aspect of the invention, determining a location of the user using a device providing locations associated with the client device and generating the succession of the images includes indicating a location of the user in the map segments. The procedure may include, in response to the user's location, instructing the user to perform specific maneuvers along the route using at least one of the verbal directions provided to the user and displaying the maneuver maps on the device. customer.
In one embodiment, the vector information includes the coordinates of the vectors of the features on the map in a predetermined reference frame and the downloading of the vector information includes the determination of a user's travel heading in at least one of the route segments based on the user's location; the transformation in the server of the coordinates of the vectors of the characteristics in at least one of the segments of the map that contains the at least one of the segments of the route in a rotated reference frame, which is approximately aligned with the course; and the
ES 2 425 555 T3 downloads the vector information from the server to the client device that includes the coordinates of the transformed vectors of the characteristics in at least one of the map segments, so that the client device generates a Image of at least one of the map segments in the rotated reference frame.
In yet another embodiment, the method includes receiving at the server, while the user travels along the route, dynamic information regarding a change in travel conditions in the vicinity of the route; submitting a request from the client device to the server for updated information regarding the route, the request specifying, based on the downloaded route and the user's location, one or more of the route segments not yet traversed by the user, and the determination at the server, based on the path segments specified by the client device and the dynamic information received by the server, a modified route to the destination, where the definition of the corridor map includes modifying the corridor map in response to the modified route.
Additionally provided, according to an embodiment of the present invention, an apparatus for displaying a map on a mobile client device, the apparatus including:
A memory; Y
A mapping server, which is adapted to store map data in memory, the map data including vector information delineating the features on the map, the server being further adapted to determine a route from a starting point to a destination within an area of the map, the route including a sequence of route segments, each route segment being provided with a respective length and heading angle and to define a corridor map on the server, the corridor map including a plurality of map segments, each map segment containing a respective route segment and having a respective magnification level and orientation determined by the length and heading angle of the respective route segment, and downloading the vector information in the map segments to the client device, such that the client device is caused to generate a succession of images of the map segments as the user of the client device travels along the path. route.
Additionally provided, according to an embodiment of the present invention, a computer software product for displaying a map on a mobile client device, the product including a computer-readable medium in which program instructions are stored, instructions which, when read by a computer, cause the computer to access map data in memory, map data including vector information delineating features on the map and for determining a route from a starting point to a destination within a map area, the route including a sequence of route segments, each segment of the route being provided with a respective length and heading angle and for defining a corridor map on the server, the corridor map including a plurality of map segments, each map segment containing a respective segment of the route and having a respective magnification level and orientation determined by the length and heading angle of the respective segment of the route and download the vector information in the map segments in the client device, so that the client device is caused to generate a succession of images of the map segments as the user of the client device travels along the route.
The present invention will be more fully understood from the following detailed description of the embodiments thereof, taken in conjunction with the drawings in which:
BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 is a simplified pictorial illustration of a real-time map display and distribution system constructed and operational in accordance with an embodiment of the present invention;
Figure 2A is a simplified pictorial illustration of a real-time map display and distribution system constructed and operational in accordance with another embodiment of the present invention;
Figures 2B-2F are schematic representations of screens displayed on a client device in a vehicle, showing maps and directions generated by the system of Figure 2A, in accordance with an embodiment of the present invention;
Figures 3-6 are simplified pictorial illustrations of real-time map display and distribution systems constructed and operational in accordance with further embodiments of the present invention;
Figure 7 is a simplified functional block diagram of a real-time map display and distribution system, according to an embodiment of the present invention;
Figure 8A is a block diagram schematically showing details of a mapping server,
ES 2 425 555 T3 according to an embodiment of the present invention;
Figure 8B is a block diagram schematically showing details of a mapping client, according to an embodiment of the present invention;
Figure 9 is a block diagram schematically illustrating data structures used to store and generate map data, in accordance with an embodiment of the present invention;
Figure 10A is a block diagram schematically illustrating additional details of the data structures depicted in Figure 9, in accordance with one embodiment of the present invention;
Figure 10B is a schematic representation of a computer screen of a template editor, which is used in setting the display properties of maps provided by a mapping server, in accordance with an embodiment of the present invention;
Figure 11 is a block diagram schematically illustrating data structures used by a mapping server in searching for geographic data, in accordance with an embodiment of the present invention;
Figure 12 is a block diagram schematically illustrating data structures used by a mapping server in providing route data, in accordance with an embodiment of the present invention;
Figure 13 is a flow chart schematically illustrating a procedure for handling map requests submitted to a mapping server, in accordance with an embodiment of the present invention;
Figures 14A and 14B are flow charts schematically illustrating a method of clipping map data for transmission to a mapping client, in accordance with an embodiment of the present invention;
FIG. 15A is a flow chart schematically illustrating a procedure for searching alphanumeric map data, in accordance with an embodiment of the present invention;
Figure 15B is a schematic representation of a screen displayed on a mobile device to allow a user to select a destination location, in accordance with an embodiment of the present invention;
Figure 16 is a flow chart schematically illustrating a procedure for handling requests for routes submitted to a mapping server, in accordance with an embodiment of the present invention;
Figure 17 is a graph schematically illustrating elements of a route corridor map generated by a mobile device on map data provided by a mapping server, according to an embodiment of the present invention;
Fig. 18 is a flow chart schematically illustrating a method for providing map data to accompany routing instructions, in accordance with another embodiment of the present invention;
Figure 19A is a flow chart schematically illustrating the operation of a mapping client, in accordance with an embodiment of the present invention;
Figures 19B-D are schematic representations of screens displayed on a mobile device to allow a user to select a destination location, in accordance with an embodiment of the present invention;
Figure 20A is a flow chart schematically illustrating a procedure for finding and displaying a point of interest on a map, in accordance with an embodiment of the present invention;
Figures 20B and 20C are schematic representations of screens displayed on a mobile device to allow a user to select a point of interest, in accordance with an embodiment of the present invention; Y
Figures 21A and 21B are flow charts schematically illustrating a method for manipulating map data received by a mapping client from the mapping server, in accordance with an embodiment of the present invention.
DETAILED DESCRIPTION OF FORMS OF REALIZATION
Reference is now made to FIG. 1, which is a simplified pictorial illustration of a real-time map display and distribution system constructed and operational in accordance with an embodiment of the present invention. As seen in Figure 1, a driver of a vehicle 100 communicates through a communicator without
ES 2 425 555 T3 wires, such as a conventional cellular telephone 102, with an interactive voice response processor (IVR) 104 and through the interactive voice response processor 104 over the Internet with a map server 106.
In the illustration, the driver requests directions to the Empire State Building. In real time, preferably within four seconds or less, while driving, the driver receives the requested directions. More preferably, the addresses are provided within two seconds, and most preferably the addresses are provided substantially immediately, that is, within one second. In the illustration, directions are requested by the driver and provided to the driver orally, typically using speech recognition and speech synthesis tools, as is known in the art. Alternatively or additionally the addresses can be requested through a different modality, such as a keyed entry to the wireless communicator, which can be sent to the server 106 through a text messaging service, such as a short message service. (SMS), or a packet data protocol, such as TCP / IP (Network Protocol Description Models), as described later in this document. Directions can also be provided to telephone 102 by these means or through a different modality, such as a visually sensitive map or written instructions. In such a case, interactive voice response (IVR) processor 104 will be bypassed.
According to one embodiment of the invention, the cellular network of which the cellular phone 102 is a part provides location determination functionality by supplying an output of location data to the phone 102 or the map server 106 via a path of adequate data. Alternatively or additionally, a location data output can be provided by a GPR receiver or other location device (not shown in this figure) mounted on the vehicle. A user can also supply location data via cell phone 102.
It is a particular feature of the present invention that the driving directions are provided in real time, allowing the driver of a vehicle to request and receive information from the map, preferably in the form of driving directions, while driving and without interrupting the journey. Novel procedures that allow such real-time address generation, along with the download and display of concomitant map data, are described in detail later in this document.
Figure 2A is a simplified pictorial illustration of a real-time map display and distribution system constructed and operational in accordance with another embodiment of the present invention. As seen in Figure 2A, the driver of a vehicle 200 communicates via a wireless communicator, such as a personal digital assistant (PDA) 202 that has cell phone functionality or a smart cell phone, with a server. of maps 206. Optionally, personal digital assistant (PDA) 202 communicates with server 206 through interactive voice response processor 204 or over the Internet. An output of location data is provided by a receiver of a GPS 208 or other location device in the vehicle and the location is automatically transmitted by personal digital assistant (PDA) 202 to server 206. Alternatively, a cellular network with which the personal digital assistant (PDA) 202 communicates may provide the location data output to the server 206, or the user may supply the location data via the PDA.
In the illustrated embodiment, the driver asks for current directions and a map showing a route to his workplace, considering current traffic conditions. In real time, preferably within four seconds or less, the driver receives the requested directions and the map showing the currently preferred route. Route selection is based on current traffic conditions, which are provided to map server 206 by traffic server 210. More globally, the map server can receive dynamic input information regarding road conditions. roads and cuts, construction, etc., from a number of different sources for use in determining preferred routes. Typically, the dynamic input information is provided as a stream of events from traffic server 210 and other information sources, with geocodes identifying the locations of the events. The map server 206 receives and classifies the information in order to generate addresses to clients such as the PDA 202. The map showing the preferred route (s) is then generated by the PDA on a display 211 by a client program running on the PDA.
In the illustrated embodiment, directions and maps are requested orally by the driver. Alternatively or additionally the addresses and the map can be requested through a different modality, such as a keyed entry to the wireless communicator, which can be transferred via an SMS or a packet data link. Directions and the map can similarly be provided through any suitable modality, such as a visually sensitive map associated with written instructions. In such cases, interactive voice response (IVR) processor 204 can be bypassed.
Figures 2B-2F are schematic representations of a display 211, showing maps displayed by the client program running on the PDA 202 in the course of a trip in a vehicle 200, in accordance with an embodiment of the present invention. Figure 2B shows a screen 212 displayed at the beginning of the trip. A circle 214 marks the starting point of the journey and an icon 216 shows the current position of vehicle 200. Due to
Due to the limitations in the accuracy of the GPS receiver 208, the PDA 202 preferably corrects the position coordinates provided by the receiver to show the true location of the vehicle 200 relative to the map displayed on the phone. Correction means placing the vehicle icon on the road on which the vehicle is actually traveling, based on the locations and characteristics of the roads on the map and the calculated trajectory of the vehicle's movement over time.
The route provided by the map server 206 is marked by visual highlight 232. A scale window 218 shows the scale of the current map. This scale is preferably determined based on the distance of the vehicle 200 from the next turn in the route itinerary. A compass arrow 226 shows the north direction. In the navigation mode of operation illustrated by Figures 2B-2E, the map displayed on screen 212 is oriented so that the heading of vehicle 200 is approximately aligned with the upward direction on the map.
Preferably, as described in greater detail later in this document, the map server 206 previously calculates the magnification factor and the orientation of the map segments to be delivered to the PDA 202 along the route of the vehicle 200's travel. Alternatively or additionally, the orientation and magnification of the map may be selected by the user of the PDA 202. The server then supplies the map data to the PDA 202, typically in vector form, with the appropriate angle of rotation for the expected direction of travel and with the appropriate level of detail for the expected magnification factor (or with an orientation and a few alternative magnification levels selected by the user). An anti-overlap process can also be applied to smooth out the lines that appear on the map, in order to avoid jagged edges and other image artifacts that may appear due to the low resolution of the client display. Client devices such as the PDA 202 are therefore capable of generating the maps quickly and efficiently, despite the generally low computing power and small memory size of such devices, since there is no need for have the client device perform substantial flip or zoom calculations on the image. Alternatively or additionally, particularly when using client devices with improved computing power, such as laptop computers, at least some of the turning and zooming operations can be performed by the client device.
Display 212 also includes a number of other navigation aids. For example, in the illustrated embodiment, a trip meter shows the relative distance that the vehicle 200 has traveled on the current route and a trip meter 222 shows the distance to the destination and the travel time that has passed. A navigation window 224 shows the next maneuver to be performed along the route and the distance to the intersection at which the maneuver will be required. The PDA 202 monitors this distance as the vehicle progresses and can use speech synthesis to provide audible instructions to the driver at predetermined distances or time intervals before the vehicle reaches each maneuvering location. The PDA is able to determine the appropriate time intervals by monitoring the location and speed of the vehicle.
A status window 228 displays status information, such as the strength of the GPS signal at the GPS receiver used by the PDA 202 and the status of the network connection between the PDA 202 and the map server 206. If the GPS signal is lost, the PDA still tries to extrapolate the position of the vehicle along the route for as long as is reasonable and display the icon 216 accordingly. Similarly, even when the network connection is lost, the PDA can still provide the user with instructions and display the map, based on the current position of the vehicle 200 and the map data that the PDA previously received from the server. 206. As long as there is a connection between the PDA and the server, the PDA continues to download map data, while downloading old data from its memory, so that the PDA can continue to display maps and navigation instructions continuously as long as possible in the case of a communication failure. The coordinates of the map data to be downloaded and the amount of the data of this type that can be requested are determined by the PDA 202 based on the position and speed of the vehicle 200 and the memory capacity of the PDA. .
A menu control 230 allows the user of the PDA 202 to access menu functions in order to set preferences and input information, such as destinations and route requests. These features are described in more detail later in this document.
Figure 2C illustrates a maneuver screen 240 and is displayed on display 211 as vehicle 200 enters an intersection where it has to make its next maneuver along the path provided by server 206. Screen 240 typically it is based on a special maneuver map of the intersection, which is prepared in advance by the server and downloaded to the PDA 202 in advance. The scale of the display 240 is scaled up to high magnification and roads entering and leaving the intersection are highlighted in contrast. Other details can be selected from the maneuver map to reduce visual confusion and distractions. A brighter arrow 242 indicates the direction of the maneuver the vehicle is required to perform. The arrow is preferably drawn by taking the actual sequence of line segments (known as a polyline) that represents the navigation route, trimming it to fit within the outer lines of the intersection, and then adding an arrowhead at its leading end. . The PDA 202 amplifies
ES 2 425 555 T3 automatically magnifies this view when the vehicle is within a certain extent of the intersection and reduces it again immediately after the maneuver has been completed. Typically, the PDA also uses speech synthesis to provide acoustic instructions before and during the time the vehicle is at the intersection.
Figure 2D illustrates another screen 250, which is displayed on display 211 after vehicle 200 has made the turn required by screen 240. The orientation of the map has been automatically rotated to correspond with the new direction of travel of the vehicle and the scale has been reduced to show both the current location of the vehicle and the intersection at which the next maneuver is to be performed. In other words, for each segment of the route, a different level of extension can be determined, based on the length of the segment, as well as other parameters supplied by the PDA 202 or the server 206. The icon 216 is generated by the PDA 202 locally and overlays on the map that the PDA generates based on the map data from the server 206.
Figure 2E illustrates a subsequent screen 260 that is displayed on display 211, following the next maneuver along the vehicle path. The direction of the map is rotated again. In this case, the road on which the vehicle is currently traveling does not follow a straight line (as previous sections of the route did), but instead comprises a curve. The curve is typically represented in the geographic database of the server 206 as a polyline, composed of a sequence of line segments of different lengths and orientations. Polyline is smoothed for display on the 260 screen, based on the magnification factor and resolution of the 211 display. The angle of rotation of the map on the screen 260 is typically determined by the server 206 based on the angle between the next steer point on the route and the previous steer point.
Figure 2F illustrates a mapping screen 270 that may be displayed on display 211, in place of the navigation screens depicted in Figures 2B-2E. This map view of the route can be selected by the user of the PDA 202 by invoking an appropriate menu item. In cartography mode, the user is able to select the map magnification, and optionally the view area and map orientation, using map controls 272. Unless directed by the user otherwise, the PDA 202 positions and scrolls the map so that the icon 216 representing the actual position of the vehicle 200 remains in the center of the screen.
Figure 3 is a simplified pictorial illustration of a real-time map display and distribution system constructed and operational in accordance with yet another embodiment of the present invention. As seen in this figure, a driver of a vehicle 300 communicates with a map server 306 on the Internet through a wireless communicator such as a personal digital assistant (PDA) that has the functionality of a cell phone, or a telephone smart phone 302. Optionally, such communication may involve an interactive voice response (IVR) processor 304. A location data output is provided by a GPS receiver 308 or other vehicle-mounted location device and the location is automatically transmitted by phone 302 to server 306. Alternatively, the cellular network of which the cellular phone is a part may provide the location data output to the server 306, or the user may provide the location data via the cellular telephone.
In the illustrated embodiment, while driving, both at the driver's initiative or not, the driver receives, in real time, the current driving directions and a map showing a route to his or her destination in view of the changing conditions of the vehicle. traffic, including proposed real-time changes to that route. Typically, the phone 302 automatically queries the server 306 periodically, to inquire about dynamic road conditions, such as traffic along or around the current route, and to receive possible route changes in light of dynamic conditions. For this purpose, it is convenient that the phone maintains a continuous connection with the server 306 over the cellular network (using a GPRS link), for example, so that it is not necessary to make a new call for each consultation. Alternatively, SMS messaging can be used between the phone and the server. Also alternatively, the server 306 can track the location of the vehicle 300 along its route and thereby can provide dynamic updates to the phone 302 automatically, without waiting for an inquiry from the customer.
As described earlier in this document, directions and the map are recommended to the driver, where graphic icons can be drawn on the map to indicate the recommended route, every time. Preferably directions and maps are provided to the driver within four seconds or less of each inquiry from telephone 302 and are displayed on a display screen of the telephone. Alternatively or additionally, addresses can be provided and updated orally. It is a particular feature of the present invention that driving directions and maps are provided in real time, allowing the driver of the vehicle to receive changes in directions and driving maps without delay.
Reference is now made to Figure 4, which is a simplified pictorial illustration of a real-time map display and distribution system constructed and operative in accordance with yet another embodiment of the present invention. In this case, a pedestrian communicates with a map server 406 on the Internet through a
ES 2 425 555 T3 wireless communicator 402, such as a personal digital assistant (PDA) having the functionality of a cell phone, or smart cell phone. The pedestrian asks for directions regarding the location of a point of interest (POI) of a particular type, in this case, a pharmacy, both through voice input to the 402 communicator and manually by keying it in, using a stylus to select or type the type of addresses requested.
The cellular network through which the communicator 402 communicates with the map server 406 may provide a location determination functionality, which supplies the coordinates of the pedestrian's location to the map server. Alternatively or additionally, a location data output may be provided by a GPS or other location device associated with or connected to the communicator. Also alternatively, the pedestrian can also supply the location data through the communicator.
Based on the location data, the map server 406 locates the closest POI of the selected type, or various POIs in the vicinity of the pedestrian's location. In the latter case, the user can select one of the points of interest through an input to the communicator 402. The server returns the location of the selected POI (for example, the pharmacy in this example), along with navigation instructions, which tell the pedestrian how to get to the POI. Typically, the server 406 also recommends a map to the communicator 402, showing the location of the point of interest and the present location of the pedestrian, with arrows pointing the way to the point of interest. The map in this case can also show footpaths to the pedestrian, as well as features such as bus and subway connections, unlike the driving maps shown in the previous embodiments. Also note that while driving maps and route calculations take into account driving restrictions, such as one-way streets, there is no need for pedestrian maps to do so.
Figure 5 is a simplified pictorial illustration of a real-time map display and distribution system constructed and operational in accordance with a further embodiment of the present invention. In this embodiment, the driver of a vehicle 500 communicates via cellular telephone 502 with a mapping server, as shown in the previous figures. As in the embodiment of figure 4, the driver asks directions to a point of interest, in this case a specific car park and wants to be directed to the closest point of interest of this type. The mapping server selects the closest parking lot from its database (taking into account traffic restrictions, too, such as one-way streets) and returns the driving directions to telephone 502. A map showing the location of the specified POI can also be recommended to the phone's display.
Figure 6 is a simplified pictorial illustration of a real-time map display and distribution system constructed and operational in accordance with yet a further embodiment of the present invention. In this embodiment, a mobile service provider, such as a taxi company, uses a website 606 to track the locations of its taxis. Taxi locations are displayed on a 608 console in the taxi company's fleet office. A driver in a taxi 600 is depicted in the figure, with a mobile communicator 602 for exchanging location, address, and map data with the website 606 over a cellular communication network. An interactive voice response (IVR) processor 604 may be used to allow the driver to interact with the website 606 via hands-free voice communications. The website 606 receives the current location of the taxi 600 and the other taxis in the fleet, based on either a GPS in the taxi or location services - cellular network location and transfers the information to the 608 console .
When a passenger calls the taxi company to order a taxi, the dispatcher uses the location formation provided by console 608 to locate and select a taxi, such as taxi 600. Typically, the closest available taxi to the location of the passenger. Selection can be made automatically by console 608, based on passenger location, taxi locations, and other factors, or can be entered manually by the dispatcher. Console 608 then sends a message over the cellular network to communicator 602, instructing the taxi driver 600 to make a pickup at a certain location. The communicator 602 may request navigation instructions from the current location of the taxi 600 to the pickup location and how to get there. A mapping server at Web site 606 generates and sends the instructions. A map showing the passenger's location and the preferred route to the location can also be viewed by the communicator. Dynamic information on traffic and other road conditions can be taken into account, as described earlier in this document, in selecting the route to be taken to the passenger's location, as well as the route to transport the vehicle. passenger to your destination.
Although this embodiment shows the integration of finding location and navigation in a particular application - managing a taxi fleet - it will be understood that the principles of the present invention can similarly be applied to other fleet management applications as well. the provision of other types of mobile services.
Figure 7 is a simplified functional block diagram of a real-time map display and distribution system constructed and operational in accordance with an embodiment of the present invention. As seen in FIG. 7, a client-server type arrangement is provided, in which a dynamic mapping server 700 communicates with a dynamic map client 702. Server 700 typically comprises a general type computer, or group of computers, with appropriate software to carry out the functions described below in
ES 2 425 555 T3 this document. This software may be provided to the server in electronic form, over a network, for example, or alternatively it may be provided on a tangible medium, such as a CD-ROM.
Server 700 comprises a dynamic content storage subsystem 720, which receives dynamic content from dynamic content providers 722. Examples of dynamic content providers include providers of real-time traffic data, such as Traffic Master Ltd. from United Kingdom; restaurant reports, such as Zagat; and movie programming services such as UK Time Out. Dynamic content typically changes in real time. For example, dynamic traffic data provides information on traffic jams at specific intersections or on specific roads as they occur. Movie and restaurant data is current but clearly not changing as fast as traffic data does. Dynamic traffic data is typically supplied by providers 722 via an agreed protocol, such as the Alert C protocol, commercially available from Traffic Master Ltd. in the UK. The restaurant and movie data may be provided in a conventional XML format or in any other suitable format.
Data on static geographic information systems (GIS), such as map data, which are generally not dynamic, are supplied to a map management processor 712 from a GIS 710 database, provided by a GIS data provider. , such as Navigation Technologies Inc. (Chicago, Illinois) or Tele Atlas North America (Menlo Park, California). The GIS data is typically supplied in a relational database format to the map management processor 712, which converts the data to a binary format used by the server 700 and stores the converted data in a binary data storage subsystem. 714. Subsystems 714 and 720 typically comprise high-capacity hard disk drives for storing the static and dynamic data, respectively.
The map management processor 712 is typically operative, among other things, to receive GIS data in various formats from different GIS data providers and to process the data into a uniform format for storage by the storage subsystem 714. Typically, the GIS data stored in the GIS 710 database is highly detailed and the map management processor is operational to generalize this data so that bandwidth requirements for transmission of the data are reduced.
Client devices, such as cell phones, PDAs, and other communicators depicted in the preceding figures, use client 702 to communicate with server 700 and provide information to users. Client 702 typically comprises an application written in the Java ™ language, but may alternatively comprise other suitable client programs, such as ActiveX ™ or C Sharp ™ clients and can run on substantially any stationary or portable computer or on any suitable communicator. Typically, when a client device connects to the server 700 for the first time, the application (or other client program) is downloaded to the client device and begins to function. The client program is preferably stored in the memory of the client device, so that the next time the client device connects to the server, it is not necessary to download the program again.
When the client 702 initiates a new connection with the server 700, the version number of the client program is checked against the latest version of the program contained on the server. If there is a new version of the client program on the server, it is automatically downloaded to the client device and replaces the oldest version contained in the client memory. Typically, only the classes or other resources that have been changed in the new version need to be downloaded, rather than the entire new version of the client software. When the connection from the client to the server is terminated, the map data that was downloaded to the client can be erased from the client memory, but the templates that generate the maps, as described later in this document, are preferably stored in memory. client to reuse them during subsequent connections.
The client 702 typically receives the location data from a device that provides locations 704, such as a GPS receiver (as shown in the previous figures) or any other service that provides location coordinates of the device in real time. Examples of such devices are cellular telephone functionalities that indicate the location of a telephone by triangulation and voice or data-sensitive services that provide location coordinates in response to information provided by the user. Such user-supplied information can be spoken or written in any conventional manner.
Typically, upon startup, dynamic map client 702 initiates an authentication hello with an authentication functionality 730 from server 700. Following authentication, client 702 may submit one or more of the following requests to the server 700:
- map requests
- search requests
ES 2 425 555 T3
- route requests
- topology requests (road data)
- requests for auxiliary information such as templates.
In a typical interaction, client 702 requests and then retrieves the appropriate template from server 700. The client can then perform a search, for a city, street, address, or point of interest, for example. (The search can use a fuzzy comparison of the client's query string, as described later in this document, so that the server returns the search results while the user is entering the string on the client device.) When the searched destination is found, the client 702 may request the geocode of the destination and the vector data required to display the area of the destination or a route to the destination.
Client requests and server responses are typically transmitted over a wireless network, such as a cellular network, with which the client device communicates. Alternatively or additionally, the client device can communicate with the server over a wireless network, such as the Internet. Requests and responses are typically transferred using communication protocols known in the art, such as TCP / IP or HTTP.
A request processor 740 handles client requests. For this purpose, processor 740 accesses GIS data from binary data storage subsystem 714, as well as dynamic information from dynamic content storage subsystem 720. Processor 740 calculates and sends a response to client 702 in real time, typically within 4 seconds after receiving the request and preferably within 2 seconds or even 1 second of the request. The response comprises vector and textual data, including information such as navigational instructions, route poly-lines, and traffic conditions. This data is typically used by the client 702 to provide instructions to the user and generate an image of the map, using a template or templates that the client has previously received and is stored in the associated memory. Additionally or alternatively, the processor 740 may generate and download images to the client 702, such as images in a bitmap.
Details of the data structures, computer programs (server and client), and protocols used by server 700 and client 702 are depicted in the figures that follow.
FIG. 8A is a block diagram schematically showing details of the server 700, according to an embodiment of the present invention. For the sake of conceptual clarity, the server is represented in this case as comprising certain functional blocks. This functional structure, however, does not necessarily correspond to any physical separation of the functions represented in the figure. Instead, the functional blocks represented in the figure correspond to software modules, which can operate on the same processor or on separate processors.
The request processor 740 comprises several components:
- A mapping engine 802 receives and serves requests for maps from and on behalf of client 702. In other words, in response to a request to provide a map of a certain geographic area, with a certain magnification level and orientation and certain types For features, the engine 802 retrieves the required information from the storage subsystems 714 and 720 and then filters and formats the map data in a manner suitable for provision to the customer. The map request may be generated directly by the user of the client device, but more commonly it is automatically generated by the client 702 as subordinate to a search or route request.
- A search engine 804 receives and serves requests from the client to locate a certain geographical feature, such as a city, a street, a building address or a point of interest. At the time of the location of the desired feature, the search engine provides the coordinates of the feature to the customer 702. The customer may then request a map showing the location of the feature or navigation instructions to the location.
- A route engine 806 receives and serves requests from the client to provide navigation instructions from a given starting point (typically the client's current location) to a destination, with possible intermediate stopping points along the route.
Details of the map generation, search and route generation processes are described later in this document.
As noted above, the server 700 may use data from third party services 810 in serving customer requests. For example, search engine 804 can access a database of codes
ES 2 425 555 T3 geographical third parties 812 in order to determine the graphic codes (map coordinates) of cities, streets or other specific geographical characteristics. Route engine 806 may use a third-party routing server 814 as an alternative or auxiliary for performing its own route calculations. Third-party services 810 may also include dynamic content providers 722, as depicted in Figure 7.
The request processor 740 generates map data and routing addresses in the form of vector data and text labels. A data compression and decompression module 820 converts the output of processor 740 into compressed binary form, to minimize the bandwidth consumed by transmitting data from server 700 to client 702. An encryption and decryption module 822 encrypts the data for transmission to the client 702, for the purpose of data security. Request messages from client 702 to server 700 are similarly compressed and encrypted and are decrypted and decompressed by modules 822 and 820. A networking module 824 assembles the data in packets for transmission to the client 702, typically TCP / IP packets, and manages the required protocol functions of networking, as is known in the art.
FIG. 8B is a block diagram schematically showing details of client 702, according to an embodiment of the present invention. The client functional blocks 702 do not necessarily correspond to any physical division of the components within the client device and may simply be implanted as software modules in a program running on a microprocessor on the client device. The functions of the mapping and navigation core of the client 702 are carried out by a mapping and navigation manager 850, which submits requests to the server 700 and receives responses from the server through a communication interface 852. This interface performs the functions networking, encryption / decryption, and compression / decompression that parallel the comparable server functions described earlier in this document. The manager 850 receives vector map data from the server 700, along with the text data for the map labels, and formats the vector data and text for generation by an imaging engine 854. The data is formatted in according to templates, as described later in this document, which determine the visual properties of the map features. The templates are also downloaded from the server 700 and are maintained by the manager 850 in a memory 855. The imaging engine 854 generates the maps on a display 856.
The manager 850 controls a user interface 858, which interacts with the client user 702 through a display 856 and through user-operated input devices (not shown in this figure), such as a keyboard or screen. tactile. The user interface can also generate audio outputs or receive voice inputs from the user.
The manager 850 periodically receives the coordinates of the client device's location from a device that provides locations 860, such as a GPS receiver. An 862 map buyer processes and corrects the location coordinates in order to correctly record the customer's location relative to a road on the map displayed on the 856 display. The map comparer corrects inaccuracies in the received coordinates to from device 860. For this purpose, the map comparer compares the current coordinates of the location with readings taken in the recent past and thereby estimates the heading and speed of the vehicle in which the client device is positioned. This information is compared with the topology of the roads in the vicinity of the client device, along which the vehicle may be traveling, in order to assign a probability score to each possible route the vehicle may have taken. The map comparator selects the most likely course and then corrects the coordinates from the current location to the closest location on the selected course.
The manager 850 receives the corrected coordinates from the map comparer 862. It typically instructs the imaging engine 854 to overlay an icon representing the vehicle (such as icon 216), at the corresponding location on the map that is currently represented on display 856. Since the location and icon are generated locally, within the client 702, the map can be updated efficiently, without any need to refresh the entire map. Updating of the location and map coordinates can continue in this manner even when communications with the server 700 are lost. Additionally, the manager 850 may use the updated location information provided by the map comparer 862 to detect navigation errors by the vehicle driver and generate driving instructions to get the vehicle back on track.
FIG. 9 is a block diagram schematically illustrating data structures used by server 700 in preparing and distributing map data to client 702, in accordance with one embodiment of the present invention. Map data 900 is arranged in layers 912, each layer corresponding to a different type of feature on the map. Layers define the shapes and locations of the features, in vector form, and typically include textual labels, too. One or more of the layers 912 may also comprise dynamic data, such as traffic conditions.
The actual appearance of map features on 702 client-generated maps is defined by the
ES 2 425 555 T3 display data 910. The display data comprises a template 914 that corresponds to each layer 912. The templates define the visual properties associated with the characteristics of the map in each layer, such as colors, line thicknesses , and whether or not a label is displayed for each characteristic. The visual properties defined by the templates depend on the magnification level of the map to be viewed by the client 702, with different templates provided for different magnification levels. Additional aspects of the 914 templates are described later in this document.
Typically, a server 700 maintains multiple templates 914 for each layer 912 and downloads the appropriate templates to client 702 depending on the capabilities of the client's equipment and display conditions. The collection of templates used to generate the multiple layers on a given client device can be treated as a single multiple template. Since the same templates are used in displaying maps of different geographic areas, the client 702 can store the templates in its local memory 855, so that it is necessary to download the templates to the client only once to view multiple different maps. Each template is optimized for different viewer types and conditions on the 702 client, for example:
- Different templates can be defined for different types of client displays, such as color or monochrome displays and different display resolutions. Thus, a cell phone with a small monochrome display will receive one set of templates, while a PDA or laptop with a large color display will receive another.
- Different templates can be used for day and night viewing on the same client device, in order to improve the visibility of the maps when they appear on the display screen in the vehicle and to facilitate navigation.
FIG. 10A is a block diagram schematically showing additional details of a data structure 1000 used in preparing and storing a map 1002 on the server 700, in accordance with an embodiment of the present invention. Map 1002 comprises multiple layers 1004, as described earlier herein, each layer containing data regarding image characteristics in a particular category. Each category can include characteristics of different types. For example, a road layer may comprise sublayers for major highways, minor highways, major roads, local streets, roads, and so on. (Therefore, the term roads as used in the context of the present patent application and in the claims includes not only roads for vehicles, but also any type of road that can be used by non-motorized or even non-motorized traffic. vehicular). Each layer 1004 typically comprises multiple sublayers 1010, corresponding to the different magnification levels at which the objects on the layer are to be displayed. The magnification level of each sublayer determines the level of detail to be used in the representation of the features in the sublayer. By extracting unnecessary details in advance, the volume of data that must be downloaded to client 702 to display a certain map at a certain magnification level is reduced.
Each sublayer 1010 comprises multiple objects 1014 that fall within the category of the corresponding layer. Each object 1014 is identified by geographic location coordinates, which are typically provided in a hierarchical index in R-Tree 1012, which divides the two-dimensional geographic space into a set of hierarchically nested (and possibly overlapping) boxes, such as known in the art. The R-Tree is described for example in the document The R * -Tree: An Efficient and Robust Access Method for Points and Rectangles. ACM SIGMOD International on Data Management (1990), pages 322331. Each object also comprises descriptive data 1016, indicating the type of characteristic it represents and a shape 1018. The shape of an object is typically either a point (for points of interest), a polyline (that is, a sequence of connected line segments, for features such as roads), or a polygon.
The visual properties of layers 1004 are defined by templates 1006. Multiple templates are provided for each layer, corresponding to the number of different display types and display modes (such as day / night) that can be used in the display of maps on different client devices, as described earlier in this document. The 1006 templates define different properties for different types of 1020 objects. Additionally, the visual properties 1022 that are defined for each type of object may vary depending on the magnification level (that is, the scale) of the map to be displayed. Therefore, for each type of object, the template provides multiple sets of visual properties, each corresponding to a different magnification level.
As an example, Table I later in this document lists a part of a template for the category roads, which defines the visual properties on nine different types of roads at seventeen different magnification levels. The template is written in XML and is largely self explanatory. The XML tags for each type of object and magnification level indicate whether or not the object will be displayed in the maps represented at this magnification level (depending on the visible tag), along with width, color, textual labeling and others.
ES 2 425 555 T3 characteristics. The order tag indicates the Z order, this is how different the objects are to be overlapped when they overlap in an image that is generated on the client device.
TABLE I - LISTING OF A SAMPLE TEMPLATE
- <TEMPLATE visible = yes no. Object Types = 9>
- <OBJECT type = main highway name = main highway order = 7 visible = yes
Default state = connected has URL = does not have Angle = does not have Vis Parameter = does not have Col Parameter = does not allow Backspace = no>
<EXPANSION id = 1 visible = is not Form = is not Image = does not have Label = does not have Pop-up information = does not have Description = no />
<EXPANSION id = 2 visible = is not Form = is not Image = does not have Label = does not have Pop-up information = does not have Description = no />
<EXPANSION id = 3 visible = is not Form = is not Image = does not have Label = does not have Pop-up information = does not have Description = no />
- <ENLARGEMENT id = 4 visible = yes it is Form = yes it is Image = does not have Label = does not have Pop-up information = does not have Description = no>
<SHAPE width = 1 color = F35A56 Border width = 1 Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 5 visible = yes it is Form = yes it is Image = does not have Label = does not have Pop-up information = does not have Description = no>
<SHAPE width = 1 color = F35A56 Border width = 1
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 6 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 1 color = F35A56 Border width = 1
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 7 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 2 color = F35A56 Border width = 1
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 8 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 2 color = F35A56 Border width = 1
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 9 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 2 color = F35A56 Border width = 1
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 10 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 4 color = F37773 Border width = 1
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
ES 2 425 555 T3
- <ENLARGEMENT id = 11 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no> <SHAPE width = 4 color = F37773 Border width = 1
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 12 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 4 color = F37773 Border width = 1
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 13 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no> <SHAPE width = 6 color = F37773 Border width = 2
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 14 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 6 color = F37773 Border width = 2
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 15 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no> <SHAPE width = 8 color = F37773 Border width = 2
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 16 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 11 color = F37773 Border width = 2
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 17 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 11 color = F37773 Border width = 2
Border color = F14B43 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
</OBJECT>
- <OBJECT type = search tour name = search tour order = 6 visible = yes
Default state = connected has URL = does not have Angle = does not have Vis Parameter = does not have Col Parameter = does not allow Backspace = no>
<EXPANSION id = 1 visible = is not Form = is not Image = does not have Label = does not have Pop-up information = does not have Description = no />
- <ENLARGEMENT id = 6 visible = yes it is Form = yes it is Image = does not have Label = does not have Pop-up information = does not have Description = no>
<SHAPE width = 1 color = B6B6C7 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 7 visible = yes it is Form = yes it is Image = does not have Label = does not have Information
ES 2 425 555 T3 pop-up = does not have Description = no>
<SHAPE width = 1 color = B6BOCC Border color = 9D86C1 is formed into distinguishable images = not animated = no />
</ ENLARGEMENT>
- <AMPLIFICATION id = 17 visible = yes it is Form = yes it is Image = does not have Label = does not have Pop-up information = does not have Description = no>
<SHAPE width = 11 color = B19ECD Border width = 1
Border color = 9D86C1 is formed in distinguishable images = not animated = not />
</ ENLARGEMENT>
</OBJECT>
- <OBJECT type = main road name = main road order = 5 visible = yes
Default state = connected has URL = does not have Angle = does not have Vis Parameter = does not have Col Parameter = does not allow Backspace = no>
<EXPANSION id = 1 visible = is not Form = is not Image = does not have Label = does not have Pop-up information = does not have Description = no />
- <ENLARGEMENT id = 9 visible = yes it is Form = yes it is Image = does not have Label = does not have Pop-up information = does not have Description = no>
<SHAPE width = 2 color = B47A10 is formed in distinguishable images = not animated = no />
</ ENLARGEMENT>
- <ENLARGEMENT id = 10 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no>
<SHAPE width = 1 color = F0E12B Border width = 1
Border color = B47A10 is formed in distinguishable images = not animated = not />
</ ENLARGEMENT>
- <ENLARGEMENT id = 17 visible = yes it is Form = yes it is Image = does not have Label = no
Has Popup Information = does not have Description = no> <SHAPE width = 10 color = F4E264 Border width = 1
Border color = DCC210 is made up of distinguishable images = not animated = no />
</ ENLARGEMENT>
</OBJECT>
- <OBJECT type = street name = toll_street order = 3 visible = yes
Default state = connected has URL = does not have Angle = does not have Vis Parameter = does not have Col Parameter = does not allow Backspace = no>
- <OBJECT type = toll_street name = street order = 2 visible = yes
Default state = connected has URL = does not have Angle = does not have Vis Parameter = does not have Col Parameter = does not allow Backspace = no>
- <OBJECT type = pedestrian_travel name = pedestrian_travel order = 1 visible = yes
Default state = connected has URL = does not have Angle = does not have Vis Parameter = does not have Col Parameter = does not allow Backspace = no>
ES 2 425 555 T3
- <OBJECT type = shuttle order = 0 visible = yes Status by default = connected has URL = does not have Angle = does not have Parameter Vis = does not have Parameter Col = does not allow
Backspace = no>
</ TEMPLATE>
FIG. 10B is a schematic representation of a computer screen 1040, which is used in a template editor for creating templates 1006, in accordance with one embodiment of the present invention. The template editor typically operates on a terminal or workstation (not shown) that is linked to the server 700 and is used by a server operator in setting the attributes of the different templates. On the screen depicted in Figure 10B, each type of road in the template streets layer is represented by a corresponding row 1042. Each column 1044 corresponds to a different magnification level. The 1046 entries in each row indicate whether the corresponding type of object will be visible at each of the different magnification levels and, if so, what color it will be. The operator uses this screen to change the colors and visibility properties of the different road types. Other screens (not shown) allow the operator to change properties such as line width, border width, and labeling, for example. Similar screens are available for other categories of objects.
FIG. 11 is a block diagram schematically illustrating a data structure 1100 used by a search engine 804 in serving customer search requests, in accordance with an embodiment of the present invention. At the highest level, data structure 1100 comprises a region / city entry 1102 for each region or city in the GIS database 710. Each region or city is represented by its name and by a bounding box, which provides the coordinates of the region or city limits. A region can contain region minor regions (such as municipalities or cities within a state or country), each of which is represented by its own 1102 entry.
At the next level down in the hierarchy, cities and regions contain roads, which are represented by 1104 street entries. Each street is made up of one or more segments, which are represented by 1108 segment entries. Each entry Segment 1104 has a street name and a bounding box that contains all street segments. In addition, each street is indexed to crossroads entries 1106, which contain the names and coordinates of all the other streets that cross it.
The search data structure 1100 may also contain other types of searchable data, such as postal code entries 1110. Note that the POI information may be stored in map layers, so that both mechanisms can be accessed. display and search for maps. Therefore, points of interest can be searched by city, or within a previously defined radius of a certain address or location, or within a certain bounding box. The search for points of interest is then typically performed using the R-Tree index.
FIG. 12 is a block diagram schematically illustrating a data structure 1200 used by routing engine 806 in response to customer routing requests, in accordance with one embodiment of the present invention. For this purpose, the locations in the GIS 710 database are represented as nodes on a graph. The road segments form the edges of the graph that connect the nodes. Thus, each node entry 1202 contains the location of the node and indicates the entries of the elements 1204 that connect the nodes. Each segment entry 1204 contains segment properties 1206, such as limitations on vehicle types and weights that must be taken into account in generating navigation instructions. Each segment entry also contains pointers to any applicable turn restriction entry 1210, which indicates for each segment the other segments within which a vehicle is allowed (or not) to turn from the segment.
FIG. 13 is a flow chart schematically illustrating a procedure used by mapping engine 802 in generating a map for download to client 702, in accordance with one embodiment of the present invention. The mapping engine begins this process by reading the parameters from the client, in a parameter input phase 1302. The client can provide these parameters in a map request message that it sends to the server 700, or the server can read the parameters from its own records. Parameters typically include:
- Template type, which corresponds to the properties of the client viewer, such as screen size and color palette and preferences, such as day or night vision.
- The size and orientation angle at which the map is to be displayed (as illustrated in Figures 2B-2F, for example).
- The location of the map.
ES 2 425 555 T3
- Object type visibility parameters, which indicate the types of objects to be included in the map (for example, what types of POIs, if any) based on the selections made by the client's user 702 or in default settings.
The cartography map 802 determines the location and size of the map in corresponding coordinates and a magnification level within its own data structure of the map 1000, in a phase of determining the coordinates 1304. As indicated earlier in this document , the data structure of the map is pre-calculated for particular levels of magnification. The mapping engine chooses the magnification level that is appropriate for the map size determined in step 1302. Using the coordinates and the map magnification, the mapping engine calculates a bounding box containing the area of the map to be mapped. visualize, in a calculation phase of the box 1306. The border box determines which are the objects that are going to be included in the map that is being downloaded to the client. The mapping engine also creates a dynamic template by combining the appropriate static template 1006 with the variable visibility information, in a template creation phase 1308. The variable visibility information typically includes, for example, the visibility parameters of the object type that were entered in step 1302 and the visibility properties of the different object types as indicated by the selected static template. The dynamic template is used to filter unnecessary objects out of the map data to be transmitted to the client 702 so that only the features that are actually to be viewed by the client are included in the transmitted data.
If the map to be displayed on the client device is to be rotated (as depicted in the examples of Figures 2B-2E) the mapping engine 802 can rotate the map coordinates in advance to the desired orientation. As noted earlier in this document, pre-flipping the map reduces the computational load assigned to the client devices at the low end. Alternatively, if the map rotation is performed by the client device, the previous rotation phases can be eliminated.
To rotate the map, the mapping engine calculates a coverage bounding box for the rotated map, in a rotation phase of box 1310. In other words, the original bounding box calculated in phase 1306 is rotated to the map angle that is to be displayed (for example, 45 ° northeast). A larger bounding box is calculated, oriented straight along the Cartesian axes of the GIS data and containing the original bounding box. This larger bounding box, referred to as the coverage bounding box, is used in clipping the map data to be transferred to client 702, in a rotated clipping phase 1312. Details of the clipping process are described later in this document. The data is then clipped or rotated to the original bounding box angle, in a data rotation phase 1314. In this phase, the coordinates of the vectors of the objects to be included in the map are rotated by an angle equal to and opposite to the angle of rotation of the original bounding box (so that the axis of true north will be inclined 45 ° to the left in the example shown earlier in this document). The coordinates of the objects on the map in the original GIS reference frame are thereby transformed into the rotated reference frame of the 856 client viewer.
The mapping engine 802 then clips the map data to the bounding box size calculated in step 1306, in a clipping step 1316. In the case of rotated data calculated in step 1314, the coverage bounding box is cropped to the size of the original bounding box at the rotated coordinates. Details of phase 1316 are depicted in Figures 14A and 14B, later in this document. The coordinates of objects that remain in the map data after phase 1316 are scaled from the original map coordinates (such as the GIS latitude and longitude coordinates) to pixel coordinates, which correspond to the pixels in the screen of the client device, in a scaling phase 1318. The mapping author simplifies the data, to fit the objects to be transmitted to the parameters and limitations of the client viewer, in a data generalization phase 1320. The generalization process extracts redundant objects and reduces the complexity of the others, while maintaining the representative integrity of the area represented on the map. Map generalization procedures are described, for example, in a document titled Automating Map Generalization, published by the Environmental Systems Research Institute (ESRI, Redlands California, 1996).
In addition to generating the vector map data, as described earlier in this document, the mapping engine 802 also prepares textual labels to be placed on the map by the client 702 at appropriate locations. Labels include street labels, which are rotated to appear along the appropriate street lines, as well as labels for polygon objects (such as cities, bodies of water, and parks) and points of interest, which they generally appear on the map in landscape orientation. The map engine decides which of the map features to label based on the applicable templates and then dynamically generates the map labels in their optimal placement. For example, polygon object labels can be offset within the polygon, street labels can be offset along the street polyline, and POI labels can be moved around the point of interest. . Label overlap is resolved by moving the labels or removing the low priority labels if there is insufficient space to display them on the map.
The map data is now ready to be transmitted to client 702, in a map completion phase at 1322. As noted earlier in this document, the map is transmitted in the form of map data.
ES 2 425 555 T3 vectors, representing points, poly-lines and polygons, in the frame of reference of the map to be generated in the client device, generalized and simplified to extract all unnecessary details.
Figures 14A and 14B are flow charts schematically illustrating a method for clipping data from the map, as performed in the aforementioned step 1316, in accordance with an embodiment of the present invention. The mapping engine 802 receives input parameters for use in clipping the map, in a parameter input phase 1402. The parameters include the area of the bounding box, the magnification level of the map and the template that will be used to display the map on the client device. The clipping procedure is applied to the map data in each of the layers and 1004 to be included in the map, based on the indices of the R-Tree 1012.
For each layer 1004, the mapping engine finds a sublayer 1010 that is appropriate for the specified magnification level, in a selection phase of sublayer 1410. The mapping engine finds the root of the R-Tree of the objects in the sublayer selected in a root clipping stage 1412. It then proceeds up the branches of the R-Tree, and clips all the shapes in the sublayer according to the bounding box, in a shape clipping stage 1420. The action taken in phase 1420 depends on the relationship of the bounding box to the current branches, as determined in a contouring phase 1422. If the branch is entirely out of the bounding box, the mapping engine ignores the branch and the skips the layer output in a branch removal phase 1424. If the branch is entirely inside the bounding box, the mapping engine collects all the shapes associated with this branch and all the minor branches, in a branch collection phase 1426, as long as the template indicates that these shapes they have to be visible on the 702 client-generated map. Non-visible shapes are ignored.
When a branch overlaps the bounding box boundary, the corresponding object shape is cut to size so that only those parts of the objects in the current sublayer that are inside the bounding box are included in the map data output, in a cut-to-size phase 1428. The minor branches of the branch that overlap are similarly clipped, continuing recurrently up the R-Tree to the highest leaves that will be visible on the map, in a phase of minor clippings 1430. The visible forms of the branch and its minor branches are collected for the output, in a collection phase of the forms 1432.
All shapes that remain inside the bounding box after clipping in phase 1420 are collected to form the map output data for the current layer, in an output phase of layer 1434. A similar procedure applies to remaining map layers, until all layers have been completed. The collection of all clipped data layers is then ready for output, in a clipped data output stage 1440.
Reference is now made to Figures 15A and 15B, which schematically illustrate a method by which search engine 804 responds to search requests from client 702, in accordance with one embodiment of the present invention. Figure 15A is a flow chart showing the procedure used to find a city name, while Figure 15B represents a user interface screen 1550 displayed by the client 702 for use in finding a street name. . It will be understood that the procedures described in this document are equally applicable to the search not only for names of streets and cities, but also for other geographic characteristics, such as crossroads, geographic codes and points of interest.
To initiate the search, a user of the client device enters a city name string and selects search preferences, which are downloaded from the client 702 to the server 700 in an entry phase of the search 1502. Typically, after the user has entered the first few letters of the city name, the search engine may begin searching its region / city 1102 entries for names that match the search mask made up of these letters. In this way, as described later in this document, the search engine can begin to return search results to the user without waiting for the full name of the city to be typed. (Typically, the client 702 waits to send the input of the input string to the server 700 until the user has stopped entering characters for a certain period of time, generally less than one second, in order to avoid disturbing the process of user data entry). To control this accelerated search process, the client 702 can use search parameters that include the maximum number of search results to be submitted by the search engine one at a time (and what to do if the number of matches found exceeds maximum) and whether to use an approximate string comparison in the search. Some or all of these parameters can be set by the user.
Search engine 804 first checks its database for a city name that is complete, the exact match to the search mask, in an integer checking phase 1504. The search is typically case insensitive. If an exact, complete match is found, the search engine reports that a matching individual city name has been found, in a 1508 complete match output phase.
ES 2 425 555 T3
Assuming a complete match is not found, the search engine checks to determine whether an exact match or a fuzzy match has to be made when searching your records, in a 1510 metric verification phase. If a fuzzy match flag is reset, the search engine searches its records for names that contain all the characters in the mask string in the appropriate sequence, in an exact match phase 1512. Otherwise, if a fuzzy match flag, the search engine performs the search in a way that allows for keyboard errors, in a fuzzy check phase 1514. In fuzzy checking mode, the search engine finds both names that exactly match the mask string and names that match the search string within a predetermined error limit. Typically, the error limit allows a bad character. The search order can be chosen to favor replacement characters that are frequently confused, such as the replacement of different vowels.
Search engine 804 reviews the search results found in step 1512 or 1514 to find out if the total number of search results is less than or equal to the maximum number of results specified in step 1502, in a verification phase of the length of the list 1516. If the number of results is within the maximum limit, the complete list of search results is output to the client, in an output phase of the complete list 1518. Otherwise, the search engine checks the send_ if _too many flag (as was set in step 1502), in a 1520 results distribution phase. If this flag is reset, the search engine does not return results, in an empty list return phase 1522. In this phase, the user of the client device can type one or more additional characters, to narrow the scope of the search, and the search process will resume at step 1502 using the new mask string.
On the other hand, if the search engine finds in phase 1520 that the send_ if _too many flag is set, it simply truncates the list of results it has found to the specified limit, in a list truncation phase 1524. Various criteria can be used to prioritize the results, so that the city names at the top of the list are those with a relatively higher probability of being the correct, real name that the user is looking for. (For example, names that exactly match the mask string can be placed before names that only roughly match). The truncated list is output to the client device, in a return phase of the truncated list in 1526. Note that following any of the phases 1518 and 1526, the user of the client device can continue entering additional characters, which will prompt the engine search to resume the search with the new mask string in step 1502.
Figure 15B illustrates the use of fuzzy matching in the context of street name search. The type of search to be performed is invoked by the user by selecting a button of the search type 1552. The user in this example is searching for streets in the city of Tel Aviv-Yafo and has typed in the name Hado. .. in a window typed 1554. The user may select an input button 1555, causing the client 702 to send this string to the server 700 and thereby initiate the search. Alternatively, client 702 may transmit the string to the server automatically, typically after the user has typed a certain number of letters or a certain amount of time has passed since typing began.
In this example, there are no streets that exactly match the string that the user entered. The search engine returns names that are an approximate match, for display in a 1556 results window on the client device. The user can select one of these names or alternatively can correct the entry in the window to 1554 and continue the search. At the time of selection of one of the street names, the user can use function buttons 1558 to ask the server 700 navigation directions to the selected street or provide a map of the street area. In requesting navigation directions, the user can select navigation type buttons 1560 to determine whether the navigation directions are to be generated according to the fastest, shortest or simplest route to the destination.
Reference is now made to Figures 16 and 17, which schematically illustrate a method for determining and displaying a route using a server 700 and a client 702, in accordance with an embodiment of the present invention. Figure 16 is a flow chart showing the procedure used by routing engine 806 in response to route requests submitted by client 702. The route request specifies various input data, in a data input phase 1602, which is required by the routing engine in order to calculate the route. These data include:
- Customer home location, provided by manual entry or automatically, by GPS, for example.
- Destiny.
- Any intermediate location to be passed along the route.
- Choice of the type of route (the shortest, the fastest or the simplest).
ES 2 425 555 T3
- Type of transport (car, truck, bicycle, pedestrian), which determines the effect that transport and turn restrictions may have on the route.
- Types of road to avoid (for example, toll roads, or routes considered to be unsafe).
- Level of detail of the verbal instructions (which can be high, medium, low or none).
The routing engine 806 converts the start and destination locations, as well as any intermediate locations, to coordinates in the reference frame of the map data 1000, in a phase of solving the coordinates 1604. The routing engine uses these coordinates in the construction of the route, in a construction phase of route 606. Substantially any automatic routing algorithm known in the art can be used for this purpose, such as the A * algorithm. Algorithms of this type are described, for example, by Cherkassky et al in Shortest Path Algorithms: Theory and Experimental Evaluation, Technical Report 93-1480, Department of Informatics, Stanford University ( Stanford, California, 1993). The route takes into account the preferences specified in phase 1602.
FIG. 17 is a graph that schematically illustrates a route 1730 generated by the routing engine 806, in accordance with one embodiment of the present invention. (This figure also shows aspects of a route corridor map for Route 1730, as described later in this document with reference to Figure 18). Route 1730 is in the form of a polyline, comprising a sequence of segments of route 1732, labeled RS1, RS2, ..., RS6, which connect nodes 1634 along the route, labeled M1, M2 , M3. Nodes 1634 typically correspond to road intersections. Route 1730 may also comprise a street crossing identification 1636 that intersects the designated route. Other road features and terrain signs along the route can be identified, too, such as a traffic roundabout 1638, as depicted in the figure, or a slipway.
Turning now to Figure 16, the routing engine 806 then checks the input data to determine if the driving instructions are requested and if so, at what level of detail, in an instruction verification phase 1610. If the instructions are not requested, the routing engine simply calculates the length of the route and estimates the time it will take to complete it and outputs the route data, in an output phase of the 1612 polyline. route is downloaded to client 702 and typically passed to mapping engine 802, as well, for generating a map of the corresponding corridor, as described later in this document and depicted in FIG. 17. If instructions are requested, the routing engine builds a list of maneuvers that will be required along the route, in an instruction generation phase 1614. For each maneuver, client 702 uses the information in the maneuver list to prepare proper verbal instructions (eg right turn in 300m, followed by right turn in 50m, followed by right turn now). The list of maneuvers is downloaded to the client 702 together with the route, in an output phase of instructions 1616.
The mapping engine 802 generates a map of the corridor along route 1730. As depicted in Figure 17, the corridor map is actually composed of a sequence of 1640 segment maps, labeled GMO-1, GM1-2 , GM2-3 and GM3-D, which contain segments 1632 of Route 1730 and a certain area on each side of the route. The scales of the segment maps vary according to the lengths of the corresponding segments of the route. (This feature of segment maps is also illustrated in Figures 2B 2E). Optionally, long segments, such as RS4, can be broken into multiple 1642 submaps.
Although 1640 segment maps differ in size within the GIS benchmark, they comprise roughly equal volumes of data, since smaller maps (such as GMO-1) are typically viewed by client 702 at a higher magnification level. and thus show more detail. Maps are downloaded incrementally to client 702 as the client proceeds along route 1730. Note that some features, in areas of overlap between maps of successive segments, can be downloaded twice, which increases the volume of data that must be transmitted to the client, but reduces the computational load on the client.
Figure 18 is a flow chart schematically illustrating a procedure for generating a corridor map along a given route, in accordance with an embodiment of the present invention. To begin the generation of the map, the mapping engine 802 receives input parameters that define the corridor, in a data input phase 1802. The data includes a polyline that defines the route that has been calculated (in phase 1612 or 1616, for example), as well as the maximum distance (max_distance) on each side of the route to be included in the maps of 1640 segments. The max_distance parameter determines the relationship between dimensions of the segment maps. Other parameters can also be specified, such as the type of transport (car, bicycle or pedestrian), to determine which characteristics are to be included in the corridor map.
For each segment 1632 of the route, the mapping engine 802 calculates a bounding box by expanding
ES 2 425 555 T3 the poly-line by the max_distance on each side of the route, in a phase of expansion of the box 1804. As shown in figure 17, each border box is characterized by certain coordinates of the location and a magnification level, as well as by an orientation angle α relative to a reference direction of the map data. The magnification and angle are used, along with the template information, in determining which map features are to be displayed on the corridor map and how the map data corresponding to these features should be processed. prior to download to client 702. These aspects of mapping engine 802 operation were described in detail earlier in this document with reference to FIG. 13.
To clip the map data to be used in each 1640 segment map, the mapping engine 802 searches the R-Tree branches of the streets layer of the map data 1000, in a street search phase. 1806. As in the procedure in figure 14, the mapping engine finds out, for each branch of the R-Tree, whether the branch lies within or intersects the bounding box, in a phase of verification of the 1808 superposition. In the case of the corridor map, however, all the road segments corresponding to the R-Tree branches that are even partially within the boundary box are collected for inclusion in the segment map, in a phase of segment collection 1810. In other words, even if a segment of a route near Highway 1730 is only partially within the bounding box, the segment is included in the corridor map. The minor branches of the branches that remain inside or intersect with the boundary box are verified and included, also, in a collection phase of minor branches 1812. On the other hand, the branches of the R-Tree that remain entirely outside the box The borderline are eliminated from the map, in a phase of omission of branches 1820. The minor branches of these omitted branches are also omitted, in a phase of omission of the minor branches 1822.
After collecting all the road segments to be included in a segment map, the mapping engine accesses the segment entries 1204 and the turn restriction entries 1210 in the routing data structure 1200, in order to determine connectivity between segments, in a collection phase of routing 1830. This information can be used not only in viewing available maneuvers and restrictions on segment maps, but also in rerouting the customer back to Route 1730 in the event of a wrong turn. This kind of re-routing can be performed by client 702, in order to reduce the need for client-server communication, by applying a simple routing algorithm to the map information contained in the next memory. The mapping engine 802 outputs the map topology data for each route segment, in an 1832 topology output phase.
Reference is now made to Figures 19A-D, which schematically illustrate the operation of client 702, in accordance with one embodiment of the present invention. Figure 19A is a flow chart showing the key phases in the customer functional flow, while Figures 19B-D show user interface screens that are viewed by the customer. When the client program starts up, the manager 850 reads the functional parameters from the dropout 855, in a parameter read phase 1902. The parameters are then used in the client's interaction with the server 700. They include information such as:
- User's language preference, that is, the language in which the map labels and messages will be presented to the user.
- A list of available mapping servers.
- The username and password of the user who is activating the client device.
- Other application-specific values.
Figures 19B, C and D schematically illustrate customer interface screens 702 displayed on display 856, which allow the user to set some of the parameters used by the customer. Figure 19B shows a 1950 location screen, which allows the user to select a 1952 map region and a 1964 map language, as well as a 1956 outer layer, which defines the look and feel of the screen displays without that affect the underlying functionality. User-selected location parameters are used to inform server 700 of the desired navigation area and the language to be used for navigation labels and instructions. The map language can also be used in selecting a set of phonetic rudiments for the specific language selected. Server 700 can then download the appropriate set of rudiments to client 702, to be kept in memory by the client and used in generating instructions audible to the user. Since all map data is stored off-board, on server 700, the same client can be used substantially anywhere in the world, without purchasing or reloading the data.
Figure 19C shows a 1960 availability screen, which allows the user to set display and user interface preferences, such as a 1962 map orientation and 1964 distance units. The map orientation selection defines whether the maps will be rotated as the user navigates to
ES 2 425 555 T3 along a certain path (as shown in Figures 2B-2E), or slide, in a fixed orientation (as shown in Figure 2F). A default entry procedure 1966 allows the user to select different formats for entering requested destinations for navigation instructions: by house number, crossroads (such as the corner of Fifth Avenue and 42nd Street), or a selected point of interest. . A default view mode 1968 allows the user to select the type of template to be used for map displays, such as a day or night template, as described earlier in this document. All of these settings can be changed by the user in the course of customer interaction 702.
Figure 19D shows a functionality screen 1970, which allows the user to customize the way in which navigation instructions are presented by the client 702. A 1972 default navigation mode allows the user to choose between receiving both maps and verbal instructions, or only verbal instructions (which can be displayed on the 856 display or interpreted audibly by speech synthesis, as described above. earlier in this document). When the communication network coverage and the round trip time (information waiting time) of the communications are poor, both the user and the manager 850 can switch to the maneuver-only navigation mode, thereby reducing mode the amount of data that must be downloaded to the customer 702. This change may affect the cost of the navigation service as well, if usage-based billing is applied.
Other preferences accessed on the 1970 screen include an option to find the 1974 car, which displays or hides the 216 icon, and the 1976 default route optimization option, which has been described earlier in this document. An off-road behavior option 1978 instructs the manager 850 whether, when the vehicle makes a wrong turn, the customer 702 should automatically generate new navigation instructions or whether it should simply prompt the user to take any necessary action.
Turning now to Figure 19A, once client 702 has booted up, it searches for a mapping server 700 to communicate with, in a server 1904 selection phase. Typically, client 702 has a list of available servers (related by address). IP, for example). The client fetches the servers on their list to find the server that is capable of providing the fastest service. For example, the client can send a hello request to initiate communications with each server on the list and can then choose the server that takes the shortest time to respond. In this phase, the authentication functionality 730 of the servers 700 also verifies the username and password supplied by the client 702. If servers do not respond to the client within a predetermined timeout limit, the client displays an error message, in a 1906 error display phase. The user can request the client to try again to find a server, in a failure phase. revision 1908. Otherwise, the client program terminates.
After finding and selecting a server, the client 702 requests the server to download templates and other global information to be used in processing and displaying the maps, in a preliminary download phase 1910. The global information may include, for example, types Default Objects (DOT) and metrics. (The default object types specify the object types which are to be included in the maps downloaded below to the client and the objects which are to be omitted, when the default object types are not overridden by the client's preferences. The metrics are used in the conversion between map and display coordinates). If the client 702 has already saved the templates in memory 855 from a previous mapping session, it can simply send the server 700 an identification (such as a version number) of the templates it has in memory. In this case, the server does not need to resend all the templates to the client, but instead download only the changes that have been made to the templates, if any have been made. At this stage, the server can also check the version number of the client software and can download a new version if the current version is out of date.
The client 702 then prompts the user to select a destination to which the user wishes to navigate or a location whose neighborhood the user wishes to see on a map, in a location selection phase 1912. The user may choose to enter the destination or another location in the form of a house number, crossroads, or a point of interest, as noted earlier in this document. A point of interest selection process is illustrated later in this document, for example, in Figures 20A-C. The user can also search the history of customer 702 to find a destination or other location that has been used in last. The user enters the selection of the place (of the chosen type) to the client 702, in a phase of entry of the destination 1914. If the user does not enter a selected location, the client program terminates, in a termination phase 1916.
The user can request both to receive navigation instructions to the selected destination, as well as simply to view a map of the selected location, in a selection phase of mode 1918. When a map is requested for display on the client 702, the manager 850 submits a map request to server 700, in a map request phase 1920. Typically, the map request includes the following fields:
- A request header, which identifies the type of request and the client and which relates an identification of the request together with information on the version and the protocol that is needed by the server when sending the response.
ES 2 425 555 T3
- Identification of the templates maintained by the client.
- Specification of the location, dimensions and orientation angle of the map.
- Objects to include or exclude from the map. The user may specify, through the user interface screens on the display 856, that certain features of the map are to be represented in map displays or, alternatively, omitted from the displays. These features may include, for example, points of interest of various types, names of geographic features, and auxiliary information, such as pop-ups and hyperlinks, that may be embedded in maps. In the absence of user selections, the default object types (DOT) are used as described earlier in this document.
The server 700 prepares and transmits the map data requested to the client 702, as described earlier in this document with reference to FIG. 13. The manager 850 at the client 702 receives and handles the response from the map, in a manipulation phase. of the 1922 map to prepare the map data for imaging. Details of phase 1922 are depicted later in this document in Figures 21A-21B. The manager 850 passes the processed map data to the imaging engine 854, which generates the map to display 856, in a map display phase 1924. The imaging engine plots each feature on the map according to the data. of the vectors provided by the server 700 (as processed by the manager 850 in step 1922) and using the visual characteristics taken from the appropriate template. The feature overlay is overlaid in the Z-order specified in the template. The text labels are read from a pool of labels provided with the map by the server 700. The road labels are preferably oriented along the angles of the roads to which they are applied (as depicted in Figures 2D and 2E, for example). An anti-overlap process is applied to smooth the lines that appear on the map to avoid jagged edges and other image artifacts that may appear due to the low resolution of the 856 display.
On the other hand, if the user requests navigation instructions in phase 1918, the manager 850 generates and sends a route request to the server 700, in a route request phase 1930. The form of the route request is similar to that of the map request, as described earlier in this document in step 1920, with appropriate changes to identify the type of request and indicate whether or not a map of the route is required. The server 700 prepares a route response, as illustrated earlier in this document in Figures 16 and 17. Upon receipt of the route response, the manager 850 processes the route data and directs the engine. image generation 854 and to the user interface 850 to display the route on the display 856, in a display phase of the route 856. If the response is accompanied by maps, the manager 850 manipulates the map data in the manner described later in this document with reference to Figures 21A-B. The maps are then displayed at step 1924, as indicated earlier in this document. document.
While the requested map is displayed, the user can request changes in the cartography mode, in a manipulation phase of the 1940 mode. For example, the user can change the magnification or the visual parameters or select a follow me mode, they can drag the map to move sideways, or you can select a hyperlink built into the map to receive additional information. The manager 850 receives these change requests, in a phase of verification of the operation of the map 1942. The manager may also determine, for example, that a display update is required in order to show the current position of the vehicle, or that the The next maneuver map (figure 2C) or segment map (figure 2D) along the route corridor should now be displayed. The manager 850 instructs the imaging engine 854 to perform the requested operations on the current map or switch to the next map, in a manipulation phase of the 1944 operation. The client 702 is cycled through the operations. phases 1924, 1940, 1942 and 1944 until no additional operations are required, typically because the vehicle has reached its destination or the user has finished viewing the current map. The user can then be prompted to choose a new destination or location, in step 1912.
Reference is now made to Figures 20A-C, which schematically illustrate a method by which a user of client 702 may select a point of interest, in accordance with one embodiment of the present invention. Figure 20A is a flow chart showing the phases of the procedure itself, which can be invoked by the user in the 1912 phase in the procedure of Figure 19. Figures 20B and 20C show customer-viewed user interface screens for the purpose of point of interest selection.
The user is prompted to enter a point of interest selection option, in a selection phase of option 2002. In particular, the user can request a list of points of interest of a desired type in a particular area of a city or region, or all POIs of the desired type within a specified radius of a specific point, or simply all POIs of the desired type within the current map region. The user interface 858 receives the user's selection, in a selection input phase 2004.
If the user has selected the city option, the user enters a text string corresponding to the desired city, in a 2014 user input phase. Client 702 submits a search request to server 700 in a search request phase 2016, invoking a search process similar to that
ES 2 425 555 T3 shown hereinabove in Figure 15A. The user can also narrow the search field by selecting an area within a city (such as a certain district or neighborhood) or by selecting the name of a street, as well as a number of a house or crossroads in the selected street. .
Alternatively, if the user has selected the point option, the user can request to search for points of interest within the radio concert from their current position (as determined by GPS, for example), or within a certain radius of a specific point in a map. In the latter case, the manager 850 checks to determine if it currently has in memory 855 a map showing the proximity of interest to the user, in a verification phase of the current map 2032. If so, this map is displayed on display 856, allowing the user to pick a point on the map. Alternatively, if no suitable map is available in memory, client 702 submits a map request to server 700 and then receives and displays a default map, showing the general area in which the client is currently located, in a display phase of the default map 2034. In either case, the user is prompted to select a point on the displayed map, in a point selection phase 2036. Typically, the user operates a mouse, stylus, or touch screen to mark a particular location on display 856. The user is also prompted to enter a radius (typically in units of miles or kilometers) around the selected point, within which the search for the point of interest will take place, in a radius entry phase 2038.
Regardless of the option chosen in phase 2004, the user must select the type of point of interest to be found, in a phase of establishing the domain of the point of interest 2050. The server 700 can control the interest rates that are allowed to search for different clients, based on the client's privileges maintained in an access control list. This feature allows multiple client communities to share the same map server while accessing different private layers of map data. Figure 20B schematically shows a point of interest selection screen 2060, which is displayed by client 702 for this purpose. A category window 2062 lists the types of POIs that are available and allows the user to select the type of POI from the list. Function buttons 2064 allow the user to request from the server 700 navigation directions to a selected POI or provide a map of the POI area. When requesting navigation directions, the user can select navigation type buttons 2066, as described earlier in this document.
The client 702 passes the user's selections to the server 700 in a search request that indicates the type of point of interest that the user has selected and the geographic area in which the search is to be performed. The server returns a list of relevant POIs, which can be organized according to their proximity to the user-specified location. Client 702 displays this list on display 856, in a POI list display phase 2052. The user selects an entry from the POI list, in an entry selection phase 2054. The client 702 then proceeds to generate a map of the area of the selected point of interest or navigation instructions leading from the client's current location to the point of interest, as described earlier in this document with reference to Figure 19. .
Figure 20C schematically shows a screen for selecting the point of interest 2070, which is displayed on the display 856 in step 2052. In this example, the user has selected gas stations in step 2050 and names of the next gas stations 2074 are displayed. in a selection window for point of interest 2072. Alternatively, the points of interest in the list provided by the server 700 may be presented to the user in the form of icons or names on a map displayed on the display 856.
Figures 21A and 21B are flow charts showing schematically details of the manipulation phase of map 1922, according to an embodiment of the present invention. The map response returned by the server 700 (at step 1322 in FIG. 13, for example) begins with the map parameters, which are read by the manager 850 in a parameter reading phase 2102. These parameters typically include X - Y ordinates of the map rectangle, the height and width of the rectangle , the rotation angle of the map (relative to geographic north), and the magnification level of the map. The map response also includes a string background, which contains, in encoded form, the text to be used in all labels in the current map. The manager 850 reads and decodes the string background from the response, in a string read phase 2104, and stores the text of the string in memory 855. In addition, the manager 850 reads from the response of the map the number of layers of the vector map data to be contained in the response, in a read phase of layer number 2106.
The manager 850 uses the number of layers as a link index over all data layers contained in the response, in a link phase of layers 2110. The manager processes the data in each layer until all layers have been completed. . To start the processing of each layer, the manager 850 reads the identifier of the layer, in a phase of identifying the layer 2112. It then reads the number of junctions in the current layer, in a reading phase of the number of junctions 2114. (Although each junction is shared by two or more poly-lines, it is more efficient to download the coordinates of each junction to client 702 only once. Junctions can also be used by client 702 in rerouting calculations, if the vehicle deviates from the route provided by server 700). The number of joints is used as an index on the link over all joints in the layer
ES 2 425 555 T3 current, in a linking phase of the junctions 2120. Each junction has corresponding XY coordinates, but to compact the representation, the coordinates of each junction can be transferred from the server 700 to the client 702 in the form of an offset from the coordinates of the previous junction in the list. When the manager
850 links over the list of connections, reads the offset and resets the X - Y coordinates of each connection based on the offset, in a phase of calculating the coordinates of the connection 2122.
The manager 850 then reads the number of object types in the current layer, in a read frame of type number 2124. Possible object types include point, polyline, polygon, label, image, and circle. Typically, the client 702 has a Java class for each of the different object types. This class contains the procedures necessary to draw the corresponding type of object at the coordinates indicated by the map data received from the server 700, using the visual characteristics specified by the appropriate template.
The handler 850 uses the object type number as an index to bind over the different types of objects in the current layer, in a type bind phase 2130. For each type of object, the handler first reads the identifier of the type, in an identification phase of type 2132. Then it reads the appropriate class of the object for the object type, in a reading phase of class 2134. The manager reads the number of objects of the current type, in a reading phase of the number of objects 2136 and then reads in the objects themselves, in a reading phase of objects 2140. For each object read in this phase, the manager 850 examines the object's parameters to determine if the object has an index that points to auxiliary information, such as a descriptive tag, tooltip, or hyperlink. If so, the manager will use the index to associate the object with the appropriate text in the string background that was sent by the server 700 as a part of the map response. The manager also reads the coordinates of the object, such as the coordinates of each vertex in each polyline or polygon, or the coordinates of the center of circles and images. After all map objects have been read and associated with their appropriate classes, the map is generated for display 856 in step 1924, as described earlier in that document.
It will be appreciated that the embodiments described earlier herein are cited by way of example and that the present invention is not limited to what has been particularly represented and described earlier herein.
Contents16
34 sheets
Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11 Sheet 12 Sheet 13 Sheet 14 Sheet 15 Sheet 16 Sheet 17 Sheet 18 Sheet 19 Sheet 20 Sheet 21 Sheet 22 Sheet 23 Sheet 24 Sheet 25 Sheet 26 Sheet 27 Sheet 28 Sheet 29 Sheet 30 Sheet 31 Sheet 32 Sheet 33 Sheet 34
24 members in 5 offices
Priority claims8
| Document | Office | Kind | Date |
|---|---|---|---|
| 37701902 | United States of America | P | |
| 37701902 | United States of America | P | |
| 0300344 | Israel | W | |
| 0300344 | Israel | W | |
| 377019P | – | – | – |
| PCTIL200300344 | – | – | – |
| US20020377019P | – | – | – |
| WO2003IL00344 | – | – | – |
Members24
| Document | Office | Kind | |
|---|---|---|---|
| WO03093765A2 | World Intellectual Property Organization (WIPO) | A2 | |
| WO03093767A1 | World Intellectual Property Organization (WIPO) | A1 | |
| WO03093768A1 | World Intellectual Property Organization (WIPO) | A1 | |
| AU2003223090A1 | Australia | A1 | |
| AU2003223091A1 | Australia | A1 | |
| AU2003223091A8 | Australia | A8 | |
| AU2003224396A1 | Australia | A1 | |
| US2003229441A1 | United States of America | A1 | |
| WO03093765A3 | World Intellectual Property Organization (WIPO) | A3 | |
| US2004027258A1 | United States of America | A1 | |
| US2004030493A1 | United States of America | A1 | |
| EP1502078A1 | European Patent Office (EPO) | A1 | |
| EP1502079A2 | European Patent Office (EPO) | A2 | |
| EP1502080A1 | European Patent Office (EPO) | A1 | |
| US2005033511A1 | United States of America | A1 | |
| US6898516B2 | United States of America | B2 | |
| US6904360B2 | United States of America | B2 | |
| US6917878B2 | United States of America | B2 | |
| US7089110B2 | United States of America | B2 | |
| EP2463627A2 | European Patent Office (EPO) | A2 | |
| EP1502080B1 | European Patent Office (EPO) | B1 | |
| EP2463627A3 | European Patent Office (EPO) | A3 | |
| ES2425555T3This record | Spain | T3 | |
| EP2463627B1 | European Patent Office (EPO) | B1 |
Numbers
- Publication
- 2425555
- Publication, DOCDB
- 2425555
- Publication, EPODOC
- ES2425555T
- Application
- 3720823
- Application, DOCDB
- 03720823
- Application, EPODOC
- ES20030720823T
Titles2
- Spanish
- Sistema de navegación que utiliza mapas de corredores
- English
- Navigation system that uses corridor maps
Classification
- CPC, 6
- G01C21/3682
- G01C21/30
- G01C21/3611
- G01C21/3667
- G01C21/3679
- G01C21/3889
- IPC, 4
- G01C21 26
- G01C21 30
- G01C21 32
- G01C21 36