Patent Description:
For example, when temporospatial information including a position and a time of an automobile which is within a predetermined area on a map is retrieved, the map information is partitioned in rectangles (meshes) defined in advance and the temporospatial information of the automobile which is within an area designated with the rectangle is acquired in the related art. At this time, a technology for retrieving temporospatial information as a <NUM>-dimensional bit string at a high speed is disclosed (see NPL <NUM>).

<CIT> discloses a vehicle position calculation apparatus to correct a vehicle position to be located on a map route. The vehicle position calculation apparatus has a vehicle position measuring section measuring a vehicle position, a road data supply section supplying road geometrical data including a line segment and a closed region correlated with a road on a map, and a vehicle position correcting section correcting the vehicle position on the map by using the road geometrical data. The position correcting section locates the vehicle position by itself on the map as a corrected vehicle position, in response to a relatively positional relation between the vehicle position and the road geometrical data. In such a correction, the vehicle position correcting section can correct the vehicle position to be in alignment with a point on corresponding one of position correction shapes, or it can correct the vehicle position onto a traveling link generated in response to the road geometrical data.

<CIT> discloses a map display system comprising a display means, a map DB, node and links, a road network DB which has a width information of link, a network polygon formation means which polygonizes link based on corresponding width information, a position detection means, a trajectory information storage means which stores the existing position information as a trajectory information, a trajectory information polygon formation means which polygonizes the trajectory information based on predetermined virtual width information, a map matching means to compare polygonized link with polygonized trajectory information, and to match the trajectory information on link and node, a map depiction means to draw a map information displayed on the display means.

<CIT> discloses automatic preparation of road data in which roads and intersections are expressed by polygons that show accurate agreement with the complicated road shapes on city maps. In simple polygon preparation processing, the respective line segments of road network data in which roads are expressed as line segments are expanded in the direction of the width dimension, thus producing simple road polygon data which has a width that is slightly greater than the width of the roads in the city map data. Next, in scissors data preparation processing, scissors data which defines the outlines of roads is prepared from the city map data by connecting shape lines in the vicinity of roads. Next, in road polygon preparation processing, road polygon data which shows good agreement with the shapes of roads in the city map data is prepared by trimming the simple road polygons along the road outlines defined by the scissors data.

<CIT> discloses a method and an apparatus for gathering probe data and using the gathered data to establish vehicle lane speed patterns for a plurality of lanes along a road segment. For this purpose, probe data are map-matched to a road segment, and further map-matched to individual lanes of the road segment.

However, according to the technology of the related art, it is difficult to perform retrieval of temporospatial information with high accuracy in some cases. For example, it is difficult to accurately retrieve temporospatial information of an automobile which is within an area designated with a polygon on a specific road within the area designated by a rectangle.

The present invention has been devised in view of the foregoing circumstances and an objective of the present invention is to perform retrieval of temporospatial information with high accuracy.

To solve the above-described problem and achieve the objective, the present invention provides a polygon retrieving method, in accordance with claim <NUM>.

According to the present invention, it is possible to perform retrieval of temporospatial information with high accuracy.

The present invention is not limited to the embodiment. In the description of the drawings, the same reference numerals are given to the same units.

[Configuration of polygon retrieving device] <FIG> is a schematic diagram illustrating an overall configuration of a polygon retrieving device according to an embodiment. As exemplified in <FIG>, a polygon retrieving device <NUM> according to the embodiment is realized by a general-purpose computer such as a PC and includes an input unit <NUM>, an output unit <NUM>, a communication control unit <NUM>, a storage unit <NUM>, and a control unit <NUM>.

The input unit <NUM> is realized using an input device such as a keyboard or a mouse and inputs various kinds of instruction information such as a processing start to the control unit <NUM> in response to an input operation performed by an operator. The output unit <NUM> is realized by a display device such as a liquid crystal display, a printing device such as a printer, or the like. For example, a result of a polygon retrieving process to be described below is displayed on the output unit <NUM>.

The communication control unit <NUM> is realized by a network interface card (NIC) or the like and controls communication between the control unit <NUM> and an external device via an electrical communication line such as a local area network (LAN) or the Internet. For example, the communication control unit <NUM> controls communication between the control unit <NUM> and a management device or the like that manages map information, temporospatial information, and the like to be described below.

The storage unit <NUM> is realized by a semiconductor memory element such as a random access memory (RAM) or a flash memory or a storage device such as a hard disk or an optical disc. The storage unit <NUM> stores a processing program for operating the polygon retrieving device <NUM>, data used during execution of the processing program, and the like in advance or temporarily every time processing is performed. The storage unit <NUM> may be configured to communicate with the control unit <NUM> via the communication control unit <NUM>.

In the embodiment, the storage unit <NUM> stores map information 14a, polygonal information 14b, temporospatial information 14c, and the like. The information is collected or generated and stored in the storage unit <NUM> earlier than a polygon retrieving process to be described below.

For example, an acquisition unit 15a to be described below collects the map information 14a from the management device or the like that manages the map information and stores the map information 14a in the storage unit <NUM>. According to the invention, the acquisition unit 15a collects the temporospatial information 14c from the management device that manages temporospatial information output from a sensor and stores the temporospatial information 14c in the storage unit <NUM>. A conversion unit 15b to be described below generates the polygonal information 14b and stores the polygonal information 14b in the storage unit <NUM>.

These various kinds of information are not limited to a case in which the information is stored in the storage unit <NUM> of the polygon retrieving device <NUM>. For example, the information may be collected or generated when a polygon retrieving process to be described below is performed.

The map information 14a includes coordinates of a representative point of a polygonal area on a map. For example, the map information 14a is information that includes coordinates of a central point of a polygonal area on a road and expresses the shape of the road on a map using a list of the coordinates of a road center, a road width, or the like.

Here, <FIG> is a diagram illustrating a data structure of the map information 14a. In <FIG>, the map information 14a indicating a shape of a road is exemplified. As illustrated in <FIG>, the map information 14a indicating the shape of the road includes a road center coordinate list, a road width, and the number of lanes. The road center coordinate list is a list of coordinates of a road center. An example illustrated in <FIG> expresses a shape of a road in which the coordinates of a central point of a road are (<NUM>, <NUM>), (<NUM>, <NUM>) and the like, a road width is <NUM>, and the number of lanes of the road is <NUM>.

The polygonal information 14b is information indicating that the coordinates of vertexes of a polygonal area are used to express the polygonal area within a predetermined unit area on a map and is information generated by the conversion unit 15b to be described below and associated with the unit area.

Specifically, <FIG> is a diagram illustrating a data structure of the polygonal information 14b. In the polygonal information 14b illustrated in <FIG>, a polygon vertex list and a space mesh are associated with each other. The polygon vertex list is a set of coordinates of vertexes of a polygonal area on a map. In <FIG>, coordinates of vertexes of a polygonal area such as (<NUM>, <NUM>), (<NUM>, <NUM>) are enumerated. The space mesh is information for identifying the unit area of a rectangle defined on the map (hereinafter referred to as a mesh ID). In <FIG>, mesh number <NUM> is exemplified.

The temporospatial information 14c is information in the form of sensor values including positional information and temporal information and is, for example, information indicating a travel position of an automobile. In the embodiment, the temporospatial information is a <NUM>-dimensional bit string including positional information and temporal information.

Specifically, <FIG> is a diagram illustrating a data structure of the temporospatial information 14c. The temporospatial information 14c exemplified in <FIG> includes a time serving as temporal information, longitude and latitude serving as positional information, and a data portion such as a sensor value. In <FIG>, the temporospatial information 14c indicating a <NUM>-dimensional bit string of a time "<NUM>/<NUM>/<NUM><NUM>:<NUM>:<NUM>", a longitude "<NUM>°", a latitude "-<NUM>°", and a data portion "data1" is exemplified.

The description will now return to <FIG>. The control unit <NUM> is realized using a central processing unit (CPU) and the like and executes a processing program stored in a memory. Thus, as exemplified in <FIG>, the control unit <NUM> functions as an acquisition unit 15a, a conversion unit 15b, a specifying unit 15c, and an extraction unit 15d. All or some of the functional units may be mounted in different hardware. The control unit <NUM> may include other functional units.

The acquisition unit 15a collects the map information 14a from the management device or the like that manages the map information via the input unit <NUM> or the communication control unit <NUM> and stores the map information 14a in the storage unit <NUM>. According to the invention, the acquisition unit 15a collects the temporospatial information 14c from a management device that manages the temporospatial information output from a sensor via the input unit <NUM> or the communication control unit <NUM> and stores the temporospatial information 14c in the storage unit <NUM>.

According to an example not falling under the scope of the present invention, the acquisition unit 15a may transmit such information to the conversion unit 15b or the specifying unit 15c to be described below without storing the information in the storage unit <NUM>.

The conversion unit 15b converts a polygonal area within the predetermined unit area on a map into the polygonal information 14b indicated using coordinates of vertexes of the polygonal area and stores the polygonal information in the storage unit <NUM> in association with the unit area.

Specifically, the conversion unit 15b converts the polygonal area into the polygonal information 14b indicating a polygonal area using the map information 14a including coordinates of a representative point of the polygonal area.

Here, <FIG> is a diagram illustrating a process of the conversion unit 15b. As illustrated in <FIG>, the conversion unit 15b specifies a central line of a road by connecting coordinates of the center of the road with reference to the map information 14a and specifies coordinates of vertexes of a polygonal area expressed on the road using a road width and the number of lanes. In <FIG>, polygonal information expressed by coordinates of vertexes of four polygonal areas indicating four lanes on a road is exemplified.

The conversion unit 15b converts the polygonal area within the unit area into the polygonal information 14b indicated by a set of the coordinates of the vertexes of the polygonal area for each rectangular unit area identified with a mesh ID defined on the map and stores the polygonal information 14b in the storage unit <NUM> in association with the mesh ID. In an example not falling under the scope of the present invention, the conversion unit 15b may transmit the polygonal information 14b to the extraction unit 15d to be described below without storing the polygonal information 14b in the storage unit <NUM>.

The description will now return to <FIG>. The specifying unit 15c specifies the temporospatial information 14c including the positional information corresponding to the coordinates within the predetermined area on the map. Specifically, the specifying unit 15c retrieves and specifies the temporospatial information 14c including the positional information corresponding to the coordinates within the unit area for each mesh ID.

The extraction unit 15d extracts the temporospatial information 14c including the positional information corresponding to the coordinates inside the polygonal area indicated by the polygonal information 14b associated with the unit area among the temporospatial information 14c specified by the specifying unit 15c.

Specifically, the extraction unit 15d extracts the temporospatial information 14c corresponding to the inside of the polygonal area within the unit area among the temporospatial information 14c specified by the specifying unit 15c with reference to the polygonal information 14b for each mesh ID. For example, the extraction unit 15d extracts the temporospatial information 14c including the positional information corresponding to the coordinates inside the polygonal area indicated by the polygonal information using the geometric algorithm information. In this case, the extraction unit 15d applies, for example, points-in-polygon (PIP) processing using a geometric algorithm library and determines whether the coordinates of the temporospatial information 14c on the map are inside the polygonal area indicated by the polygonal information.

The extraction unit 15d outputs the extracted temporospatial information 14c. For example, the extraction unit 15d may output the extracted temporospatial information 14c to the output unit <NUM> or an application such as automated driving or route guidance. Thus, the user can further detect the temporospatial information inside the polygonal area among the temporospatial information within the rectangular unit area defined on the map with high accuracy.

[Polygon retrieving process] Next, a polygon retrieving process performed by the polygon retrieving device <NUM> according to the embodiment will be described with reference to <FIG> is a flowchart illustrating an order of the polygon retrieving process. The flowchart of <FIG> starts at, for example, a timing at which the user performs an input operation of giving a start instruction.

First, before the flowchart of <FIG> starts, the conversion unit 15b converts the polygonal area within the rectangular unit area identified with the mesh ID defined on the map into the polygonal information 14b indicated using the coordinates of the vertexes of the polygonal area. For example, the conversion unit 15b converts the polygonal area into the polygonal information 14b indicating the polygonal area using the map information 14a including the coordinates of the representative point of the polygonal area. The conversion unit 15b stores the converted polygonal information 14b in the storage unit <NUM> in association with the mesh ID of the unit area.

When the flowchart starts, the specifying unit 15c specifies the temporospatial information 14c including the positional information corresponding to the coordinates within the predetermined unit area on the map (step S1). Specifically, for the temporospatial information 14c collected by the acquisition unit 15a, the specifying unit 15c retrieves and specifies the temporospatial information 14c including the positional information corresponding to the coordinates within the unit area for each mesh ID.

Subsequently, the extraction unit 15d extracts the temporospatial information 14c including the positional information corresponding to the coordinates inside the polygonal area indicated by the polygonal information 14b associated with the unit area among the temporospatial information 14c specified by the specifying unit 15c (step S2). Specifically, the extraction unit 15d extracts the temporospatial information 14c inside the polygonal area within the unit area among the temporospatial information 14c specified by the specifying unit 15c with reference to the polygonal information 14b for each mesh ID.

The extraction unit 15e outputs the extracted temporospatial information 14c to the output unit <NUM> or the application such as automated driving or route guidance (step S3). Then, the series of the polygon retrieving process ends.

As described above, in the polygon retrieving device <NUM> according to the embodiment, the conversion unit 15b converts the polygonal area within the predetermined unit area on the map into the polygonal information 14b indicated using the coordinates of the vertexes of the polygonal area and stores the polygonal information 14b in the storage unit <NUM> in association with the unit area. Specifically, the conversion unit 15b converts the polygonal area into the polygonal information 14b indicating the polygonal area using the map information 14a including the coordinates of the representative point of the polygonal area.

The specifying unit 15c specifies the temporospatial information 14c including the positional information corresponding to the coordinates within the predetermined unit area on the map. The extraction unit 15d extracts the temporospatial information 14c including the positional information corresponding to the coordinates inside the polygonal area indicated by the polygonal information 14b associated with the unit area among the specified temporospatial information 14c. Specifically, the extraction unit 15d extracts the temporospatial information 14c including the positional information corresponding to the coordinates inside the polygonal area indicated by the polygonal information 14b using the geometric algorithm information.

Thus, the polygon retrieving device <NUM> can further detect temporospatial information inside a polygonal area among temporospatial information within a rectangular unit area defined on a map. For example, the polygon retrieving device <NUM> can detect an automobile which is on a specific road. In this way, through the polygon retrieving process of the polygon retrieving device <NUM>, it is possible to retrieve temporospatial information with high accuracy.

The temporospatial information 14c is a <NUM>-dimensional bit string including positional information and temporal information. Thus, through the polygon retrieving process, it is possible to retrieve temporospatial information at a higher speed.

[Program] It is also possible to generate a program in which a process performed by the polygon retrieving device <NUM> according to the foregoing embodiment is described in a computer-executable language. As an embodiment, the polygon retrieving device <NUM> can be mounted by installing a polygon retrieving program that performs the foregoing polygon retrieving process on a desired computer as package software or online software. For example, by causing an information processing device to perform the foregoing polygon retrieving program, it is possible to cause the information processing device to function as the polygon retrieving device <NUM>. The information processing device mentioned here includes a desktop or notebook type personal computer. In addition, a mobile communication terminal such as a smartphone, a mobile phone, or a personal handyphone system (PHS) and a slate terminal such as a personal digital assistant (PDA) are included in the category of the information processing device. A function of the polygon retrieving device <NUM> may be mounted on a cloud server.

<FIG> is a diagram illustrating an example of a computer that executes the polygon retrieving program. A computer <NUM> includes, for example, a memory <NUM>, a CPU <NUM>, a hard disk drive interface <NUM>, a disk drive interface <NUM>, a serial port interface <NUM>, a video adapter <NUM>, and a network interface <NUM>. These units are connected by a bus <NUM>.

The memory <NUM> includes a read-only memory (ROM) <NUM> and a RAM <NUM>. The ROM <NUM> stores, for example, a boot program such as a basic input output system (BIOS). The hard disk drive interface <NUM> is connected to a hard disk drive <NUM>. The disk drive interface <NUM> is connected to a disk drive <NUM>. For example, a detachably mounted storage medium such as a magnetic disk or an optical disc is inserted into the disk drive <NUM>. For example, a mouse <NUM> and a keyboard <NUM> are connected to the serial port interface <NUM>. For example, a display <NUM> is connected to the video adapter <NUM>.

Here, the hard disk drive <NUM> stores, for example, an OS <NUM>, an application program <NUM>, a program module <NUM>, and program data <NUM>. The information described in the foregoing embodiment is stored in, for example, the hard disk drive <NUM> or the memory <NUM>.

The polygon retrieving program is stored as, for example, the program module <NUM> in which an instruction performed by the computer <NUM> is described in the hard disk drive <NUM>. Specifically, the program module <NUM> in which each process performed by the polygon retrieving device <NUM> described in the foregoing embodiment is described is stored in the hard disk drive <NUM>.

Data used for information processing by the polygon retrieving program is stored as the program data <NUM> in, for example, the hard disk drive <NUM>. The CPU <NUM> reads the program module <NUM> or the program data <NUM> stored in the hard disk drive <NUM> to the RAM <NUM> as necessary to perform each of the above-described procedures.

The program module <NUM> or the program data <NUM> related to the polygon retrieving program are not limited to a case in which the program module <NUM> or the program data <NUM> are stored in the hard disk drive <NUM>. For example, the program module <NUM> or the program data <NUM> may be stored in, for example, a detachably mounted storage medium to be read by the CPU <NUM> via the disk drive <NUM> or the like. Alternatively, the program module <NUM> or the program data <NUM> related to the polygon retrieving program may be stored in another computer connected via a network such as a LAN or a wide area network (WAN) to be read by the CPU <NUM> via the network interface <NUM>.

Claim 1:
A polygon retrieving method performed by a polygon retrieving device (<NUM>) including a storage unit (<NUM>), the polygon retrieving method comprising:
collecting temporospatial information (14c) from a management device that manages temporospatial information output from a sensor and storing the temporospatial information (14c) in the storage unit (<NUM>), wherein the temporospatial information (14c) is information comprising sensor values including positional information and temporal information;
converting one or more polygonal areas each indicating a shape of a respective lane of a road within a predetermined unit area on a map into polygonal information (14b) indicated using coordinates of vertexes of the polygonal area and storing the polygonal information (14b) in the storage unit (<NUM>) in association with the predetermined unit area;
specifying (S1) temporospatial information including positional information corresponding to coordinates within the predetermined unit area on the map, from among the stored temporospatial information (14c);
extracting (S2) temporospatial information including positional information corresponding to coordinates inside a polygonal area indicated by the polygonal information (14b) associated with the predetermined unit area among the specified temporospatial information; and
outputting (S3) the extracted temporospatial information that is associated with the predetermined unit area on the map.