Navigation method and system for extracting, sorting and displaying POI information

• US 7,272,489 B2
• Filed: 07/18/2002
• Issued: 09/18/2007
• Est. Priority Date: 07/18/2002
• Status: Expired due to Fees

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Tu, Ihung S.
• Primary Examiner(s): Nguyen; Thu V.
• Application Number:
  US10/198,596
• Publication Number:
  US 20040204821A1
• Time in Patent Office: 1,888 Days
• Field of Search: 701/200, 701/23, 701/202, 701/205, 701/209, 701/211, 701/213, 340/990, 340/995
• US Class Current: 701/200
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence

Abstract

A navigation method and system for extracting point of interest (POI) data from a map data source and sorting the POIs by distance from a current user position to display the same at high speed without requiring a large memory. The navigation system aligns the cells each having specified POI in an cell array and classifies the cells into a plurality of different levels based on distance (first sorting operation) from the current user position, or positions of the cells in the cell array relative to the cell closest to the user position. The navigation system extracts the POIs from the cells in the specified level, sorts the POIs by distance (second sorting operation), and displays the POIs. During each process, the navigation system retrieves and processes only a small amount of POIs sufficient for the current display screen and immediate scrolls of few pages.

Claims

1. A navigation method for displaying point of interest (POI) information for selecting a destination, comprising the following steps of:

specifying a category of POI in a navigation system for displaying a list of specified POIs;

collecting a predetermined number of populated cells from a cell matrix and producing an array of populated cells where a populated cell is a cell having at least one POI of specified category therein;

conducting a first sorting operation for sorting the populated cells in the populated cell array by distance from a predetermined position irrespective of numbers of POIs in the populated cells;

retrieving the specified POIs from a first distance level of sorted populated cells and conducting a second sorting operation for sorting the retrieved POIs by distance from the predetermined position;

displaying and scrolling a list of specified POIs in the order of distance from the predetermined position; and

repeating foregoing steps for a next distance level of populated cells when POIs to be displayed are insufficient for further scroll request.

2. A navigation method as defined in claim 1, wherein said step of collecting the populated cells includes a step of determining the predetermined number of populated cells based on a particular kind of POI category specified by a user in such a way to retrieve a sufficient number of specified POIs to be displayed and scrolled on a screen of the navigation system.

3. A navigation method as defined in claim 2, wherein said sufficient number of specified POIs is about several tens, which are displayed on the screen as the list of POIs with several pages of scroll.

4. A navigation method as defined in claim 1, wherein said step of conducting the second sorting operation for sorting the retrieved POIs by distance from the predetermined position includes a step of detecting an out of order POI having a distance from the predetermined position larger than the first distance level and temporarily storing the out of order POI in a buffer memory.

5. A navigation method as defined in claim 4, wherein said out of order POI is retrieved from the buffer memory and inserted in a list of POIs extracted from the next or higher distance level of populated cells to be displayed in the order of distance from the predetermined position.

6. A navigation method for displaying point of interest (POI) information for selecting a destination, comprising the following steps of:

specifying a category of POI in a navigation system for displaying a list of specified POIs;

collecting a predetermined number of populated cells from a cell matrix formed in a map data storage and producing an array of populated cells where a populated cell is a cell having at least one POI of specified type therein, wherein the cells in the populated cell array are aligned based on positions in the cell matrix;

determining a populated cell which is closest to a predetermined position and conducting a first sorting operation by selecting a prescribed number of populated cells adjacent to the closest populated cell irrespective of numbers of POIs in the populated cells to establish a first level of populated cells consisting of the closest populated cell and the adjacent populated cells;

retrieving the specified POIs from the first level of cells and conducting a third sorting operation for sorting the retrieved POIs by distance from the predetermined position;

displaying and scrolling a list of specified POIs in the order of distance from the predetermined position; and

repeating foregoing steps for a next level of populated cells when POIs to be displayed are insufficient for further scroll request.

7. A navigation method as defined in claim 6, further comprising a step of conducting a second sorting operation for sorting the populated cells in the first level by distance from the predetermined position before retrieving the POIs from the populated cells.

8. A navigation method as defined in claim 6, wherein said step of determining the closest populated cell to the predetermined position includes a step of finding a shortest distance from the predetermined position to each of the populated cells and comparing the shortest distance of each populated cell.

9. A navigation method as defined in claim 6, wherein said step of collecting the populated cells includes a step of determining the predetermined number of populated cells based on a particular kind of POI category specified by a user in such a way to retrieve a sufficient number of specified POIs to be displayed and scrolled on a screen of the navigation system.

10. A navigation method as defined in claim 9, wherein said sufficient number of specified POIs is about several tens, which are displayed on the screen as the list of POIs with several pages of scroll.

11. A navigation method as defined in claim 6, wherein said step of conducting the third sorting operation for sorting the retrieved POIs by distance from the predetermined position includes a step of detecting an out of order POI having a distance from the predetermined position larger than a first distance level and temporarily storing the out of order POI in a buffer memory.

12. A navigation method as defined in claim 11, wherein said out of order POI is retrieved from the buffer memory and inserted in a list of POIs extracted from the next or higher level of populated cells to be displayed in the order of distance from the predetermined position.

13. A navigation method for displaying point of interest (POI) information for selecting a destination, comprising the following steps of:

specifying a category of POI in a navigation system for displaying a list of specified POIs;

defining a first level cell matrix formed in a map data storage and a second level cell matrix where each cell in the second level cell matrix corresponds to a plurality of cells in the first level cell matrix;

collecting a predetermined number of first level populated cells from the first level cell matrix by collecting a predetermined number of second level populated cells from the second level cell matrix where a populated cell is a cell having at least one specified POI therein;

sorting the second level populated cells by distance from a predetermined position irrespective of numbers of POIs in the populated cells to determine the second level populated cells in a first distance level and the second level populated cells in a second distance level;

retrieving the first level populated cells corresponding to the sorted second level populated cells in the first distance level and sorting the first level populated cells by distance from the predetermined position;

retrieving the specified POIs from the first level populated cells in the first distance level and sorting the retrieved POIs by distance from the predetermined position;

retrieving the first level populated cells corresponding to the sorted second level populated cells in the second distance level and sorting the first level populated cells by distance from the predetermined position;

retrieving the specified POIs from the first level populated cells in the second distance level and sorting the retrieved POIs by distance from the predetermined position;

combining the POIs sorted by distance for the first distance level and the POIs sorted by distance for the second distance level; and

displaying and scrolling a list of specified POIs in the order of distance from the predetermined position.

14. A navigation system for displaying point of interest (POI) information for selecting a destination, comprising:

means for specifying a category of POI in a navigation system for displaying a list of specified POIs;

means for collecting a predetermined number of populated cells from a cell matrix and producing an array of populated cells where a populated cell is a cell having at least one POI of the specified category therein;

means for conducting a first sorting operation for sorting the cells in the populated cell array by distance from a predetermined position irrespective of numbers of POIs in the populated cells;

means for retrieving the specified POIs from a first distance level of sorted populated cells and conducting a second sorting operation for sorting the retrieved POIs by distance from the predetermined position;

means for displaying and scrolling a list of specified POIs in the order of distance from the predetermined position; and

means for repeating foregoing operations for a next distance level of populated cells when POIs to be displayed are insufficient for further scroll request.

15. A navigation system as defined in claim 14, wherein said means for collecting the populated cells includes means for determining the predetermined number of populated cells based on a particular kind of POI category specified by a user in such a way to retrieve a sufficient number of specified POIs to be displayed and scrolled on a screen of the navigation system.

16. A navigation system as defined in claim 15, wherein said means for conducting the second sorting operation for sorting the retrieved POIs by distance from the predetermined position includes means for detecting an out of order POI having a distance from the predetermined position larger than the first distance level and temporarily storing the out of order POI in a buffer memory.

17. A navigation system as defined in claim 16, wherein said out of order POI is retrieved from the buffer memory and inserted in a list of POIs extracted from the next or higher distance level of populated cells to be displayed in the order of distance from the predetermined position.

18. A navigation system for displaying point of interest (POI) information for selecting a destination, comprising:

means for specifying a category of POI in a navigation system for displaying a list of specified POIs;

means for collecting a predetermined number of populated cells from a cell matrix formed in a map data storage and producing an array of populated cells where a populated cell is a cell having at least one POI of specified category therein, wherein the cells in the populated cell array are aligned based on positions in the cell matrix;

means for determining a populated cell which is closest to a predetermined position and conducting a first sorting operation by selecting a prescribed number of populated cells adjacent to the closest populated cell in the populated cell array irrespective of numbers of POIs in the populated cells to establish a first level of populated cells consisting of the closest populated cell and the prescribed number of adjacent populated cells;

means for retrieving the specified POIs from the first level of cells and conducting a third sorting operation for sorting the retrieved POIs by distance from the predetermined position;

means for displaying and scrolling a list of specified POIs in the order of distance from the predetermined position; and

means for repeating foregoing steps for a next level of populated cells when POIs to be displayed are insufficient for further scroll request.

19. A navigation system as defined in claim 18, further comprising means for conducting a second sorting operation for sorting the populated cells in the first level by distance from the predetermined position before retrieving the POIs from the populated cells.

20. A navigation method as defined in claim 18, wherein said means for determining the closest populated cell to the predetermined position includes means for finding a shortest distance from the predetermined position to each of the populated cells and comparing the shortest distance of each populated cell.

21. A navigation system as defined in claim 18, wherein said step of collecting the populated cells includes means for determining the predetermined number of populated cells based on a particular kind of POI category specified by a user in such a way to retrieve a sufficient number of specified POIs to be displayed and scrolled on a screen of the navigation system.

22. A navigation system as defined in claim 18, wherein said means for conducting the third sorting operation for sorting the retrieved POIs by distance from the predetermined position includes means for detecting an out of order POI having a distance from the predetermined position larger than a first distance level and temporarily storing the out of order POI in a buffer memory.

23. A navigation system as defined in claim 22, wherein said out of order POI is retrieved from the buffer memory and inserted in a list of POIs extracted from the next or higher level of populated cells to be displayed in the order of distance from the predetermined position.

24. A navigation system for displaying point of interest (POI) information for selecting a destination, comprising:

means for specifying a category of POI in a navigation system for displaying a list of specified POIs;

means for defining a first level cell matrix formed in a map data storage and a second level cell matrix where each cell in the second level cell matrix corresponds to a plurality of cells in the first level cell matrix;

means for collecting a predetermined number of first level populated cells from the first level cell matrix by collecting a predetermined number of second level populated cells from the second level cell matrix where a populated cell is a cell having at least one specified POI therein;

means for sorting the second level populated cells by distance from a predetermined position irrespective of numbers of POIs in the populated cells to determine the second level populated cells in a first distance level and the second level populated cells in a second distance level;

means for retrieving the first level populated cells corresponding to the sorted second level populated cells in the first distance level and sorting the first level populated cells by distance from the predetermined position;

means for retrieving the specified POIs from the first level populated cells in the first distance level and sorting the retrieved POIs by distance from the predetermined position;

means for retrieving the first level populated cells corresponding to the sorted second level populated cells in the second distance level and sorting the first level populated cells by distance from the predetermined position;

means for retrieving the specified POIs from the first level populated cells in the second distance level and sorting the retrieved POIs by distance from the predetermined position;

means for combining the POIs sorted by distance for the first distance level and the POIs sorted by distance for the second distance level; and

means for displaying and scrolling a list of specified POIs in the order of distance from the predetermined position.