Patent Description:
There is a polygon inside/outside determination technology for determining whether a specific coordinate is included inside a specific polygon. The polygon inside/outside determination technology is applied, for example, in a case where whether a geographical coordinate of an automobile, or the like, is included in a polygon which expresses a road area is determined.

Examples of the polygon inside/outside determination technology in related art can include determination technologies using a Crossing Number method and a Winding Number method (see, for example, Non-Patent Literature <NUM>). These determination technologies determine whether a coordinate is included inside a polygon by calculating positional relationship between all sides of the polygon to be determined and a coordinate to be determined.

Further, examples of the polygon inside/outside determination technology in related art can include a simple determination technology using a bounding container (see, for example, Non-Patent Literature <NUM>). This bounding container is such a figure that includes a polygon to be determined. This technology reduces average processing time by selecting a figure which enables high-speed execution of inside/outside determination as the bounding container and applying the Crossing Number method and the Winding Number method only to coordinates included in the bounding container. A rectangle (MBR: Minimal Bounding Rectangle) having sides parallel to an XY axis is typically used as the above-described bounding container.

<CIT> describes that in order to advance a game at high speed by reducing a calculating amount and shortening processing time, the area of a quarter view displayed parallelogram observed from a view position upper than a horizontal plane is made into a rectangle by moving the coordinates of respective apexes together with any arbitrary position so that the X axis component and the Y axis component of each side can be the same, and rotated together with the arbitrary position so that two sides of the rectangle can be parallel with an X axis and by comparing the apex coordinates of the rotated rectangle with the coordinates of the arbitrary position, it is decided whether the arbitrary position is inside or outside the area of the quarter view displayed parallelogram.

In a case where the polygon inside/outside determination technology is applied to determination as to whether or not a geographical automobile, or the like, is included in a road area, this polygon has a number of vertexes and has an elongated shape to express the road area.

However, the Crossing Number method and the Winding Number method have a problem that if determination is performed on a polygon having a number of vertexes, processing time becomes longer, because the processing time is proportional to the number of vertexes. Further, the MBR has a problem that if determination is performed on a polygon having an elongated shape, average processing time is less likely to be shortened, because the MBR also includes many regions outside the elongated polygon.

The present invention has been made in view of the above, and an object of the present invention is to provide a preprocessing device, a determination system, a preprocessing method, and a preprocessing program which can shorten processing time required for polygon inside/outside determination processing.

To solve the above-described problems and achieve the object, a preprocessing device of the present invention is as set out in Claim <NUM>.

Further, a determination system of the present invention is as set out in Claim <NUM>.

Further, a preprocessing method of the present invention is as set out in Claim <NUM>.

Further, a preprocessing program of the present invention is as set out in Claim <NUM>.

According to the present invention, it is possible to shorten processing time required for polygon inside/outside determination processing.

A preprocessing device described herein includes a reduction unit configured to acquire coordinate information of respective vertexes of a polygon for inside/outside determination and reduce the vertexes of the polygon for inside/outside determination as preprocessing of determination processing of determining whether a coordinate to be determined exists inside or outside the polygon for inside/outside determination, and an output unit configured to output the coordinate information of the respective vertexes of the polygon after the vertexes are reduced by the reduction unit, to a device which performs the determination processing.

Further, a determination system described herein includes a determination device configured to determine whether a coordinate to be determined exists inside or outside a polygon for inside/outside determination, and a first preprocessing device configured to perform preprocessing of determination processing, the first preprocessing device including a reduction unit configured to acquire coordinate information of respective vertexes of the polygon for inside/outside determination and perform first preprocessing of reducing the vertexes of the polygon for inside/outside determination and an output unit configured to output reduced polygon information which is the coordinate information of the respective vertexes of the polygon after the vertexes are reduced by the reduction unit, the determination device determining whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination using information after the preprocessing.

Further, a preprocessing method described herein is a preprocessing method to be performed by a preprocessing device, the preprocessing method including a step of acquiring coordinate information of respective vertexes of a polygon for inside/outside determination and reducing the vertexes of the polygon for inside/outside determination as preprocessing of determination processing of determining whether a coordinate to be determined exists inside or outside the polygon for inside/outside determination, and a step of outputting the coordinate information of the respective vertexes of the polygon after the vertexes are reduced, to a device which performs the determination processing.

Further, a preprocessing program described herein causes a computer to execute a step of acquiring coordinate information of respective vertexes of a polygon for inside/outside determination and reducing the vertexes of the polygon for inside/outside determination as preprocessing of determination processing of determining whether a coordinate to be determined exists inside or outside the polygon for inside/outside determination, and a step of outputting the coordinate information of the respective vertexes of the polygon after the vertexes are reduced, to a device which performs the determination processing.

Background Examples and Embodiments of a preprocessing device, a determination system, a preprocessing method and a preprocessing program according to the present invention will be described in detail below on the basis of the drawings. Further, the present invention is not limited to the embodiments described below.

[First background example] First, a first background example useful for understanding the present invention will be described. In the first background example, processing time required for inside/outside determination processing is shortened by reducing vertexes of a polygon for inside/outside determination before the inside/outside determination processing of determining whether a coordinate to be determined exists inside or outside the polygon for inside/outside determination.

[Configuration of determination system] <FIG> is a block diagram illustrating an example of a configuration of a determination system according to the first background example. As illustrated in <FIG>, a determination system <NUM> according to the first background example includes a client terminal <NUM>, an inside/outside determination control device <NUM>, a vertex reduction device <NUM>, and a determination device <NUM>. The client terminal <NUM> is connected to the inside/outside determination control device <NUM> via a network, or the like. The inside/outside determination control device <NUM> is connected to the vertex reduction device <NUM> and the determination device <NUM> via a network, or the like.

The client terminal <NUM> is a terminal device to be used by a user of the determination system <NUM>. The client terminal <NUM> transmits coordinate information D20 of a coordinate to be determined and polygon information D10 which is coordinate information of respective vertexes of a polygon for inside/outside determination to the inside/outside determination control device <NUM> and requests determination.

The inside/outside determination control device <NUM> is a server device which controls processing at the vertex reduction device <NUM> and the determination device <NUM>. In a case where the inside/outside determination control device <NUM> receives a request for determination from the client terminal <NUM>, the inside/outside determination control device <NUM> causes the determination device <NUM> to execute inside/outside determination processing (determination processing) of determining whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination and returns a determination result to the client terminal <NUM>. Further, in the present first background example <NUM>, the inside/outside determination control device <NUM> causes the vertex reduction device <NUM> to execute preprocessing of the inside/outside determination processing before the determination device <NUM> executes the inside/outside determination processing.

The vertex reduction device <NUM> receives the polygon information D10 from the inside/outside determination control device <NUM> and executes preprocessing of reducing vertexes of the polygon for inside/outside determination. The vertex reduction device <NUM> outputs reduced polygon information D11 which is coordinate information of the respective vertexes of the polygon after the vertexes are reduced, to the inside/outside determination control device <NUM>.

The determination device <NUM> performs inside/outside determination processing of determining whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination. In this event, the determination device <NUM> performs the inside/outside determination processing on the basis of the reduced polygon information D11 and the coordinate information D20 of the coordinate to be determined. The determination device <NUM> outputs determination information including a determination result to the inside/outside determination control device <NUM>.

[Vertex reduction device] The vertex reduction device <NUM> illustrated in <FIG> will be described next. <FIG> is a block diagram illustrating an example of a configuration of the vertex reduction device <NUM> illustrated in <FIG>. As illustrated in <FIG>, the vertex reduction device <NUM> includes a communication unit <NUM>, a storage unit <NUM> and a control unit <NUM>.

The communication unit <NUM> is a communication interface which transmits/receives various kinds of information to and from other devices connected via a network, or the like. The communication unit <NUM> is implemented with a NIC (Network Interface Card), or the like, and performs communication between other devices and the control unit <NUM> (which will be described later) via a telecommunication line such as a LAN (Local Area Network) and the Internet.

The communication unit <NUM> receives the polygon information D10 from the inside/outside determination control device <NUM> via a network. Further, the communication unit <NUM> transmits the reduced polygon information D11 to the inside/outside determination control device <NUM>.

The storage unit <NUM> is implemented with a semiconductor memory device such as a RAM (Random Access Memory) and a flash memory, or a storage device such as a hard disk and an optical disk and stores a processing program for causing the vertex reduction device <NUM> to operate, data to be used while the processing program is executed, or the like. The storage unit <NUM> stores the polygon information D10 and the reduced polygon information D11.

The polygon information D10 is coordinate information of the respective vertexes of the polygon for inside/outside determination. The polygon information D10 is transmitted from the inside/outside determination control device <NUM>. <FIG> is a view illustrating a list of data configurations of the polygon information D10. As illustrated in <FIG>, the polygon information D10 is a list of coordinates of the vertexes of the polygon for inside/outside determination, and, for example, has <NUM> sets of coordinates in a case where the polygon for inside/outside determination has <NUM> vertexes.

The reduced coordinate information D11 is coordinate information of the respective vertexes of the polygon whose vertexes are reduced through processing performed by the vertex reduction unit <NUM> (which will be described later) on the respective vertexes of the polygon for inside/outside determination. The reduced coordinate information D11 is, for example, a list of coordinates of the respective vertexes of the polygon whose vertexes are reduced from <NUM> to <NUM>.

The control unit <NUM> controls the whole of the vertex reduction device <NUM>. The control unit <NUM> is, for example, an electronic circuit such as a CPU (Central Processing Unit) and an MPU (Micro Processing Unit), or an integrated circuit such as an ASIC (Application Specific Integrated Circuit) and an FPGA (Field Programmable Gate Array). Further, the control unit <NUM> includes an internal memory for storing a program which specifies various kinds of processing procedure, and control data, and executes respective kinds of processing using the internal memory. The control unit <NUM> functions as various kinds of processing units by various kinds of programs running. The control unit <NUM> includes a vertex reduction unit <NUM> (reduction unit).

The vertex reduction unit <NUM> acquires the polygon information D10 and reduces the vertexes of the polygon for inside/outside determination as preprocessing of the inside/outside determination processing. The vertex reduction unit <NUM> performs processing of thinning the vertexes of the polygon for inside/outside determination at appropriate intervals. For example, the vertex reduction unit <NUM> implements vertex reduction processing using algorithm of Ramer-Douglas-Peucker (see, for example, Reference Literature <NUM>).

The vertex reduction unit <NUM> stores the reduced coordinate information D11 which is coordinate information of the respective vertexes of the polygon whose vertexes are reduced through vertex reduction processing performed on the respective vertexes of the polygon for inside/outside determination, in the storage unit <NUM> and outputs the reduced coordinate information D11 to the inside/outside determination control device <NUM> through the communication unit <NUM>.

[Determination device] The determination device <NUM> illustrated in <FIG> will be described next. <FIG> is a block diagram illustrating an example of a configuration of the determination device <NUM> illustrated in <FIG>. As illustrated in <FIG>, the determination device <NUM> includes a communication unit <NUM>, a storage unit <NUM>, and a control unit <NUM>.

The communication unit <NUM>, which is a communication interface which transmits/receives various kinds of information to/from other devices connected via a network, or the like, is implemented with an NIC, or the like, and performs communication between other devices and the control unit <NUM> (which will be described later) via a telecommunication line such as a LAN and the Internet. The communication unit <NUM> receives the reduced polygon information D11 and receives the coordinate information D20 from the inside/outside determination control device <NUM> via a network as the coordinate information of the respective vertexes of the polygon for inside/outside determination. Further, the communication unit <NUM> transmits a determination result of the inside/outside determination unit <NUM> (which will be described later) to the inside/outside determination control device <NUM>.

The storage unit <NUM> is implemented with a semiconductor memory device such as a RAM and a flash memory, or a storage device such as a hard disk and an optical disk and stores a processing program for causing the determination device <NUM> to operate, data to be used during execution of the processing program, or the like. The storage unit <NUM> stores the reduced polygon information D11 and the coordinate information D20.

The coordinate information D20 is coordinate information of the coordinate to be determined. The coordinate information D20 is transmitted from the inside/outside determination control device <NUM>. <FIG> is a view illustrating a list of data configurations of the coordinate information D20. As illustrated in <FIG>, the coordinate information D20 indicates longitude and latitude of the coordinate to be determined.

The control unit <NUM> controls the whole of the vertex reduction device <NUM>. The control unit <NUM> is, for example, an electronic circuit such as a CPU and an MPU or an integrated circuit such as an ASIC and an FPGA. Further, the control unit <NUM> includes an internal memory for storing a program which specifies various kinds of processing procedure, and control data, and executes respective kinds of processing using the internal memory. Further, the control unit <NUM> functions as various kinds of processing units by various kinds of programs running. The control unit <NUM> functions as the inside/outside determination unit <NUM>.

The inside/outside determination unit <NUM> performs inside/outside determination processing which determines whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination on the basis of the reduced polygon information D11 and the coordinate information D20 The inside/outside determination unit <NUM> executes detailed determination using the Crossing Number method or the Winding Number method after simple determination using the MBR.

[Vertex reduction processing] The vertex reduction processing to be executed by the vertex reduction device <NUM> will be specifically described next. <FIG> is a view for explaining the vertex reduction processing. (<NUM>) of <FIG> indicates a polygon P10 for inside/outside determination before the vertex reduction processing. (<NUM>) of <FIG> indicates a polygon P11 after the vertex reduction processing. <FIG> also indicates an MBR <NUM> and coordinates C1, C2 and C3 to be determined for explanation.

The polygon P10 illustrated in (<NUM>) of <FIG> has <NUM> vertexes. The vertex reduction unit <NUM> of the vertex reduction device <NUM> reduces the vertexes of the polygon P10 using algorithm of Ramer-Douglas-Peucker. The algorithm of Ramer-Douglas-Peucker is algorithm of (A) setting a starting point and an end point of a route as plot targets, (B) obtaining distances between a line connecting the plot targets and respective points between the plot targets to find a point which is separate by equal to or greater than an allowable distance and which is the farthest point, (C) setting the point as a new plot target, recursively repeating processing of (B) and (C), and (D) ending if there is no point which is separate by equal to or greater than ε.

Through this processing, the vertex reduction unit <NUM> generates the polygon P11 whose vertexes are reduced to <NUM> compared to the polygon P10 having <NUM> vertexes as illustrated in (<NUM>) of <FIG>. Then, the determination device <NUM> performs determination processing using this polygon P11 as the polygon for inside/outside determination.

In this case, detailed determination is executed on the coordinates C2 and C3 for which it is necessary to perform detailed determination on the basis of the polygon P11 whose vertexes are reduced, so that it is possible to shorten processing time for detailed determination processing compared to a case where detailed determination is performed on the original polygon P10 for inside/outside determination. Note that the coordinate C1 is located outside the MBR <NUM>, and thus, determination ends after only the simple determination is performed.

[Processing procedure of determination processing] Processing procedure of determination processing in the determination system <NUM> will be described next. <FIG> is a sequence diagram for explaining processing procedure of the determination processing by the determination system <NUM> illustrated in <FIG>.

First, the client terminal <NUM> transmits the coordinate information D20 of the coordinate to be determined and the polygon information D10 which is coordinate information of the respective vertexes of the polygon for inside/outside determination to the inside/outside determination control device <NUM> and requests determination (step S1). When the inside/outside determination control device <NUM> receives the request for determination, the inside/outside determination control device <NUM> transmits the polygon information D10 to the vertex reduction device <NUM> (step S2) and causes the vertex reduction device <NUM> to execute preprocessing.

The vertex reduction device <NUM> executes the vertex reduction processing of reducing the vertexes of the polygon for inside/outside determination on the basis of the polygon information D10 received from the inside/outside determination control device <NUM> as the preprocessing (step S3) and transmits the reduced polygon information D11 to the inside/outside determination control device <NUM> (step S4).

The inside/outside determination control device <NUM> transmits the reduced polygon information D11 and the coordinate information D20 to the determination device <NUM> (step S5) and causes the determination device <NUM> to execute inside/outside determination processing. The inside/outside determination control device <NUM> performs the inside/outside determination processing on the basis of the reduced polygon information D11 and the coordinate information D20 (step S6) and transmits determination information to the inside/outside determination control device <NUM> (step S7). The inside/outside determination control device <NUM> transmits the determination information to the client terminal <NUM> (step S8).

[Processing procedure of vertex reduction processing] Processing procedure of the vertex reduction processing (step S3) will be described next. <FIG> is a flowchart illustrating the processing procedure of the vertex reduction processing illustrated in <FIG>.

As illustrated in <FIG>, when the vertex reduction device <NUM> accepts input of the polygon information D10 from the inside/outside determination control device <NUM> (step S11), the vertex reduction device <NUM> reduces the vertexes of the polygon for inside/outside determination (step S12). The vertex reduction device <NUM> generates the reduced polygon information D11, outputs the reduced polygon information D11 to the inside/outside determination control device <NUM> (step S13) and finishes the vertex reduction processing.

Processing procedure of the inside/outside determination processing (step S6) will be described next. <FIG> is a flowchart illustrating the processing procedure of the inside/outside determination processing illustrated in <FIG>.

As illustrated in <FIG>, the determination device <NUM> performs simple determination processing of determining whether or not the coordinate to be determined is located inside the MBR (step S21). In a case where the determination device <NUM> determines that the coordinate to be determined is not located inside the MBR (step S21: No), the determination device <NUM> determines that this coordinate is located outside the polygon for inside/outside determination ("false") (step S22).

On the other hand, in a case where the determination device <NUM> determines that the coordinate to be determined is located inside the MBR (step S21: Yes), the determination device <NUM> performs detailed determination using the Crossing Number method or the Winding Number method. In this case, the determination device <NUM> determines whether or not the coordinate to be determined is located inside the polygon for inside/outside determination using the polygon indicated in the reduced polygon information D11 as the polygon for inside/outside determination (step S23).

In a case where the determination device <NUM> determines that the coordinate to be determined is not located inside the polygon for inside/outside determination (step S23: No), the processing proceeds to step S22, and the determination device <NUM> determines that this coordinate is located outside the polygon for inside/outside determination ("false") (step S22).

In contrast, in a case where the determination device <NUM> determines that the coordinate to be determined is located inside the polygon for inside/outside determination (step S23: Yes), the determination device <NUM> determines that this coordinate is located inside the polygon for inside/outside determination ("true") (step S24).

The determination device <NUM> executes processing from step S21 to step S24 for each coordinate to be determined and transmits determination information associated with a determination result to the inside/outside determination control device <NUM> for each coordinate to be determined.

[Effects of first background example] In this manner, in the first background example, the preprocessing of reducing the vertexes of the polygon for inside/outside determination is performed, and polygon inside/outside determination processing is performed on each coordinate using the polygon whose vertexes are reduced. Thus, in the first background example, detailed determination is executed on the basis of the polygon whose vertexes are reduced upon detailed determination processing, so that it is possible to shorten processing time of the detailed determination processing compared to a case where detailed determination is performed on the original polygon for inside/outside determination.

Particularly, in a case where the first background example is applied to determination as to whether a geographical coordinate of an automobile, or the like, is included in a polygon which expresses a road area, detailed determination processing is performed after vertexes of the polygon which has a number of vertexes and which expresses the road area are reduced in advance, so that it is possible to shorten processing time of the determination processing.

Note that in the first background example, the inside/outside determination control device <NUM> may cause the vertex reduction device <NUM> to reduce vertexes of the polygon for inside/outside determination in advance, store the polygon in a storage region of the inside/outside determination control device <NUM>, read out the polygon upon inside/outside determination and transmit the polygon to the determination device <NUM>.

[First embodiment] A first embodiment will be described next. In the first embodiment, processing time required for inside/outside determination processing is shortened by rotating the polygon for inside/outside determination and the coordinate to be determined before the inside/outside determination processing by the determination device and reducing a region of the MBR including the rotated polygon.

<FIG> is a block diagram illustrating an example of a configuration of a determination system according to the first embodiment. As illustrated in <FIG>, a determination system <NUM> according to the first embodiment includes a rotation device <NUM> (a preprocessing device, a first preprocessing device) in place of the vertex reduction device <NUM> compared to the determination system <NUM> illustrated in <FIG>.

The rotation device <NUM> receives the polygon information D10 and the coordinate information D20 from the inside/outside determination control device <NUM> and executes preprocessing of rotating the polygon for inside/outside determination and the coordinate to be determined. The rotation device <NUM> outputs rotated polygon information D12 which is coordinate information of respective vertexes of the rotated polygon and rotated coordinate information D22 which is coordinate information of the rotated coordinate to be determined, to the inside/outside determination control device <NUM>.

The determination device <NUM> performs inside/outside determination processing of determining whether the rotated coordinate to be determined exists inside or outside the rotated polygon for inside/outside determination on the basis of the rotated polygon information D12 and the rotated coordinate information D22.

[Rotation device] The rotation device <NUM> illustrated in <FIG> will be described next. <FIG> is a block diagram illustrating an example of a configuration of the rotation device <NUM> illustrated in <FIG>. As illustrated in <FIG>, the rotation device <NUM> includes a communication unit <NUM> (an output unit, a first output unit), a storage unit <NUM>, and a control unit <NUM>.

The communication unit <NUM> has functions similar to the functions of the communication unit <NUM> in the vertex reduction device <NUM>. The communication unit <NUM> receives the polygon information D10 and the coordinate information D20 from the inside/outside determination control device <NUM> via a network. Further, the communication unit <NUM> transmits the rotated polygon information D12 and the rotated coordinate information D22 generated through the rotation processing performed by a rotation unit <NUM> (which will be described later) on the polygon for inside/outside determination and the coordinate to be determined, to the inside/outside determination control device <NUM>.

The storage unit <NUM> has functions similar to the functions of the storage unit <NUM> in the vertex reduction device <NUM> The storage unit <NUM> stores the polygon information D10, the coordinate information D20, the rotated polygon information D12 and the rotated coordinate information D22.

The control unit <NUM> has functions similar to the functions of the control unit <NUM> in the vertex reduction device <NUM> The control unit <NUM> includes the rotation unit <NUM>.

The rotation unit <NUM> acquires the polygon information D10 and the coordinate information D20 and rotates the polygon for inside/outside determination and the coordinate to be determined as preprocessing of inside/outside determination processing. For example, the rotation unit <NUM> implements rotation processing using algorithm for deriving a rotation angle (see, for example, Reference Literature <NUM>), or the like.

The rotation unit <NUM> stores the rotated polygon information D12 and the rotated coordinate information D22 in the storage unit <NUM> and outputs the rotated polygon information D12 and the rotated coordinate information D22 to the inside/outside determination control device <NUM> via the communication unit <NUM>.

[Rotation processing] Rotation processing to be executed by the rotation device <NUM> will be specifically described next. <FIG> is a view for explaining the rotation processing. (<NUM>) of <FIG> indicates the polygon P10 for inside/outside determination and the coordinates C1, C2 and C3 to be determined before the rotation processing, and (<NUM>) of <FIG> indicates the polygon P11 after the rotation processing and rotated coordinates C12, C22 and C32. Further, <FIG> also indicates the MBR <NUM> before the rotation processing and an MBR <NUM> set after the rotation processing for explanation.

As illustrated in (<NUM>) of <FIG>, the MBR <NUM> for the polygon P10 has a substantially square shape including the coordinates C1 and C2. The rotation unit <NUM> of the rotation device <NUM> rotates the polygon P10 and the coordinates C1, C2 and C3 to be determined as appropriate using the algorithm for deriving a rotation angle.

Through this processing, as illustrated in (<NUM>) of <FIG>, the MBR <NUM> whose area is reduced compared to the MBR <NUM> can be set as the MBR including the rotated polygon P12 for inside/outside determination. Further, the coordinate C22 to be determined is located outside the new MBR <NUM> through rotation, and thus, determination on the coordinate C22 to be determined is finished after only simple determination is performed.

As a result of this, simple determination is performed using the MBR <NUM> whose area is reduced in the determination processing by the determination device <NUM>, and thus, more coordinates can be determined as being located outside the polygon for inside/outside determination only through simple determination so that it is possible to reduce the number of times of execution of detailed determination. In the example in <FIG>, only the coordinate C32 among the coordinates C12, C22 and C23 is to be subjected to detailed determination.

[Processing procedure of determination processing] Processing procedure of the determination processing in the determination system <NUM> will be described next. <FIG> is a sequence diagram for explaining the processing procedure of the determination processing by the determination system <NUM> illustrated in <FIG>.

Processing in step S31 illustrated in <FIG> is the same processing as the processing in step S1 illustrated in <FIG>. When the inside/outside determination control device <NUM> receives a request for determination, the inside/outside determination control device <NUM> transmits the polygon information D10 and the coordinate information D20 to the rotation device <NUM> (step S32) and causes the rotation device <NUM> to execute preprocessing.

The rotation device <NUM> executes rotation processing of rotating the polygon for inside/outside determination and the coordinate to be determined on the basis of the polygon information D10 and the coordinate information D20 received from the inside/outside determination control device <NUM> as the preprocessing (step S33). The rotation device <NUM> transmits rotated polygon information D12 and rotated coordinate information D22 to the inside/outside determination control device <NUM> (step S34).

The inside/outside determination control device <NUM> transmits the rotated polygon information D12 and the rotated coordinate information D22 to the determination device <NUM> (step S35) and causes the determination device <NUM> to execute inside/outside determination processing. The determination device <NUM> performs inside/outside determination processing of determining whether the rotated coordinate to be determined exists inside or outside the rotated polygon for inside/outside determination on the basis of the rotated polygon information D12 and the rotated coordinate information D22 (step S36). Note that the inside/outside determination processing is the same processing as the processing in step S6 illustrated in <FIG>. Further, processing in step S37 and S38 illustrated in <FIG> is the same processing as the processing in step S7 and S8 illustrated in <FIG>.

[Processing procedure of rotation processing] Processing procedure of the rotation processing (step S33) will be described next. <FIG> is a flowchart illustrating the processing procedure of the rotation processing illustrated in <FIG>.

As illustrated in <FIG>, when the rotation device <NUM> receives input of the polygon information D10 and the coordinate information D20 from the inside/outside determination control device <NUM> (step S41), the rotation device <NUM> rotates the polygon for inside/outside determination and the coordinate to be determined (step S42). The rotation device <NUM> generates the rotated polygon information D12 and the rotated coordinate information D22, outputs the rotated polygon information D12 and the rotated coordinate information D22 to the inside/outside determination control device <NUM> (step S43) and finishes the rotation processing.

[Effects of first embodiment] In this manner, in the first embodiment, preprocessing of rotating the polygon for inside/outside determination and the coordinate to be determined is performed, and polygon inside/outside determination processing is performed on each rotated coordinate to be determined using the MBR whose area is reduced compared to the MBR before the rotation. Thus, in the first embodiment, simple determination is performed using the MBR whose area is reduced, so that more coordinates can be determined as being located outside the polygon for inside/outside determination only through the simple determination. It is therefore possible to reduce the number of times of execution of detailed determination, so that it is possible to shorten the whole processing time of the determination processing in the first embodiment.

Note that in the first embodiment, the inside/outside determination control device <NUM> may cause the rotation device <NUM> to rotate the polygon for inside/outside determination and the coordinate to be determined in advance, store the rotated polygon for inside/outside determination and the rotated coordinate to be determined in a storage region of the inside/outside determination control device <NUM>, read out the rotated polygon for inside/outside determination and the rotated coordinate to be determined and transmit the rotated polygon for inside/outside determination and the rotated coordinate to be determined to the determination device <NUM> upon inside/outside determination.

[Second background example] A second background example useful for understanding the present invention will be described next. The second background example reduces processing time required for inside/outside determination processing by dividing the polygon for inside/outside determination into a plurality of polygons having small areas before the inside/outside determination processing by the determination device to reduce areas of respective MBRs for the divided polygons.

<FIG> is a block diagram illustrating an example of a configuration of a determination system according to the second background example. As illustrated in <FIG>, a determination system <NUM> according to the second background example includes a division device <NUM> (second preprocessing apparatus) in place of the vertex reduction device <NUM> compared to the determination system <NUM> illustrated in <FIG>.

The division device <NUM> receives the polygon information D10 from the inside/outside determination control device <NUM> and executes preprocessing of dividing the polygon for inside/outside determination. The division device <NUM> divides the polygon for inside/outside determination and outputs divided polygon information D13 including coordinate information of respective vertexes of the respective divided polygons, to the inside/outside determination control device <NUM>.

The determination device <NUM> performs inside/outside determination processing of determining whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination for each of the divided polygons for inside/outside determination on the basis of the divided polygon information D13 and the coordinate information D20.

[Division device] The division device <NUM> illustrated in <FIG> will be described next. <FIG> is a block diagram illustrating an example of a configuration of the division device <NUM> illustrated in <FIG>. As illustrated in <FIG>, the division device <NUM> includes a communication unit <NUM> (second output unit), a storage unit <NUM>, and a control unit <NUM>.

The communication unit <NUM> has functions similar to the functions of the communication unit <NUM> in the vertex reduction device <NUM>. The communication unit <NUM> receives the polygon information D10 from the inside/outside determination control device <NUM> via a network. Further, the communication unit <NUM> transmits divided polygon information D13 generated through division processing performed by a division unit <NUM> (which will be described later) on the polygon for inside/outside determination, to the inside/outside determination control device <NUM>.

The storage unit <NUM> has functions similar to the functions of the storage unit <NUM> in the vertex reduction device <NUM> The storage unit stores the polygon information D10 and the divided polygon information D13.

The control unit <NUM> has functions similar to the functions of the control unit <NUM> in the vertex reduction device <NUM> The control unit <NUM> includes the division unit <NUM>.

The division unit <NUM> acquires the polygon information D10 and divides the polygon for inside/outside determination into a plurality of polygons as preprocessing of the inside/outside determination processing. For example, the division unit <NUM> implements division processing using polygon triangulation algorithm (see, for example, Reference Literature <NUM>).

The division unit <NUM> stores the divided polygon information D13 which is coordinate information of respective vertexes of respective polygons divided through division processing on the polygon for inside/outside determination in the storage unit <NUM> and outputs the divided polygon information D13 to the inside/outside determination control device <NUM> via the communication unit <NUM>.

[Division processing] Division processing to be executed by the division device <NUM> will be specifically described next. <FIG> is a view for explaining the division processing. (<NUM>) of <FIG> indicates the polygon P10 for inside/outside determination before the division processing and the coordinates C1, C2 and C3 to be determined, and (<NUM>) of <FIG> indicates polygons P13-<NUM>, P13-<NUM> and P13-<NUM> after the division processing. Further, <FIG> also indicates the MBR <NUM>, MBRs <NUM>-<NUM>, <NUM>-<NUM> and <NUM>-<NUM> respectively for the divided polygons P13-<NUM>, P13-<NUM> and P13-<NUM> and the coordinates C1, C2 and C3 to be determined for explanation.

As illustrated in (<NUM>) of <FIG>, the MBR <NUM> for the polygon P10 has a substantially square shape including the coordinates C1 and C2. The division unit <NUM> of the division device <NUM> divides the polygon P10 into, for example, three polygons P13-<NUM>, P13-<NUM> and P13-<NUM> (see (<NUM>) of <FIG>) using the polygon triangulation algorithm.

Through this processing, the MBRs <NUM>-<NUM>, <NUM>-<NUM> and <NUM>-<NUM> can be set as MBRs respectively including the divided polygons P13-<NUM>, P13-<NUM> and P13-<NUM> for inside/outside determination as illustrated in (<NUM>) of <FIG>. As illustrated in (<NUM>) of <FIG>, areas of these MBRs <NUM>-<NUM>, <NUM>-<NUM> and <NUM>-<NUM> are reduced compared to the area of the MBR <NUM>. Further, as illustrated in (<NUM>) of <FIG>, the coordinate C2 to be determined located inside the MBR <NUM> is located outside the new MBRs <NUM>-<NUM>, <NUM>-<NUM> and <NUM>-<NUM>, and thus, determination on the coordinate C2 to be determined is finished after only simple determination is performed.

As a result, simple determination is performed using the MBRs <NUM>-<NUM>, <NUM>-<NUM> and <NUM>-<NUM> whose areas are reduced in the determination processing by the determination device <NUM>, and thus, more coordinates can be determined as being located outside the polygon for inside/outside determination only through the simple determination, so that it is possible to reduce the number of times of execution of detailed determination. In the example in <FIG>, only the coordinate C3 among the coordinates C1, C2 and C3 is to be subjected to detailed determination.

[Processing procedure of determination processing] Processing procedure of determination processing in the determination system <NUM> will be described next. <FIG> is a sequence diagram for explaining the processing procedure of the determination processing by the determination system <NUM> illustrated in <FIG>.

Processing in step S51 illustrated in <FIG> is the same processing as the processing in step S1 illustrated in <FIG>. When the inside/outside determination control device <NUM> receives a request for determination, the inside/outside determination control device <NUM> transmits the polygon information D10 to the division device <NUM> (step S52) and causes the division device <NUM> to execute preprocessing.

The division device <NUM> executes division processing of dividing the polygon for inside/outside determination into a plurality of polygons on the basis of the polygon information D10 received from the inside/outside determination control device <NUM> as the preprocessing (step S53). The division device <NUM> transmits divided polygon information D13 to the inside/outside determination control device <NUM> (step S54).

The inside/outside determination control device <NUM> transmits the divided polygon information D13 and the coordinate information D20 to the determination device <NUM> (step S55) and causes the determination device <NUM> to execute inside/outside determination processing. The determination device <NUM> performs inside/outside determination processing of determining whether the coordinate to be determined exists inside or outside the divided polygons for inside/outside determination for each of the divided polygons for inside/outside determination on the basis of the divided polygon information D13 and the coordinate information D20 (step S56). Note that the inside/outside determination processing is the same processing as the processing in step S6 illustrated in <FIG>. Further, processing in step S57 and S58 illustrated in <FIG> is the same processing as the processing in step S7 and S8 illustrated in <FIG>.

[Processing procedure of division processing] Processing procedure of the division processing (step S53) will be described next. <FIG> is a flowchart illustrating the processing procedure of the division processing illustrated in <FIG>.

As illustrated in <FIG>, when the rotation device <NUM> receives input of the polygon information D10 from the inside/outside determination control device <NUM> (step S61), the division device <NUM> divides the polygon for inside/outside determination into a plurality of polygons (step S62). The division device <NUM> generates the divided polygon information D13, outputs the divided polygon information D13 to the inside/outside determination control device <NUM> (step S63) and finishes the rotation processing.

[Effects of second background example] In this manner, in the second background example, preprocessing of dividing the polygon for inside/outside determination into a plurality of polygons is performed, and polygon inside/outside determination processing is performed on respective coordinates to be determined using a plurality of MBRs whose areas are reduced as a whole compared to the MBR for the polygon before division. Thus, in the second background example, simple determination is performed using a plurality of MBRs whose areas are reduced as a whole, and thus, more coordinates can be determined as being located outside the polygon for inside/outside determination only through the simple determination. By this means, in the second background example, the number of times of execution of detailed determination can be reduced, so that it is possible to shorten the whole processing time for determination processing.

Note that in the second background example, the inside/outside determination control device <NUM> may cause the division device <NUM> to divide the polygon for inside/outside determination into a plurality of polygons in advance, store the plurality of divided polygons in the storage region of the inside/outside determination control device <NUM>, and read out and transmit the plurality of divided polygons to the determination device <NUM> upon inside/outside determination.

[Second embodiment]A second embodiment will be described next. The second embodiment further shortens processing time required for inside/outside determination processing by sequentially executing the preprocessing described in the first background example, first embodiment and the second background example.

<FIG> is a block diagram illustrating an example of a configuration of a determination system according to the second embodiment. As illustrated in <FIG>, a determination system <NUM> according to the second embodiment includes the vertex reduction device <NUM>, the division device <NUM> and the rotation device <NUM> as preprocessing devices.

The inside/outside determination control device <NUM>, for example, first, transmits the polygon information D10 to the vertex reduction device <NUM> and causes the vertex reduction device <NUM> to execute the vertex reduction processing as first preprocessing to thereby acquire reduced polygon information D11.

Then, the inside/outside determination control device <NUM> transmits the reduced polygon information D11 to the division device <NUM> and causes the division device <NUM> to execute the division processing as second preprocessing. The inside/outside determination control device <NUM> thereby acquires vertex-reduced divided polygon information D13' for polygons which are divided after vertexes are reduced.

Subsequently, the inside/outside determination control device <NUM> transmits the vertex-reduced divided polygon information D13' and the coordinate information D20 to the rotation device <NUM> and causes the rotation device <NUM> to execute the rotation processing as third preprocessing. The inside/outside determination control device <NUM> thereby acquires vertex-reduced divided rotated polygon information D12' for polygons for inside/outside determination which are rotated after the vertexes are reduced and divided, and the rotated coordinate information D22.

The determination device <NUM> performs inside/outside determination processing of determining whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination for each of the divided and rotated polygons for inside/outside determination on the basis of the vertex-reduced divided rotated polygon information D12' and the rotated coordinate information D22.

Processing from step S71 to step S74 illustrated in <FIG> is the same processing as the processing from step S1 to step S4 illustrated in <FIG>. The inside/outside determination control device <NUM> transmits the reduced polygon information D11 to the division device <NUM> (step S75) and causes the division device <NUM> to execute preprocessing.

The division device <NUM> executes division processing of dividing the polygon whose vertexes are reduced into a plurality of polygons as the preprocessing (step S76). The division device <NUM> transmits vertex-reduced divided polygon information D13' to the inside/outside determination control device <NUM> (step S77). The processing in step S76 is the same processing as the processing in step S53 illustrated in <FIG>.

The inside/outside determination control device <NUM> then transmits the vertex-reduced divided polygon information D13' and the coordinate information D20 to the rotation device <NUM> (step S78) and causes the rotation device <NUM> to execute preprocessing. The rotation device <NUM> executes rotation processing of rotating the respective polygons for inside/outside determination and the coordinate to be determined on the basis of the vertex-reduced divided polygon information D13' and the coordinate information D20 received from the inside/outside determination control device <NUM> as the preprocessing (step S79). The rotation device <NUM> transmits the vertex-reduced divided rotated polygon information D12' and the rotated coordinate information D22 to the inside/outside determination control device <NUM> (step S80). The processing in step S79 is the same processing as the processing in step S33 illustrated in <FIG>.

The inside/outside determination control device <NUM> transmits the vertex-reduced divided rotated polygon information D12' and the rotated coordinate information D22 to the determination device <NUM> (step S81) and causes the determination device <NUM> to execute inside/outside determination processing. The determination device <NUM> performs inside/outside determination processing of determining whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination for each of the divided and rotated polygons for inside/outside determination on the basis of the vertex-reduced divided rotated polygon information D12' and the rotated coordinate information D22 (step S82). Note that the inside/outside determination processing is the same processing as the processing in step S6 illustrated in <FIG>. Further, processing in step S83 and S84 illustrated in <FIG> is the same processing as the processing in step S7 and S8 illustrated in <FIG>.

[Effects of second embodiment] In this manner, in the second embodiment, the vertex reduction processing on the polygon for inside/outside determination, the rotation processing on the polygon for inside/outside determination after vertexes are reduced, and the division processing on the polygon for inside/outside determination after vertexes are reduced and after the polygon is divided are sequentially executed as the preprocessing. By this means, in the second embodiment, more coordinates can be expected to be determined as being located outside the polygon for inside/outside determination only through simple determination, so that it is possible to further shorten processing time required for inside/outside determination processing compared to the first background example, the first embodiment and the second background example.

Note that while a case has been described as an example in the second embodiment where the vertex reduction processing on the polygon for inside/outside determination, the rotation processing on the polygon for inside/outside determination after vertexes are reduced, and the division processing on the polygon for inside/outside determination after vertexes are reduced and after the polygon is divided are sequentially performed in this order as the preprocessing, the order of the preprocessing is not limited to this order.

[Modified example <NUM> of second embodiment] Further, while a case has been described as an example in the second embodiment where the vertex reduction device <NUM>, the division device <NUM> and the rotation device <NUM> are provided as the preprocessing devices, the preprocessing devices are not limited to these devices. The preprocessing devices may be two devices of the vertex reduction device <NUM> and the rotation device <NUM>. Processing procedure of the determination processing in this case will be described.

<FIG> is a sequence diagram for explaining the processing procedure of the determination processing in modified example <NUM> of the second embodiment. Processing from step S91 to step S94 illustrated in <FIG> is the same processing as the processing from step S1 to step S4 illustrated in <FIG>. The inside/outside determination control device <NUM> transmits the reduced polygon information D11 and the coordinate information D20 to the rotation device <NUM> (step S95) and causes the rotation device <NUM> to execute preprocessing.

The rotation device <NUM> executes rotation processing of rotating the polygon for inside/outside determination after vertexes are reduced and the coordinate to be determined on the basis of the reduced polygon information D11 and the coordinate information D20 received from the inside/outside determination control device <NUM> as the preprocessing (step S96). The rotation device <NUM> transmits vertex-reduced rotated polygon information D12" and the rotated coordinate information D22 to the inside/outside determination control device <NUM> (step S97). The processing in step S96 is the same processing as the processing in step S33 illustrated in <FIG>.

The inside/outside determination control device <NUM> transmits the vertex-reduced rotated polygon information D12" and the rotated coordinate information D22 to the determination device <NUM> (step S98) and causes the determination device <NUM> to execute inside/outside determination processing. The determination device <NUM> performs inside/outside determination processing of determining whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination for each polygon for inside/outside determination after vertexes are reduced and after rotation on the basis of the vertex-reduced rotated polygon information D12" and the rotated coordinate information D22 (step S99). Note that the inside/outside determination processing is the same processing as the processing in step S6 illustrated in <FIG>. Further, processing in step S100 and S101 illustrated in <FIG> is the same processing as the processing in step S7 and S8 illustrated in <FIG>.

[Modified example <NUM> of second embodiment] Further, the preprocessing devices may be two of the vertex reduction device <NUM> and the division device <NUM>. Processing procedure of determination processing in this case will be described.

<FIG> is a sequence diagram for explaining the processing procedure of the determination processing in modified example <NUM> of the second embodiment. Processing from step S111 to step S114 illustrated in <FIG> is the same processing as the processing from step S1 to step S4 illustrated in <FIG>. Processing from step S115 to step S117 illustrated in <FIG> is the same processing as the processing from step S75 to step S77 illustrated in <FIG>. The inside/outside determination control device <NUM> transmits the vertex-reduced divided polygon information D13' and the coordinate information D20 to the determination device <NUM> (step S118) and causes the determination device <NUM> to execute inside/outside determination processing.

The determination device <NUM> performs inside/outside determination processing of determining whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination for each of the polygons for inside/outside determination after vertexes are reduced and after the polygon is divided on the basis of the vertex-reduced divided polygon information D13' and the coordinate information D20 (step S119). Note that the inside/outside determination processing is the same processing as the processing in step S6 illustrated in <FIG>. Further, processing in step S120 and S121 illustrated in <FIG> is the same processing as the processing in step S7 and S8 illustrated in <FIG>.

[Modified example <NUM> of second embodiment] Further, the preprocessing devices may be two of the rotation device <NUM> and the division device <NUM>. Processing procedure of determination processing in this case will be described.

<FIG> is a sequence diagram for explaining the processing procedure of the determination processing in modified example <NUM> of the second embodiment. Processing from step S131 to step S134 illustrated in <FIG> is the same processing as the processing from step S51 to step S54 illustrated in <FIG>.

The inside/outside determination control device <NUM> then transmits the divided polygon information D13 and the coordinate information D20 to the rotation device <NUM> (step S135) and causes the rotation device <NUM> to execute preprocessing. The rotation device <NUM> executes rotation processing of rotating the respective polygons for inside/outside determination and the coordinate to be determined on the basis of the divided polygon information D13 and the coordinate information D20 received from the inside/outside determination control device <NUM> as preprocessing (step S136). The rotation device <NUM> transmits divided rotated polygon information D13" and the rotated coordinate information D22 to the inside/outside determination control device <NUM> (step S137). The processing in step S136 is the same as the processing in step S33 illustrated in <FIG>.

The inside/outside determination control device <NUM> transmits the divided rotated polygon information D13" and the rotated coordinate information D22 to the determination device <NUM> (step S138) and causes the determination device <NUM> to execute inside/outside determination processing. The determination device <NUM> performs inside/outside determination processing of determining whether the coordinate to be determined exists inside or outside the polygon for inside/outside determination for each of the divided and rotated polygons for inside/outside determination on the basis of the divided rotated polygon information D13" and the rotated coordinate information D22 (step S139). Note that the inside/outside determination processing is the same processing as the processing in step S6 illustrated in <FIG>. Further, processing in step S140 and S141 illustrated in <FIG> is the same processing as the processing in step S7 and S8 illustrated in <FIG>.

[Verification] Comparison of performance between the determination method using the determination system in the first background example, the first embodiment and the second background example and the determination method in related art was verified. <FIG> is a view for explaining an experimental model. In the present verification, one polygon as illustrated in <FIG> and <NUM> vehicles are set as targets. The polygon illustrated in <FIG> is specifically a road polygon having a long side of <NUM>, a short side of <NUM>, and an interval between vertexes of <NUM>. Further, in the present verification, comparison is performed while three patterns of vehicles including a pattern in which a vehicle is located outside the MBR and outside the polygon, a pattern in which a vehicle is located inside the MBR and outside the polygon, and a pattern in which a vehicle is located inside the MBR and inside the polygon, are provided, and by employing average values of determination results obtained by performing trials <NUM> times.

First, a result of comparison between a case where inside/outside determination was performed after vertex reduction processing was performed on the road polygon as the preprocessing and a case where inside/outside determination was performed without preprocessing being performed will be described. PIP processing time in a case where the number of vertexes of the road polygon was reduced to <NUM>/<NUM>, <NUM>/<NUM> and <NUM>/<NUM> as preprocessing, and PIP processing time in a case where inside/outside determination was performed without preprocessing being executed, were measured.

<FIG> is a view for explaining the PIP processing time in a case where inside/outside determination was performed after vertex reduction processing was performed and in a case where inside/outside determination was performed without preprocessing being executed. As illustrated in <FIG>, compared to a case where inside/outside determination was performed without preprocessing being executed ("reference" case in <FIG>), in a case where the number of vertexes was reduced to <NUM>/<NUM>, <NUM>/<NUM> and <NUM>/<NUM>, the processing time could be respectively shortened to <NUM> times, <NUM>. times and <NUM> times of the PIP processing time in the reference case.

A result of comparison between a case where inside/outside determination was performed after division processing of dividing the road polygon into a plurality of polygons was performed as preprocessing and a case where inside/outside determination was performed without preprocessing being executed will be described next. <FIG> is a view for explaining division processing performed in the verification.

In the present verification, PIP processing time in a case where inside/outside determination was performed after preprocessing which will be described next was executed and PIP processing time in a case where inside/outside determination was performed without preprocessing being executed, were measured. The preprocessing is processing of equally dividing the road polygon P14 (see (<NUM>) of <FIG>) into two road polygons P14-<NUM> and P-<NUM>-<NUM> (see (<NUM>) of <FIG>) and dividing the MBR <NUM> (see (<NUM>) of <FIG>) into MBRs <NUM>-<NUM> and <NUM>-<NUM> (see (<NUM>) of <FIG>) whose areas are reduced compared to the MBR <NUM>.

<FIG> is a view for explaining PIP processing time in a case where inside/outside determination was performed after the division processing was performed and in a case where inside/outside determination was performed without preprocessing being executed. The experimental result indicates a model assuming that all <NUM> vehicles move outside the MBR by the division processing. The model indicates such a drastic case to indicate a base of an estimated value as to how much improvement can be expected from the method.

In a case where inside/outside determination was performed without division processing being executed, total time required for <NUM> vehicles located within the MBR to be subjected to PIP processing was <NUM> ("no division" in <FIG>). In contrast, in a case where inside/outside determination was performed after division processing was executed, all <NUM> vehicles located within the MBR moved "outside the MBR", and thus, processing was finished after only simple determination was performed. In other words, it is possible to omit exterior product computation for vehicles which have moved outside the MBR by the division processing. Thus, in a case where inside/outside determination was performed after division processing was executed ("division" in <FIG>), total time required for inside/outside determination processing performed on <NUM> vehicles outside the MBR was <NUM>.

As a result, in a case where inside/outside determination was performed after division processing was performed, total processing time obtained by adding division processing time and PIP processing time could be shortened to <NUM> times of processing time in a case where preprocessing is not executed.

Further, a result of comparison between a case where inside/outside determination was performed after rotation processing of rotating the road polygon and the vehicles was performed as preprocessing and a case where inside/outside determination was performed without preprocessing being executed will be described. <FIG> is a view for explaining rotation processing performed in the verification.

As illustrated in <FIG>, in the present verification, PIP processing time in a case where the road polygon P14 (see (<NUM>) of <FIG>) and the vehicles were rotated by <NUM> degrees as the preprocessing (see (<NUM>) of <FIG>), and PIP processing time in a case where inside/outside determination was performed without preprocessing being executed, were measured. As illustrated in (<NUM>) of <FIG>, the MBR becomes an MBR <NUM>-<NUM> whose area is reduced compared to the MBR <NUM> in accordance with a road polygon P15 rotated by <NUM> degrees. Note that the experimental result indicates a model assuming that all <NUM> vehicles have moved outside the MBR by the rotation processing. The model indicates such a drastic case to indicate a base of an estimated value as to how much improvement can be expected from the method. Further, rotation processing time is short and equal to or less than <NUM>/<NUM> of the PIP processing time.

<FIG> is a view for explaining PIP processing time in a case where inside/outside determination was performed after rotation processing was performed and in a case where inside/outside determination was performed without preprocessing being executed. In a case where inside/outside determination was performed without rotation processing being executed, total time required for <NUM> vehicles located within the MBR to be subjected to PIP processing is <NUM> (see "no rotation" in <FIG>).

In contrast, in a case where inside/outside determination was performed after rotation processing was executed ("rotation" in <FIG>), all <NUM> vehicles located within the MBR have moved "outside the MBR", and thus, processing was finished after only simple determination was performed. In other words, it is possible to omit exterior product computation on vehicles which have moved outside the MBR by the rotation processing. Thus, in a case where inside/outside determination was performed after the rotation processing was executed ("rotation" in <FIG>), total time required for inside/outside determination processing for <NUM> vehicles outside the MBR was <NUM>.

As a result, in a case where inside/outside determination was performed after rotation processing was performed, total processing time obtained by adding rotation processing time and PIP processing time could be shortened to <NUM> times of processing time in a case where preprocessing is not executed.

[Other application examples] <FIG> is a view for explaining another application example of the determination system according to the first background example, the first embodiment, the second background example and the second embodiment. The determination system according to the first background example, the first embodiment, the second background example and the second embodiment can be applied to determination of a coordinates (area: ocean route) of ships on an ocean route. First, a width of the ocean route is expanded to W m (W can be freely set) on the basis of the ocean route (solid line indicated in (<NUM>) of <FIG>). Then, the determination system according to the first background example, the first embodiment, the second background example and the second embodiment determines positions of ships on the ocean while replacing the road with a new ocean route and replacing the automobiles with the ships.

Further, the determination system according to the first background example, the first embodiment, the second background example and the second embodiment can be applied to tracking of fishes to which coordinate sensors are attached (area: river). Specifically, the determination system according to the first background example, the first embodiment, the second background example and the second embodiment determines positions of fishes in the river while replacing the road with the river and replacing the automobiles with the fishes.

[System configuration of embodiments] Respective components of the vertex reduction device <NUM> illustrated in <FIG>, the determination device <NUM> illustrated in <FIG>, the rotation device <NUM> illustrated in <FIG> and the division device <NUM> illustrated in <FIG> indicate functional concept, and do not necessarily have to be physically constituted as illustrated. In other words, specific forms of distribution and integration of the functions of the vertex reduction device <NUM>, the determination device <NUM>, the rotation device <NUM> and the division device <NUM> are not limited to those illustrated, and all or part can be functionally or physically distributed or integrated in arbitrary unit in accordance with various loads and usage conditions.

Further, all or arbitrary part of respective kinds of processing to be performed at the vertex reduction device <NUM>, the determination device <NUM>, the rotation device <NUM> and the division device <NUM> may be implemented by a CPU and programs to be analyzed and executed by the CPU. Further, respective kinds of processing to be performed at the vertex reduction device <NUM> may be implemented as hardware using wired logic.

Further, among respective kinds of processing described in the embodiments, all or part of processing described as being automatically performed can be manually performed. Alternatively, all or part of processing described as being manually performed can be automatically performed using a publicly known method. Further, information including the processing procedure, control procedure, specific name, various kinds of data and parameters described above and illustrated can be changed as appropriate unless otherwise specified.

[Program] <FIG> is a view illustrating an example of a computer which implements the vertex reduction device <NUM>, the determination device <NUM>, the rotation device <NUM> and the division device <NUM> by programs being executed. A computer <NUM> includes, for example, a memory <NUM> and a CPU <NUM>. Further, the computer <NUM> includes 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 components are connected with a bus <NUM>.

The memory <NUM> includes a ROM <NUM> and a RAM <NUM>. The ROM <NUM> stores, for example, a boot program such as a BIOS (Basic Input Output System). 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 detachable storage medium such as a magnetic disk and an optical disk is inserted into the disk drive <NUM>. The serial port interface <NUM> is connected to, for example, a mouse <NUM> and a keyboard <NUM>. The video adapter <NUM> is, for example, connected to a display <NUM>.

The hard disk drive <NUM> stores, for example, an OS (Operating System) <NUM>, an application program <NUM>, a program module <NUM>, and program data <NUM>. In other words, programs which specify respective kinds of processing of the vertex reduction device <NUM>, the determination device <NUM>, the rotation device <NUM> and the division device <NUM> are implemented as the program module <NUM> which describes codes which can be executed by the computer <NUM>. The program module <NUM> is stored in, for example, the hard disk drive <NUM>. For example, the program module <NUM> for executing processing similar to functional components of the vertex reduction device <NUM>, the determination device <NUM>, the rotation device <NUM> and the division device <NUM> is stored in the hard disk drive <NUM>. Note that the hard disk drive <NUM> may be substituted with an SSD (Solid State Drive).

Further, setting data used in the processing in the above-described embodiments is stored in, for example, the memory <NUM> or the hard disk drive <NUM> as the program data <NUM>. Further, the CPU <NUM> reads out the program module <NUM> and the program data <NUM> stored in the memory <NUM> or the hard disk drive <NUM> to the RAM <NUM> as necessary and executes the program module <NUM> and the program data <NUM>.

Note that the program module <NUM> and the program data <NUM> may be stored in, for example, a detachable storage medium, as well as being stored in the hard disk drive <NUM>, and may be read out by the CPU <NUM> via the disk drive <NUM>, or the like. Alternatively, the program module <NUM> and the program data <NUM> may be stored in other computers connected via a network (such as a LAN (Local Area Network) and a WAN (Wide Area Network)). Further, the program module <NUM> and the program data <NUM> may be read out from other computers by the CPU <NUM> via the network interface <NUM>.

Claim 1:
A preprocessing device (<NUM>) comprising:
a rotation unit (<NUM>) configured to
acquire first coordinate information of respective vertexes of a polygon for inside/outside determination and the coordinate information of a coordinate to be determined, and
reduce an area of a minimal bounding rectangle, MBR, including the polygon by rotating the polygon and the coordinate, as preprocessing of determination processing of determining whether the coordinate exists inside or outside the polygon; and
an output unit (<NUM>) configured to output coordinate information of respective vertexes of the rotated polygon and the rotated coordinate as rotated coordinate information.