Method, system, and computer product for forming a graph structure that describes free and occupied areas

• US 8,286,122 B2
• Filed: 06/14/2010
• Issued: 10/09/2012
• Est. Priority Date: 10/23/2002
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: De Graeve, Charles-Marie, Fiegert, Michael
• Primary Examiner(s): Memula, Suresh
• Application Number:
  US12/801,548
• Publication Number:
  US 20100293517A1
• Time in Patent Office: 848 Days
• Field of Search: 716/4, 716/136, 706/20, 706/32
• US Class Current: 716/136
• CPC Class Codes: G05D 1/024 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A graph structure is generated to describe an area with a free area and an occupied area. In this case a topological graph structure for the free area is determined. A point of the topological graph structure is selected and for this a nearest adjacent occupied area point is determined. For this nearest adjacent occupied area point location information is determined. The graph structure is formed from at least the selected point of the topological graph structure and from the associated location information of the nearest adjacent occupied area point.

Claims

1. A method implemented in a computer for forming a graph to describe a location having a free area and an occupied area, comprising:

determining a topological graph structure for only the free area;

selecting a point in the topological graph structure;

for the selected point of the topological graph structure, determining an adjacent occupied area;

selecting an occupied point for the adjacent occupied area, the occupied point being at a shortest physical distance to the selected point of the topological graph structure;

determining associated location information for the occupied point; and

forming, by the computer, the graph from the selected point of the topological graph structure and from the associated location information for the occupied point.

2. The method in accordance with claim 1, wherein

the location has a plurality of sub-areas, and

the graph is formed by combining graphs for the plurality of sub-areas.

3. A system to form a graph a location having a free area and an occupied area, comprising:

a structure determination unit to determine a topological graph structure for only the free area;

a selection unit to select a point in the topological graph structure;

an obstacle identification unit to identify an obstacle and to select an occupied point for the obstacle, the occupied point being at a shortest physical distance to the selected point of the topological graph structure;

a location determination unit to determine associated location information for the occupied point; and

a graph generation unit, to form the graph from the selected point of the topological graph structure and from the associated location information for the occupied point.

4. A non-transitory computer-readable medium storing program to control a computer to perform a method for forming a graph structure to describe a location having a free area and an occupied area, the method comprising:

determining a topological graph structure for only the free area;

selecting a point in the topological graph structure;

for the selected point of the topological graph structure, determining an adjacent occupied area;

selecting an occupied point for the adjacent occupied area, the occupied point being at a shortest physical distance to the selected point of the topological graph structure;

determining associated location information for the occupied point; and

forming the graph from the selected point of the topological graph structure and from the associated location information for the occupied point.