Planar graph generation device and method

Patent metadata

Field	Value
Publication number	US-10191928-B2
Application number	US-201414510223-A
Country	US
Kind code	B2
Filing date	Oct 9, 2014
Priority date	Oct 11, 2013
Publication date	Jan 29, 2019
Grant date	Jan 29, 2019

Abstract

A planar graph generation device that includes a processor that executes a process. The process includes: computing a specific value, including components of a value representing complexity of a track of the given track data, and a value representing a non-nearness between the given track data and each of all the other track data; selecting the track data with the smallest specific value among the collection; a first portion of the first track or a second portion of the second track positioned within the specific distance of each other, or a combination of the first portion and the second portion, is approximated to a specific portion such that a track of the addition target track data after addition passes through the specific portion in cases in which there are portions positioned within the specific distance of each other in a combination of the first track with the second track.

First claim

What is claimed is:

1. A plane graph generation device comprising:
a memory; and
a processor configured to execute a process, the process comprising:
selecting first track data that is associated with a smallest specific cost among a collection of track data, the collection of track data including the first track data, a second track data, and a third track data, wherein
each track data in the collection is obtained from a position detection sensor mounted on a moving vehicle and includes a plurality of positional data each representing a position on a path along which the moving vehicle has moved and link data representing links between the positions on the path, and
the specific cost associated with the first track data in the collection is a value that includes a first component and a second component,
the first component, representing complexity of the first track data, includes at least one selected from the group consisting of
 a number of positions in the first track data,
 a number of the links in the first track data, and
 a total length of the links in the first track data, and
the second component, representing a non-nearness between the first track data and each of all the other track data in the collection, includes at least one selected from the group consisting of
 the number of positions of the first track data that are outside a region, the region being represented by the respective positions of the first track data and track data other than the first track data that are within a specific distance of each other,
 the number of links of the first track data that are outside the region,
 the total length of the links of the first track data that are outside the region,
 a surface area determined from the positions and the links of the first track data that are outside the region, and
 a greatest distance between the positions of the first track data that are outside the region;

selecting the second track data based on a specific cost of the second track data being less than a specific cost of the third track data;
if none of the respective positions within the first track data and the second track data is within a predetermined distance from each other, adding the positional data and the link data of the first track data to the second track data; and
if there is a first set of positions within the first track data and a second set of positions within the second track data that are within the predetermined distance from each other, modifying the second track data by changing the second set of positions within the second track data to a first set of positions or to a combination of a first set of positions and a second set of positions; and
generating, based on the second track data, a plane graph in which the positions of the moving vehicle are simplified to be used for analyzing paths along which the moving vehicle has moved.

2. The planar graph generation device of claim 1 , the process further comprising:
determining whether or not there is track data remaining in the collection, and whether or not the specific cost value of the first track has fallen below a previous specific cost; and
in cases in which it is determined that there is track data in the collection and the specific cost value of the first track has not fallen below the previous specific cost, adding all the track data remaining in the collection to the first track data and the second track data.

3. The planar graph generation device of claim 1 , wherein
the specific cost is determined based on whether or not there are portions of the first track and the second track positioned within a specific distance of each other in a combination of the first track data and each respective track of all the other track data, the second component representing the non-nearness being computed based on content of track data of portions of the first track and the second track other than the portions of the first track and the second track positioned within the specific distance of each other in cases in which there are portions of the first track and the second track positioned within the specific distance of each other in the respective tracks, and the second component representing the non-nearness being computed based on content of the first track data and content of each of all the other track data in cases in which there are no portions of the first track and the second track positioned within the specific distance of each other in the respective tracks.

4. The planar graph generation device of claim 1 , wherein
the specific cost is a summation value of the first component and the second component.

5. The planar graph generation device of claim 4 , wherein
the summation value is a weighted summation value.

6. A non-transitory recording medium storing a program that causes a computer to execute a planar graph generation process, the process comprising:
selecting first track data that is associated with a smallest specific cost among a collection of track data, the collection of track data including the first track data, a second track data, and a third track data, wherein
each track data in the collection is obtained from a position detection sensor mounted on a moving vehicle and includes a plurality of positional data each representing a position on a path along which the moving vehicle has moved and link data representing links between the positions on the path, and
the specific cost associated with the first track data in the collection is a value that includes a first component and a second component,
the first component, representing complexity of the first track data, includes at least one selected from the group consisting of
a number of positions in the first track data,
a number of the links in the first track data, and
a total length of the links in the first track data, and

the second component, representing a non-nearness between the first track data and each of all the other track data in the collection, includes at least one selected from the group consisting of
the number of positions of the first track data that are outside a region, the region being represented by the respective positions of the first track data and track data other than the first track data that are within a specific distance of each other,
the number of links of the first track data that are outside the region,
the total length of the links of the first track data that are outside the region,
a surface area determined from the positions and the links of the first track data that are outside the region, and
a greatest distance between the positions of the first track data that are outside the region;

selecting the second track data based on a specific cost of the second track data being less than a specific cost of the third track data;
if none of the respective positions within the first track data and the second track data is within a predetermined distance from each other, adding the positional data and the link data of the first track data to the second track data; and
if there is a first set of positions within the first track data and a second set of positions within the second track data that are within the predetermined distance from each other, modifying the second track data by changing the second set of positions within the second track data to a first set of positions or to a combination of a first set of positions and a second set of positions; and
generating, based on the second track data, a plane graph in which the positions of the moving vehicle are simplified to be used for analyzing paths along which the moving vehicle has moved.

7. The non-transitory recording medium of claim 6 , the planar graph generation process further comprising:
determining

Assignees

• Fujitsu Ltd

Inventors

• Inakoshi Hiroya
• Asai Tatsuya
• Morikawa Hiroaki
• Shigezumi Junichi

Classifications

• G06F16/2237 Primary

  Vectors, bitmaps or matrices · CPC title

• G06F17/30324 Primary

  Physics · mapped topic