Method for automatically determining a boundary of a partial area of a total area

• US 8,798,845 B2
• Filed: 11/14/2011
• Issued: 08/05/2014
• Est. Priority Date: 11/19/2010
• Status: Active Grant

• Current Assignee: Audi AG (Volkswagen AG)
• Original Assignee: Audi AG (Volkswagen AG)
• Inventors: Lange, Rainer
• Primary Examiner(s): Cheung, Mary
• Assistant Examiner(s): WONG, YUEN H
• Application Number:
  US13/988,448
• Publication Number:
  US 20140005878A1
• Time in Patent Office: 995 Days
• Field of Search: 701/29.1, 701/410
• US Class Current: 701/29.1
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• CPC Class Codes: G01C 21/3453 Special cost functions, i.e. other than distance or default speed limit of road segments
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• CPC Class Codes: G01C 21/3697 Output of additional, non-guidance related information, e.g. low fuel level G01C21/3679 takes precedence
• CPC Class Codes: G06F 17/00 Digital computing or data processing equipment or methods, specially adapted for specific functions information retrieval, database structures or file system structures therefor G06F16/00
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

A method automatically determines a boundary of a partial area of a map, the partial area indicating the remaining range of a motor vehicle. The total area is divided into a matrix of rectangular area segments, with which a connected subset of the partial area is associated. Initially starting from a region of the total area not belonging to the partial area, a boundary area segment of the partial area is located and a first point describing the position of the boundary area segment is entered into a list of points, following which the process proceeds along the edge of the partial area and a point describing the position of the boundary area segment is entered into the list for each further boundary area segment located, until the boundary area segment corresponding to the first point is reached again. The boundary is determined from the list of points.

Claims

1. A method for automatically determining a boundary, comprising:

dividing, by a processor, a total area of a map into a matrix of rectangular area segments;

determining a partial area of the map, the partial area being associated with a connected subset of the rectangular area segments, the partial area being determined using an algorithm that determines a remaining range of a motor vehicle;

initially starting from a region of the total area not belonging to the partial area, finding a first boundary area segment of the partial area;

entering a first point describing a position of the first boundary area segment into a list of points;

after entering the first point, stepping along an edge of the partial area;

for each further boundary area segment that is found, entering a corresponding further point describing a position of the further boundary area segment into the list of points; and

when the first boundary area segment is reached again, determining the boundary from the list of points.

2. The method as claimed in claim 1,

wherein finding the first boundary area segment of the partial area comprises:

starting from an area segment not belonging to the partial area, checking along a path in a current search direction until the first boundary area segment is encountered, the current search direction extending along a row or column of the matrix; and

setting the first boundary area segment as the current boundary area segment, and

wherein stepping along the edge of the partial area and finding further boundary area segments comprises;

a) setting a last-not-occupied area segment as a test area segment, the last-not-occupied area segment being an area segment not belonging to the partial area and adjacent to the current boundary area segment on a side of the current boundary area segment opposite the current search direction;

b) checking whether, in a second search direction perpendicular to the current search direction, there is a further boundary area segment of the partial area adjacent to the test area segment;

c) if checking in b) gives a positive result, setting the further boundary area segment as the current boundary area segment, setting the second search direction as the current search direction and repeating a) and b);

d) if checking in b) gives a negative result, checking whether there is a further boundary area segment adjacent to the current boundary area segment in the second search direction;

e) if checking in d) gives a positive result, setting the further boundary area segment as the current boundary area segment, retaining the current search direction and repeating a) and b); and

f) if checking in d) gives a negative result, retaining the current boundary area segment, setting the current search direction to a direction opposite to the second search direction and repeating a) and b).

3. The method as claimed in claim 2, wherein finding the first boundary area segment starts from an area segment at an edge of the total area and not belonging to the partial area.

4. The method as claimed in claim 2, wherein the second search direction is a direction rotated clockwise by 90°

from the current search direction.

5. The method as claimed in claim 1, wherein the algorithm used to determine the partial area associates with each area segment an energy cost for traversing the area segment, the algorithm comprising:

starting from a starting area segment corresponding to a current position of the motor vehicle;

finding paths from the starting area segment by expanding from the starting area segment on paths to respective adjacent area segments, each path being continued until a residual energy contained in an energy storage system for a drive acting on at least one wheel of the motor vehicle has been consumed; and

marking each area segment visited while finding paths as an area segment associated with the partial area.

6. The method as claimed in claim 1, wherein

each point in the list of points represents a center point of a boundary area segment, and

the boundary is a line determined from the list of points.

7. The method as claimed in claim 1, wherein a polygon is determined as the boundary.

8. The method as claimed in claim 1, further comprising displaying the total area of the map using the boundary to offset the partial area from the total area.

9. The method as claimed in any claim 1, wherein the partial area does not contact any edge of the matrix.

10. The method according to claim 1, wherein, if the partial area contacts an edge of the matrix, the boundary is determined by advancing along the edge of the matrix until an area segment at the edge the matrix not belonging to the partial area is located.

11. A motor vehicle, comprising:

a drive acting on at least one wheel of the motor vehicle;

an energy storage system for the drive; and

a computing device to automatically determine a boundary by a method comprising;

dividing a total area of a map into a matrix of rectangular area segments;

determining a partial area of the map, the partial area being associated with a connected subset of the rectangular area segments, the partial area being determined using an algorithm that determines a remaining range of the motor vehicle;

initially start from a region of the total area not belonging to the partial area, finding a first boundary area segment of the partial area;

entering a first point describing a position of the first boundary area segment into a list of points;

after entering the first point, stepping along an edge of the partial area;

for each further boundary area segment that is found, entering a corresponding further point describing a position of the further boundary area segment into the list of points; and

when the first boundary area segment is reached again, determining the boundary from the list of points.