ROUTING METHOD AND ROUTING DEVICE FOR DETERMINING TARGET ROUTE ACCORDING TO POI DISTRIBUTION

• US 20090234574A1
• Filed: 04/21/2008
• Published: 09/17/2009
• Est. Priority Date: 03/13/2008
• Status: Abandoned Application

• Current Assignee: MediaTek Singapore Pte. Ltd. (MediaTek, Inc.)
• Original Assignee: MediaTek Singapore Pte. Ltd. (MediaTek, Inc.)
• Inventors: Zhu, Lu, Deng, Dao-Wen
• Application Number:
  US12/106,347
• Publication Number:
  US 20090234574A1
• Time in Patent Office: Days
• US Class Current: 701/201
• CPC Class Codes: G01C 21/3476 using point of interest [POI] information, e.g. a route passing visible POIs

Abstract

A routing method determines a route according to a distribution of POIs within a distance extending from the route. The distribution of POIs is derived from a POI density that is calculated by dividing an amount of POIs within the distance extending from a path with a length of the path. The cost value of the path is calculated by multiplying a weighting value to a length of the path, and the weighting value is given corresponding to the density. The route is then determined dependent on a cost value of the route derived by adding the cost values of all paths contained it.

Claims

1. A routing method for determining a route from a starting point to an ending point, comprising:

obtaining a plurality of candidate paths between the starting point and the ending point from a database;

obtaining a POI (point of interest) distribution corresponding to each of the candidate paths; and

determining the route having paths selected from the candidate paths according to the detection results.

2. The method of claim 1, wherein the step of obtaining a POI distribution corresponding to each of the candidate paths comprises:

determining a POI number of POIs each located within a distance threshold from the candidate path; and

generating the POI distribution of the candidate path according to the POI number.

3. The method of claim 1, wherein the step of obtaining a POI distribution corresponding to each of the candidate paths comprises:

determining a POI number of POIs each located within a distance threshold from the candidate path;

calculating a POI density of the candidate path according to the POI number; and

generating the POI distribution according to the POI density value of the candidate path.

4. The method of claim 3, wherein the step of calculating the POI density of the candidate path comprises:

calculating a ratio of the POI number to a length of the candidate path to set the POI density.

5. The method of claim 1, wherein the step of obtaining a POI distribution corresponding to each of the candidate paths comprises:

determining a POI number of POIs each located within a distance threshold from the candidate path;

calculating a POI density of the candidate path according to the POI number;

determining a weighting factor corresponding to the POI density of the candidate path;

calculating a cost value of the candidate path according to a multiplication result of the weighting factor and a length of the candidate path; and

generating the POI distribution according to the cost value of the candidate path.

6. The method of claim 5, wherein the step of determining the POI number of POIs comprises:

determining a search area by extending the candidate path with a plurality of rectangles according to the distance threshold and the shape of the path; and

searching any POI located within the search area from the database to determine the POI number.

7. The method of claim 6, wherein the search area is a minimum bounding rectangle containing a polygonal area formed by the rectangles.

8. A routing device for determining a target route from a starting point to an ending point, comprising:

a first storage device, for storing a database;

a second storage device, for storing a routing program including a first program code, a second program code, and a third program code; and

a routing unit, coupled to the first storage device and the second storage device, for executing the first program code for obtaining a plurality of candidate paths between the starting point and the ending point from the database stored in the first storage device;

executing the second program code for obtaining a POI distribution corresponding to each of the candidate paths; and

executing the third program code for determining a route having paths selected from the candidate paths according to the detection results.

9. The routing device of claim 8, wherein the routing unit executes the second program code to obtain a POI distribution corresponding to each of the candidate paths by:

determining a POI number of POIs each located within a distance threshold from the candidate paths, and generating the POI distribution of the candidate path according to the POI number.

10. The routing device of claim 8 wherein the routing unit executes the second program code to obtain a POI distribution corresponding to each of the candidate paths by:

determining a POI number of POIs each located within a distance threshold from the candidate path;

calculating a POI density of the candidate path according to the POI number; and

generating the POI distribution according to the POI density value of the candidate path.

11. The routing device of claim 10 wherein the routing unit executes the second program code to calculate the POI density of the candidate path by calculating a ratio of the POI number to a length of the candidate path to set the POI density.

12. The routing device of claim 8, wherein the routing unit executes the second program code to obtain a POI distribution corresponding to each of the candidate paths by:

determining a POI number of POIs each located within a distance threshold from the candidate path;

calculating a POI density of the candidate path according to the POI number;

determining a weighting factor corresponding to the POI density of the candidate path;

calculating a cost value of the candidate path according to a multiplication result of the weighting factor and a length of the candidate path; and

generating the POI distribution according to the cost value of the candidate path.

13. The routing device of claim 12, wherein the routing unit executes the second program code to determine the POI number of POIs by:

determining a search area by extending the candidate path with a plurality of rectangles according to the distance threshold and the shape of the path; and

searching any POI located within the search area from the database to determine the POI number.

14. The routing device of claim 13, wherein the search area is a minimum bounding rectangle containing a polygonal area formed by the rectangles.