WO2021048992A1 - 前処理装置、判定システム、前処理方法および前処理プログラム - Google Patents

前処理装置、判定システム、前処理方法および前処理プログラム Download PDF

Info

Publication number
WO2021048992A1
WO2021048992A1 PCT/JP2019/035988 JP2019035988W WO2021048992A1 WO 2021048992 A1 WO2021048992 A1 WO 2021048992A1 JP 2019035988 W JP2019035988 W JP 2019035988W WO 2021048992 A1 WO2021048992 A1 WO 2021048992A1
Authority
WO
WIPO (PCT)
Prior art keywords
determination
polygon
outside
internal
rotation
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2019/035988
Other languages
English (en)
French (fr)
Inventor
和大 宮原
木村　達郎
一兵衛 内藤
淳 磯村
朋哉 池田
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to PCT/JP2019/035988 priority Critical patent/WO2021048992A1/ja
Priority to EP19944858.0A priority patent/EP4009280B1/en
Priority to JP2021545063A priority patent/JP7168099B2/ja
Priority to US17/640,354 priority patent/US11954812B2/en
Priority to CN201980100208.1A priority patent/CN114424248B/zh
Publication of WO2021048992A1 publication Critical patent/WO2021048992A1/ja
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three-dimensional [3D] modelling for computer graphics
    • G06T17/05—Geographic models
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T19/00—Manipulating three-dimensional [3D] models or images for computer graphics
    • G06T19/20—Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00—Three-dimensional [3D] modelling for computer graphics
    • G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2210/00—Indexing scheme for image generation or computer graphics
    • G06T2210/12—Bounding box
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2210/00—Indexing scheme for image generation or computer graphics
    • G06T2210/21—Collision detection, intersection
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T2219/00—Indexing scheme for manipulating 3D models or images for computer graphics
    • G06T2219/20—Indexing scheme for editing of 3D models
    • G06T2219/2016—Rotation, translation, scaling

Definitions

  • the present invention relates to a pretreatment device, a determination system, a pretreatment method, and a pretreatment program.
  • the polygon inside / outside judgment technology determines whether specific coordinates are included inside a specific polygon.
  • the polygon inside / outside determination technique is applied, for example, when determining whether the coordinates of a geographical vehicle or the like are included in a polygon representing a road area.
  • determination techniques For example, as a conventional polygon inside / outside determination technique, there are determination techniques based on the Crossing Number method and the Winding Number method (see, for example, Non-Patent Document 1). These determination techniques determine whether or not the coordinates are included inside the polygon by aggregating the positional relationship between all the sides of the polygon to be determined and the coordinates of the determination target.
  • This bounding container is a figure that includes a polygon to be determined.
  • This technology is a technology that reduces the average processing time by selecting a figure that can execute internal / external judgment at high speed as a bounding container and applying the Crossing Number method or Winding Number method only to the coordinates included in the bounding container. is there.
  • a rectangle MRR: Minimal Bounding Rectangle
  • MRR Minimal Bounding Rectangle
  • this polygon When the polygon inside / outside judgment technology is applied to determine whether or not the road area includes geographical vehicles, this polygon has a large number of vertices and has an elongated shape in order to represent the road area. It has the characteristic of being.
  • the Crossing Number method and the Winding Number method have the property that the processing time is proportional to the number of vertices, there is a problem that the processing time becomes long when the judgment is made for a polygon having a large number of vertices.
  • the MBR has the property of including a large area outside the polygon for the elongated polygon, the effect of shortening the average processing time can be obtained when the determination is performed for the polygon having the elongated shape. There is a problem that it is hard to come out.
  • the present invention has been made in view of the above, and an object of the present invention is to provide a preprocessing apparatus, a determination system, a preprocessing method, and a preprocessing program capable of shortening the processing time required for polygon inside / outside determination processing. And.
  • the preprocessing apparatus of the present invention is used as a preprocessing of the determination process for determining whether the coordinates to be determined exist inside or outside the polygon for inside / outside determination.
  • the reduction unit that acquires the coordinate information of each vertex of the polygon for internal / external judgment and reduces the vertices of the polygon for internal / external judgment, and the coordinate information of each vertex of the polygon after the reduction unit reduces the vertices. It is characterized by having an output unit that outputs to a device that performs determination processing.
  • the determination system of the present invention includes a determination device that determines whether or not the coordinates to be determined exist inside or outside the polygon for inside / outside determination, and a first preprocessing device that performs preprocessing of the determination process.
  • the first preprocessing device acquires the coordinate information of each vertex of the polygon for internal / external determination, and performs the first preprocessing to reduce the vertices of the polygon for internal / external determination.
  • the determination device has a unit and an output unit that outputs the reduced polygon information which is the coordinate information of each vertex of the polygon after the reduction unit reduces the vertices, and the determination device uses the information after the preprocessing. , It is characterized in that it is determined whether or not the coordinates to be determined exist inside or outside the polygon for inside / outside determination.
  • the pre-processing method of the present invention is a pre-processing method performed by the pre-processing apparatus, and is used as a pre-processing for determining whether or not the coordinates to be determined are inside or outside the polygon for determining inside or outside.
  • the process of acquiring the coordinate information of each vertex of the polygon for internal / external judgment and reducing the vertices of the polygon for internal / external judgment, and the judgment processing of the coordinate information of each vertex of the polygon after the number of vertices is reduced. It is characterized by including a process of outputting to a device to be performed.
  • the preprocessing program of the present invention provides coordinate information of each vertex of the polygon for internal / external determination as a preprocessing for determination processing for determining whether the coordinates to be determined exist inside or outside the polygon for internal / external determination. And the step of reducing the vertices of the polygon for internal / external judgment and the step of outputting the coordinate information of each vertex of the polygon after the vertices are reduced to the device that performs the judgment processing are executed on the computer. Let me.
  • the processing time required for the polygon inside / outside determination processing can be shortened.
  • FIG. 1 is a block diagram showing an example of the configuration of the determination system according to the first embodiment.
  • FIG. 2 is a block diagram showing an example of the configuration of the vertex reduction device shown in FIG.
  • FIG. 3 is a diagram showing a list of data structures of polygon information.
  • FIG. 4 is a block diagram showing an example of the configuration of the determination device shown in FIG.
  • FIG. 5 is a diagram showing a list of data configurations of coordinate information.
  • FIG. 6 is a diagram illustrating a vertex reduction process.
  • FIG. 7 is a sequence diagram illustrating a processing procedure of the determination process by the determination system shown in FIG.
  • FIG. 8 is a flowchart showing a processing procedure of the vertex reduction processing shown in FIG. 7.
  • FIG. 7 is a sequence diagram illustrating a processing procedure of the determination process by the determination system shown in FIG.
  • FIG. 8 is a flowchart showing a processing procedure of the vertex reduction processing shown in FIG. 7.
  • FIG. 7 is a sequence diagram
  • FIG. 9 is a flowchart showing a processing procedure of the inside / outside determination process shown in FIG. 7.
  • FIG. 10 is a block diagram showing an example of the configuration of the determination system according to the second embodiment.
  • FIG. 11 is a block diagram showing an example of the configuration of the rotating device shown in FIG.
  • FIG. 12 is a diagram illustrating the rotation process.
  • FIG. 13 is a sequence diagram illustrating a processing procedure of the determination process by the determination system shown in FIG.
  • FIG. 14 is a flowchart showing a processing procedure of the rotation process shown in FIG.
  • FIG. 15 is a block diagram showing an example of the configuration of the determination system according to the third embodiment.
  • FIG. 16 is a block diagram showing an example of the configuration of the dividing device shown in FIG. FIG.
  • FIG. 17 is a diagram illustrating a division process.
  • FIG. 18 is a sequence diagram illustrating a processing procedure of the determination process by the determination system shown in FIG.
  • FIG. 19 is a flowchart showing a processing procedure of the division processing shown in FIG.
  • FIG. 20 is a block diagram showing an example of the configuration of the determination system according to the fourth embodiment.
  • FIG. 21 is a sequence diagram illustrating a processing procedure of the determination process by the determination system shown in FIG. 20.
  • FIG. 22 is a sequence diagram illustrating a processing procedure of the determination process in the first modification of the fourth embodiment.
  • FIG. 23 is a sequence diagram for explaining the processing procedure of the determination process in the second modification of the fourth embodiment.
  • FIG. 21 is a sequence diagram illustrating a processing procedure of the determination process by the determination system shown in FIG. 20.
  • FIG. 22 is a sequence diagram illustrating a processing procedure of the determination process in the first modification of the fourth embodiment.
  • FIG. 23 is a sequence diagram for explaining the processing procedure of
  • FIG. 24 is a sequence diagram illustrating a processing procedure of the determination process according to the third modification of the fourth embodiment.
  • FIG. 25 is a diagram illustrating an experimental model.
  • FIG. 26 is a diagram for explaining the PIP processing time in the case where the inside / outside determination is performed after the vertex reduction processing is performed and the case where the inside / outside determination is performed without executing the preprocessing.
  • FIG. 27 is a diagram illustrating the division process performed in the verification.
  • FIG. 28 is a diagram for explaining the PIP processing time in the case where the inside / outside determination is performed after the division processing is performed and the case where the inside / outside determination is performed without executing the preprocessing.
  • FIG. 29 is a diagram illustrating the rotation process performed in the verification.
  • FIG. 29 is a diagram illustrating the rotation process performed in the verification.
  • FIG. 30 is a diagram for explaining the PIP processing time in the case where the inside / outside determination is performed after the rotation processing is performed and the case where the inside / outside determination is performed without executing the preprocessing.
  • FIG. 31 is a diagram illustrating another application example of the determination system according to the first to fourth embodiments.
  • FIG. 32 is a diagram showing an example of a computer in which a vertex reduction device, a determination device, a rotation device, and a division device are realized by executing a program.
  • the first embodiment will be described.
  • the vertices of the polygon for internal / external determination are reduced before the internal / external determination process for determining whether the coordinates to be determined exist inside or outside the polygon for internal / external determination.
  • the processing time required for the judgment processing is shortened.
  • FIG. 1 is a block diagram showing an example of the configuration of the determination system according to the first embodiment.
  • the determination system 1 according to the first embodiment includes a client terminal 2, an inside / outside determination control device 3, a vertex reduction device 10, and a determination device 20.
  • the client terminal 2 and the inside / outside determination control device 3 are connected via a network or the like.
  • the inside / outside determination control device 3, the vertex reduction device 10, and the determination device 20 are connected via a network or the like.
  • the client terminal 2 is a terminal device used by the user of the determination system 1.
  • the client terminal 2 transmits the coordinate information D20 of the coordinates to be determined and the polygon information D10 which is the coordinate information of each vertex of the polygon for internal / external determination to the internal / external determination control device 3 to make a determination request. ..
  • the inside / outside determination control device 3 is a server device that controls processing in the vertex reduction device 10 and the determination device 20. Upon receiving a judgment request from the client terminal 2, the inside / outside judgment control device 3 determines whether the coordinates to be judged exist inside or outside the polygon for inside / outside judgment (judgment processing). Is executed, and the determination result is returned to the client terminal 2. Further, in the first embodiment, the inside / outside determination control device 3 causes the vertex reduction device 10 to execute the preprocessing of the inside / outside determination process before the determination device 20 executes the inside / outside determination process.
  • the vertex reduction device 10 receives the polygon information D10 from the inside / outside determination control device 3 and executes preprocessing for reducing the vertices of the polygon for inside / outside determination.
  • the vertex reduction device 10 outputs the reduced polygon information D11, which is the coordinate information of each vertex of the polygon after the number of vertices is reduced, to the inside / outside determination control device 3.
  • the determination device 20 performs an inside / outside determination process for determining whether the coordinates to be determined exist inside or outside the polygon for inside / outside determination. At this time, the determination device 20 performs internal / external determination processing based on the reduced polygon information D11 and the coordinate information D20 of the coordinates to be determined. The determination device 20 outputs determination information including the determination result to the inside / outside determination control device 3.
  • FIG. 2 is a block diagram showing an example of the configuration of the vertex reduction device 10 shown in FIG.
  • the vertex reduction device 10 includes a communication unit 11, a storage unit 12, and a control unit 13.
  • the communication unit 11 is a communication interface for transmitting and receiving various information to and from other devices connected via a network or the like.
  • the communication unit 11 is realized by a NIC (Network Interface Card) or the like, and communicates between another device and the control unit 13 (described later) via a telecommunication line such as a LAN (Local Area Network) or the Internet.
  • NIC Network Interface Card
  • telecommunication line such as a LAN (Local Area Network) or the Internet.
  • the communication unit 11 receives the polygon information D10 from the inside / outside determination control device 3 via the network. Further, the communication unit 11 transmits the reduced polygon information D11 to the inside / outside determination control device 3.
  • the storage unit 12 is realized by a semiconductor memory element such as a RAM (Random Access Memory) or a flash memory (Flash Memory), or a storage device such as a hard disk or an optical disk, and is a processing program or a processing program for operating the vertex reduction device 10. Data used during execution of is stored.
  • the storage unit 12 stores the polygon information D10 and the reduced polygon information D11.
  • the polygon information D10 is the coordinate information of each vertex of the polygon for determining inside and outside.
  • the polygon information D10 is transmitted from the inside / outside determination control device 3.
  • FIG. 3 is a diagram showing a list of data structures of polygon information D10.
  • the polygon information D10 is a list of coordinates of the vertices of the polygon for internal / external determination. For example, when the polygon for internal / external determination has 100 vertices, 100 sets of polygons are used. Has coordinates.
  • the reduced coordinate information D11 is the coordinate information of each vertex of the polygon whose vertices are reduced by the processing of the vertex reduction unit 131 (described later) for each vertex of the polygon for internal / external determination.
  • the reduced coordinate information D11 is, for example, a coordinate list of each vertex of the polygon whose vertices are reduced from 100 to 60.
  • the control unit 13 controls the entire vertex reduction device 10.
  • the control unit 13 is, for example, an electronic circuit such as a CPU (Central Processing Unit) and an MPU (Micro Processing Unit), and an integrated circuit such as an ASIC (Application Specific Integrated Circuit) and an FPGA (Field Programmable Gate Array). Further, the control unit 13 has an internal memory for storing programs and control data that define various processing procedures, and executes each process using the internal memory. Further, the control unit 13 functions as various processing units by operating various programs.
  • the control unit 13 has a vertex reduction unit 131 (reduction unit).
  • the vertex reduction unit 131 acquires the polygon information D10 as a preprocessing of the inside / outside determination process, and reduces the vertices of the polygon for inside / outside determination.
  • the vertex reduction unit 131 performs a process of thinning out the vertices of the polygon for determining inside / outside at appropriate intervals.
  • the vertex reduction unit 131 realizes the vertex reduction process by using a Ramer-Douglas-Peucker algorithm (see, for example, Reference 1).
  • the vertex reduction unit 131 stores the reduced coordinate information D11, which is the coordinate information of each vertex of the polygon whose vertices have been reduced by the vertex reduction processing for each vertex of the polygon for internal / external determination, in the storage unit 12, and also stores the coordinate information D11. This information is output to the inside / outside determination control device 3 via the communication unit 11.
  • FIG. 4 is a block diagram showing an example of the configuration of the determination device 20 shown in FIG.
  • the determination device 20 includes a communication unit 21, a storage unit 22, and a control unit 23.
  • the communication unit 21 is a communication interface for transmitting and receiving various information to and from other devices connected via a network or the like, and is realized by a NIC or the like, and is another device via a telecommunication line such as a LAN or the Internet. Communication is performed between the device and the control unit 23 (described later).
  • the communication unit 21 receives the reduced polygon information D11 and the coordinate information D20 as the coordinate information of each vertex of the polygon for inside / outside determination from the inside / outside determination control device 3 via the network. Further, the communication unit 21 transmits the determination result of the inside / outside determination unit 231 (described later) to the inside / outside determination control device 3.
  • the storage unit 22 is realized by a semiconductor memory element such as a RAM or a flash memory, or a storage device such as a hard disk or an optical disk, and contains a processing program that operates the determination device 20, data used during execution of the processing program, and the like. It will be remembered.
  • the storage unit 22 stores the reduced polygon information D11 and the coordinate information D20.
  • the coordinate information D20 is the coordinate information of the coordinates to be determined.
  • the coordinate information D20 is transmitted from the inside / outside determination control device 3.
  • FIG. 5 is a diagram showing a list of data configurations of the coordinate information D20. As shown in FIG. 5, the coordinate information D20 indicates the longitude and latitude of the coordinates to be determined.
  • the control unit 23 controls the entire vertex reduction device 10.
  • the control unit 23 is, for example, an electronic circuit such as a CPU or MPU, or an integrated circuit such as an ASIC or FPGA. Further, the control unit 23 has an internal memory for storing programs and control data that define various processing procedures, and executes each process using the internal memory. Further, the control unit 23 functions as various processing units by operating various programs. The control unit 23 performs the inside / outside determination unit 231.
  • the inside / outside determination unit 231 performs an inside / outside determination process for determining whether the coordinates to be determined exist inside or outside the polygon for inside / outside determination based on the reduced polygon information D11 and the coordinate information D20.
  • the internal / external determination unit 231 executes a detailed determination by the Crossing Number method or the Winding Number method after the simple determination by the MBR.
  • FIG. 6 is a diagram illustrating a vertex reduction process.
  • FIG. 6 (1) shows a polygon P10 for determining inside / outside before the vertex reduction process
  • FIG. 6 (2) shows a polygon P11 after the vertex reduction process.
  • FIG. 6 also shows MBR40, coordinates C1, C2, and C3 to be determined.
  • the polygon P10 shown in FIG. 6 (1) has 16 vertices.
  • the vertex reduction unit 131 reduces the vertices of the polygon P10 by using the algorithm of Ramer-Douglas-Peucker.
  • Ramer-Douglas-Peucker's algorithm (A) plots the start and end points of the route, (B) examines the distance between the straight line connecting the plot targets and each point between them, and at points that are more than the allowable distance. , Find the farthest point, (C) make it a new plot target, repeat the processes of (B) and (C) recursively, and (D) end if there is no point more than ⁇ away. Is.
  • the vertex reduction unit 131 is a polygon in which the number of vertices is reduced to 10 as compared with the polygon P10 in which the number of vertices is 16. Generate P11. Then, the determination device 20 performs the determination process using the polygon P11 as a polygon for internal / external determination.
  • FIG. 7 is a sequence diagram illustrating a processing procedure of the determination process by the determination system 1 shown in FIG.
  • the client terminal 2 transmits the coordinate information D20 of the coordinates to be determined and the polygon information D10 which is the coordinate information of each vertex of the polygon for internal / external determination to the internal / external determination control device 3 to request the determination. (Step S1).
  • the inside / outside determination control device 3 Upon receiving the determination request, transmits the polygon information D10 to the vertex reduction device 10 (step S2), and causes the preprocessing to be executed.
  • the vertex reduction device 10 executes a vertex reduction process for reducing the vertices of the polygon for internal / external determination based on the polygon information D10 received from the internal / external determination control device 3 (step S3), and after reduction.
  • the polygon information D11 is transmitted to the inside / outside determination control device 3 (step S4).
  • the inside / outside determination control device 3 transmits the reduced polygon information D11 and the coordinate information D20 to the determination device 20 (step S5), and executes the inside / outside determination process.
  • the inside / outside determination control device 3 performs an inside / outside determination process (step S6) based on the reduced polygon information D11 and the coordinate information D20, and transmits the determination information to the inside / outside determination control device 3 (step S7).
  • the inside / outside determination control device 3 transmits the determination information to the client terminal 2 (step S8).
  • FIG. 8 is a flowchart showing a processing procedure of the vertex reduction processing shown in FIG. 7.
  • the vertex reduction device 10 when the vertex reduction device 10 receives the input of the polygon information D10 by the inside / outside determination control device 3 (step S11), the vertex reduction device 10 reduces the vertices of the polygon for inside / outside determination (step S12).
  • the vertex reduction device 10 generates polygon information D11 after reduction, outputs the polygon information D11 to the inside / outside determination control device 3 (step S13), and ends the vertex reduction process.
  • FIG. 9 is a flowchart showing a processing procedure of the inside / outside determination process shown in FIG. 7.
  • the determination device 20 performs a simple determination process for determining whether or not the coordinates of the determination target are inside the MBR (step S21).
  • the determination device 20 determines that the coordinates to be determined are not inside the MBR (step S21: No)
  • the determination device 20 determines that the coordinates are outside the polygon for inside / outside determination (“false”) (step S22). ..
  • the determination device 20 determines that the coordinates to be determined are inside the MBR (step S21: Yes)
  • the determination device 20 performs detailed determination by the Crossing Number method or the Winding Number method.
  • the determination device 20 sets the polygon shown in the reduced polygon information D11 as the polygon to be determined inside and outside, and determines whether or not the coordinates of the determination target are inside the polygon for determining inside and outside (step). S23).
  • step S23 When the determination device 20 determines that the coordinates of the determination target are not inside the polygon for inside / outside determination (step S23: No), the process proceeds to step S22, and the coordinates are outside the polygon for inside / outside determination ("" "False") is determined (step S22).
  • step S23 when the determination device 20 determines that the coordinates of the determination target are inside the polygon for determining inside / outside (step S23: Yes), the coordinates are inside the polygon for determining inside / outside ("" It is determined that "true") (step S24).
  • the determination device 20 executes the processes of steps S21 to S24 for each of the coordinates of the determination target, and transmits the determination information associated with the determination result for each of the coordinates of the determination target to the internal / external determination control device 3.
  • the preprocessing for reducing the vertices of the polygon for internal / external determination is performed, and the polygon internal / external determination processing for each coordinate is performed using the polygon with the reduced vertices. Therefore, in the first embodiment, since the detailed determination is executed based on the polygon whose vertices are reduced during the detailed determination process, it is compared with the case where the detailed determination is performed for the initial polygon for internal / external determination. Therefore, the processing time of the detailed determination process can be shortened.
  • the first embodiment is applied to a polygon representing a road area having a large number of vertices, particularly when it is applied to determine whether the coordinates of a geographical vehicle or the like are included in the polygon representing the road area. Since the detailed determination process is performed after reducing the number of vertices in advance, the processing time of the determination process can be increased.
  • the inside / outside determination control device 3 causes the vertex reduction device 10 to reduce the vertices of the polygon for inside / outside determination in advance and stores the vertices in the storage area of the inside / outside determination control device 3. It may be read out at the time of internal / external determination and transmitted to the determination device 20.
  • the inside / outside judgment processing is performed by rotating the polygon for inside / outside judgment and the coordinates of the judgment target to reduce the area of the MBR including the rotated polygon. Reduce the processing time required for.
  • FIG. 10 is a block diagram showing an example of the configuration of the determination system according to the second embodiment.
  • the determination system 201 according to the second embodiment has a rotating device 210 (pretreatment device, first pretreatment device) instead of the vertex reduction device 10 as compared with the determination system 1 shown in FIG. ).
  • the rotating device 210 receives the polygon information D10 and the coordinate information D20 from the inside / outside determination control device 3, and executes a preprocessing for rotating the polygon for inside / outside determination and the coordinates of the determination target.
  • the rotating device 210 sends the post-rotation polygon information D12, which is the coordinate information of each vertex of the rotated polygon, and the post-rotation coordinate information D22, which is the coordinate information of the coordinates to be determined after the rotation, to the inside / outside determination control device 3. Output.
  • the determination device 20 determines whether the coordinates of the determination target after rotation exist inside or outside the polygon for internal / external determination after rotation based on the polygon information D12 after rotation and the coordinate information D22 after rotation. Judgment processing is performed.
  • FIG. 11 is a block diagram showing an example of the configuration of the rotating device 210 shown in FIG.
  • the rotating device 210 includes a communication unit 211 (output unit, first output unit), a storage unit 212, and a control unit 213.
  • the communication unit 211 has the same function as the communication unit 11 in the vertex reduction device 10.
  • the communication unit 211 receives the polygon information D10 and the coordinate information D20 from the inside / outside determination control device 3 via the network. Further, the communication unit 211 controls the inside / outside determination of the polygon for inside / outside determination and the post-rotation polygon information D12 and the post-rotation coordinate information D22 generated by the rotation processing by the rotation unit 2131 (described later) with respect to the coordinates to be determined. It is transmitted to the device 3.
  • the storage unit 212 has the same function as the storage unit 12 in the vertex reduction device 10.
  • the storage unit 312 stores polygon information D10, coordinate information D20, post-rotation polygon information D12, and post-rotation coordinate information D22.
  • the control unit 213 has the same function as the control unit 13 in the vertex reduction device 10.
  • the control unit 213 has a rotating unit 2131.
  • the rotating unit 2131 acquires polygon information D10 and coordinate information D20 as preprocessing of the inside / outside determination processing, and rotates the polygon for inside / outside determination and the coordinates of the determination target.
  • the rotation unit 2131 realizes the rotation process by using an algorithm for deriving the rotation angle (see, for example, Reference 2).
  • Reference 2 "Minimum-Area Rectangle Containing a Set of Points", [online], [Search on August 23, 1st year of Reiwa], Internet ⁇ URL: https://www.geometrictools.com/Documentation/MinimumAreaRectangle. pdf >
  • the rotating unit 2131 stores the post-rotation polygon information D12 and the post-rotation coordinate information D22 in the storage unit 212, and outputs these information to the internal / external determination control device 3 via the communication unit 211.
  • FIG. 12 is a diagram illustrating the rotation process.
  • FIG. 12 (1) shows the polygon P10 for internal / external determination before rotation processing and the coordinates C1, C2, C3 to be determined
  • FIG. 12 (2) shows the polygon P11 after rotation processing and after rotation.
  • the coordinates C12, C22, and C32 of are shown.
  • FIG. 12 also shows an MBR 40 before the rotation process and an MBR 42 set after the rotation process.
  • the MBR40 with respect to the polygon P10 is a substantially square including the coordinates C1 and C2.
  • the rotating unit 2131 appropriately rotates the polygon P10 and the coordinates C1, C2, and C3 to be determined by using the algorithm for deriving the rotation angle.
  • the MBR 42 having a smaller area than the MBR 40 can be set as the MBR including the polygon P12 for determining the inside / outside after rotation. Further, the coordinate C22 to be determined is located outside the new MBR42 due to rotation, and the determination is completed only by a simple determination.
  • the coordinates determined to be outside the polygon for internal / external determination increase only by the simple determination, and the detailed determination is made. Can be reduced in the number of executions.
  • the coordinates to be determined in detail are only the coordinates C32 among the coordinates C12, C22, and C23.
  • FIG. 13 is a sequence diagram illustrating a processing procedure of the determination process by the determination system 201 shown in FIG.
  • Step S31 shown in FIG. 13 is the same process as step S1 shown in FIG. 7.
  • the inside / outside determination control device 3 Upon receiving the determination request, the inside / outside determination control device 3 transmits the polygon information D10 and the coordinate information D20 to the rotating device 210 (step S32), and causes the preprocessing to be executed.
  • the rotating device 210 executes a rotation process of rotating the polygon for internal / external determination and the coordinates of the determination target based on the polygon information D10 and the coordinate information D20 received from the internal / external determination control device 3 (Ste S33), the post-rotation polygon information D12 and the post-rotation coordinate information D22 are transmitted to the inside / outside determination control device 3 (step S34).
  • the inside / outside determination control device 3 transmits the post-rotation polygon information D12 and the post-rotation coordinate information D22 to the determination device 20 (step S35), and causes the inside / outside determination process to be executed.
  • the determination device 20 determines whether or not the coordinates of the determination target after rotation exist inside or outside the polygon for internal / external determination after rotation, based on the polygon information D12 after rotation and the coordinate information D22 after rotation.
  • the inside / outside determination process is performed (step S36).
  • the inside / outside determination process is the same process as step S6 shown in FIG. Further, steps S37 and S38 shown in FIG. 13 are the same processes as steps S7 and S8 shown in FIG.
  • FIG. 14 is a flowchart showing a processing procedure of the rotation process shown in FIG.
  • the rotating device 210 when the rotating device 210 receives the input of the polygon information D10 and the coordinate information D20 by the inside / outside determination control device 3 (step S41), the rotating device 210 rotates the polygon for inside / outside determination and the coordinates of the determination target. (Step S42). The rotating device 210 generates the post-rotation polygon information D12 and the post-rotation coordinate information D22, outputs the information to the inside / outside determination control device 3 (step S43), and ends the rotation process.
  • the polygon for internal / external determination and the coordinates of the determination target are preprocessed to rotate, and the MBR whose area is reduced as compared with that before the rotation is used to determine the determination target after rotation. Performs polygon inside / outside judgment processing for each coordinate of. Therefore, in the second embodiment, since the simple determination is performed using the MBR with the reduced area, the coordinates determined to be outside the polygon for internal / external determination increase only by the simple determination. As a result, in the second embodiment, the number of executions of the detailed determination can be reduced, and the entire processing time of the determination process can be shortened.
  • the inside / outside determination control device 3 rotates the polygon for inside / outside determination and the coordinates of the determination target in advance with respect to the rotation device 210, and stores the inside / outside determination control device 3 in the storage area. It may be stored, read at the time of internal / external determination, and transmitted to the determination device 20.
  • the third embodiment Before the inside / outside judgment processing by the judgment device, the polygon for inside / outside judgment is divided into a plurality of polygons having a small area, and the area of each MBR with respect to the divided polygon is reduced. , Shorten the processing time required for internal / external judgment processing.
  • FIG. 15 is a block diagram showing an example of the configuration of the determination system according to the third embodiment.
  • the determination system 301 according to the third embodiment has a division device 310 (second pretreatment device) instead of the vertex reduction device 10 as compared with the determination system 1 shown in FIG.
  • the dividing device 310 receives the polygon information D10 from the inside / outside determination control device 3 and executes preprocessing for dividing the polygon for inside / outside determination.
  • the dividing device 310 divides the polygon for internal / external determination, and outputs the divided polygon information D13 including the coordinate information of each vertex of each divided polygon to the internal / external determination control device 3.
  • the determination device 20 determines whether the coordinates of the determination target exist inside or outside the polygon for internal / external determination for each polygon for internal / external determination after division. Performs internal / external determination processing for determination.
  • FIG. 16 is a block diagram showing an example of the configuration of the dividing device 310 shown in FIG.
  • the dividing device 310 includes a communication unit 311 (second output unit), a storage unit 312, and a control unit 313.
  • the communication unit 311 has the same function as the communication unit 11 in the vertex reduction device 10.
  • the communication unit 311 receives the polygon information D10 from the inside / outside determination control device 3 via the network. Further, the communication unit 311 transmits the post-division polygon information D13 generated by the division process by the division unit 3131 (described later) for the polygon for internal / external determination to the internal / external determination control device 3.
  • the storage unit 312 has the same function as the storage unit 12 in the vertex reduction device 10.
  • the storage unit stores the polygon information D10 and the divided polygon information D13.
  • the control unit 313 has the same function as the control unit 13 in the vertex reduction device 10.
  • the control unit 313 has a division unit 3131.
  • the dividing unit 3131 acquires the polygon information D10 as a preprocessing of the inside / outside determination process, and divides the polygon for inside / outside determination into a plurality of polygons. For example, the division unit 3131 realizes the division process by using an algorithm for dividing a polygon into triangles (see, for example, Reference 3).
  • Reference 3 “Polygon triangulation inO (n log logn) time with simple data structures”, [online], [Search on August 23, 1st year of Reiwa], Internet ⁇ URL: https://link.springer.com/ article / 10.1007% 2FBF02187846 >
  • the division unit 3131 stores the post-division polygon information D13, which is the coordinate information of each vertex of each polygon divided by the division process for the polygon for internal / external determination, in the storage unit 312, and also via the communication unit 211. , This information is output to the inside / outside determination control device 3.
  • FIG. 17 is a diagram illustrating a division process.
  • FIG. 17 (1) shows the polygon P10 for internal / external determination before the division process and the coordinates C1, C2, C3 of the determination target
  • FIG. 17 (2) shows the polygon P13-1, after the division process. P13-2 and P13-3 are shown. Further, for the sake of explanation, FIG. 17 determines that the MBR40 and the divided polygons P13-1, P13-2, and P13-3 are MBR43-1, 43-2, and 43-3, respectively.
  • the target coordinates C1, C2, and C3 are also shown.
  • the MBR40 with respect to the polygon P10 is a substantially square including the coordinates C1 and C2.
  • the dividing unit 3131 uses an algorithm for dividing the polygon into triangles to divide the polygon P10 into, for example, three polygons P13-1, P13-2, and P13-3 ((FIG. 17). 2) Divide into (see).
  • the MBR including the polygons P13-1, P13-2, and P13-3 for internal / external determination after division is MBR43-1, 43-2, 43, respectively. -3 can be set. As shown in (2) of FIG. 17, these MBR43-1, 43-2, 43-3 have a smaller area than the MBR40. Then, as shown in (2) of FIG. 17, the coordinate C2 of the determination target located in the MBR40 is located outside the new MBR43-1,43-2,43-3, and only a simple determination is required. The judgment is completed.
  • the simple determination is performed using the MBR43-1, 43-2, 43-3 whose area is reduced, only the simple determination is performed and the polygon is outside the polygon for internal / external determination.
  • the number of coordinates to be determined is increased, and the number of executions of detailed determination can be reduced.
  • the coordinates to be determined in detail are only the coordinates C3 among the coordinates C1, C2, and C3.
  • FIG. 18 is a sequence diagram illustrating a processing procedure of the determination process by the determination system 301 shown in FIG.
  • Step S51 shown in FIG. 18 is the same process as step S1 shown in FIG. 7.
  • the inside / outside determination control device 3 Upon receiving the determination request, the inside / outside determination control device 3 transmits the polygon information D10 to the division device 310 (step S52) to execute the preprocessing.
  • the dividing device 310 executes a dividing process for dividing the polygon for internal / external determination into a plurality of polygons based on the polygon information D10 received from the internal / external determination control device 3 (step S53), and divides the polygon.
  • the rear polygon information D13 is transmitted to the inside / outside determination control device 3 (step S54).
  • the inside / outside determination control device 3 transmits the polygon information D13 and the coordinate information D20 after division to the determination device 20 (step S55), and causes the inside / outside determination process to be executed. Based on the divided polygon information D13 and the coordinate information D20, the determination device 20 sets the coordinates of the determination target for each of the divided polygons for internal / external determination to be inside and outside the divided polygons for internal / external determination. Performs internal / external determination processing for determining whether or not it exists (step S56).
  • the inside / outside determination process is the same process as step S6 shown in FIG. Further, steps S57 and S58 shown in FIG. 17 are the same processes as steps S7 and S8 shown in FIG.
  • FIG. 19 is a flowchart showing a processing procedure of the division processing shown in FIG.
  • the rotating device 210 when the rotating device 210 receives the input of the polygon information D10 by the inside / outside determination control device 3 (step S61), the rotating device 210 divides the polygon for inside / outside determination into a plurality of polygons (step S62). .. The dividing device 310 generates polygon information D13 after division, outputs the polygon information D13 to the inside / outside determination control device 3 (step S63), and ends the rotation process.
  • the preprocessing for dividing the polygon for internal / external determination into a plurality of polygons is performed, and the area is reduced as a whole as compared with the MBR for the polygon before the division.
  • MBR metal-oxide-semiconductor
  • polygon inside / outside judgment processing is performed for each coordinate of the judgment target. Therefore, in the third embodiment, since the simple determination is performed using a plurality of MBRs whose area is reduced as a whole, the coordinates determined to be outside the polygon for internal / external determination increase only by the simple determination. As a result, in the third embodiment, the number of executions of the detailed determination can be reduced, and the entire processing time of the determination process can be shortened.
  • the internal / external determination control device 3 divides the polygon for internal / external determination into a plurality of polygons in advance by the dividing device 310, and stores the polygon in the storage area of the internal / external determination control device 3. Then, it may be read out at the time of internal / external determination and transmitted to the determination device 20.
  • the fourth embodiment will be described.
  • the processing time required for the internal / external determination processing is further shortened by sequentially executing the preprocessing described in the first to third embodiments.
  • FIG. 20 is a block diagram showing an example of the configuration of the determination system according to the fourth embodiment.
  • the determination system 401 according to the fourth embodiment includes a vertex reduction device 10, a division device 310, and a rotation device 210 as pretreatment devices.
  • the inside / outside determination control device 3 first transmits the polygon information D10 to the vertex reduction device 10 and causes the vertex reduction device 10 to execute the vertex reduction process as the first pre-process, whereby the reduced polygon information.
  • Acquire D11 the polygon information D10 to the vertex reduction device 10 and causes the vertex reduction device 10 to execute the vertex reduction process as the first pre-process, whereby the reduced polygon information.
  • the inside / outside determination control device 3 transmits the reduced polygon information D11 to the dividing device 310, and causes the dividing process by the dividing device 310 to be executed as the second preprocessing. As a result, the inside / outside determination control device 3 acquires the vertex reduction / divided polygon information D13'after the division with respect to the polygon after the vertex reduction.
  • the inside / outside determination control device 3 transmits the polygon information D13'and the coordinate information D20 after vertex reduction / division to the rotation device 210, and causes the rotation process by the rotation device 210 to be executed as the third preprocessing.
  • the inside / outside determination control device 3 acquires the post-rotation vertex reduction / division / post-rotation polygon information D12'and the post-rotation coordinate information D22 for each polygon for inside / outside determination divided after the vertex reduction.
  • the determination device 20 determines the coordinates of the determination target for each polygon for internal / external determination after division and rotation based on the polygon information D12'after reduction / division / rotation and the coordinate information D22 after rotation. Performs internal / external determination processing to determine whether or not it exists inside or outside the polygon of.
  • FIG. 21 is a sequence diagram illustrating a processing procedure of the determination process by the determination system 401 shown in FIG.
  • Steps S71 to S74 shown in FIG. 20 are the same processes as steps S1 to S4 shown in FIG.
  • the inside / outside determination control device 3 transmits the reduced polygon information D11 to the dividing device 310 (step S75), and causes the preprocessing to be executed.
  • the dividing device 310 executes a dividing process for dividing the polygon after the vertex reduction into a plurality of polygons (step S76), and determines the inside / outside determination control device for the polygon information D13'after the vertex reduction / division. It is transmitted to 3 (step S77).
  • Step S76 is the same process as step S53 shown in FIG.
  • the inside / outside determination control device 3 transmits the polygon information D13'and the coordinate information D20 after the vertex reduction / division to the rotating device 210 (step S78), and causes the preprocessing to be executed.
  • the rotating device 210 rotates each polygon for internal / external determination and the coordinates of the determination target based on the vertex reduction / division polygon information D13'and the coordinate information D20 received from the internal / external determination control device 3.
  • the rotation process is executed (step S79), and the vertex reduction / division / post-rotation polygon information D12'and the post-rotation coordinate information D22 are transmitted to the inside / outside determination control device 3 (step S80).
  • Step S79 is the same process as step S33 shown in FIG.
  • the inside / outside determination control device 3 transmits the vertex reduction / division / post-rotation polygon information D12'and the post-rotation coordinate information D22 to the determination device 20 (step S81), and executes the inside / outside determination process.
  • the determination device 20 determines the coordinates of the determination target for each polygon for internal / external determination after division and rotation based on the polygon information D12'after reduction / division / rotation and the coordinate information D22 after rotation.
  • Performs an inside / outside determination process for determining whether or not the polygon exists inside or outside the polygon step S82).
  • the inside / outside determination process is the same process as step S6 shown in FIG. Further, steps S83 and S84 shown in FIG. 21 are the same processes as steps S7 and S8 shown in FIG.
  • the vertex reduction processing for the polygon for internal / external determination, the rotation processing for the polygon for internal / external determination after vertex reduction, and the polygon for internal / external determination after vertex reduction and rotation are performed.
  • the division process is sequentially executed as a preprocess.
  • the vertex reduction process for the polygon for internal / external determination the rotation process for the polygon for internal / external determination after vertex reduction, and the division process for the polygon for internal / external determination after vertex reduction and rotation are performed.
  • the preprocessing is performed in the order of is described as an example, the order of the preprocessing is not limited.
  • FIG. 22 is a sequence diagram for explaining the processing procedure of the determination process in the first modification of the fourth embodiment. Steps S91 to S94 shown in FIG. 22 are the same processes as steps S1 to S4 shown in FIG. 7.
  • the inside / outside determination control device 3 transmits the reduced polygon information D11 and the coordinate information D20 to the rotating device 210 (step S95), and causes the preprocessing to be executed.
  • the rotating device 210 rotates the polygon for determining the inside / outside after reducing the vertices and the coordinates of the determination target based on the reduced polygon information D11 and the coordinate information D20 received from the inside / outside determination control device 3.
  • the rotation process is executed (step S96), and the vertex reduction / post-rotation polygon information D12 ′′ and the post-rotation coordinate information D22 are transmitted to the inside / outside determination control device 3 (step S97). This is the same process as S33.
  • the inside / outside determination control device 3 transmits the post-rotation polygon information D12 ′′ and the post-rotation coordinate information D22 to the determination device 20 (step S98), and causes the inside / outside determination process to be executed. Based on the post-rotation polygon information D12 ′′ and the post-rotation coordinate information D22, whether the coordinates to be determined exist inside or outside the polygon for internal / external determination for each polygon for vertex reduction and internal / external determination after rotation.
  • the inside / outside determination process for determining the above is performed (step S99).
  • the inside / outside determination process is the same process as step S6 shown in FIG. Further, steps S100 and S101 shown in FIG. 21 are the same processes as steps S7 and S8 shown in FIG.
  • the pretreatment device may be two, the vertex reduction device 10 and the division device 310.
  • the processing procedure of the determination process in this case will be described.
  • FIG. 23 is a sequence diagram for explaining the processing procedure of the determination process in the second modification of the fourth embodiment.
  • Steps S111 to S114 shown in FIG. 23 are the same processes as steps S1 to S4 shown in FIG. 7.
  • Steps S115 to S117 shown in FIG. 23 are the same processes as steps S75 to S77 shown in FIG.
  • the inside / outside determination control device 3 transmits the polygon information D13'and the coordinate information D20 after vertex reduction / division to the determination device 20 (step S118), and causes the inside / outside determination process to be executed.
  • the determination device 20 is based on the polygon information D13'after vertex reduction / division and the coordinate information D20, and the coordinates of the determination target are polygons for internal / external determination for each polygon for internal / external determination after vertex reduction and division.
  • Performs an inside / outside determination process for determining whether or not it exists inside or outside step S119).
  • the inside / outside determination process is the same process as step S6 shown in FIG.
  • steps S120 and S121 shown in FIG. 23 are the same processes as steps S7 and S8 shown in FIG.
  • the pretreatment device may be two, a rotating device 210 and a dividing device 310.
  • the processing procedure of the determination process in this case will be described.
  • FIG. 24 is a sequence diagram for explaining the processing procedure of the determination process in the third modification of the fourth embodiment. Steps S131 to S134 shown in FIG. 24 are the same processes as steps S51 to S54 shown in FIG.
  • the inside / outside determination control device 3 transmits the polygon information D13 and the coordinate information D20 after division to the rotating device 210 (step S135), and causes the preprocessing to be executed.
  • the rotating device 210 performs a rotation process for rotating each polygon for internal / external determination and the coordinates to be determined based on the divided polygon information D13 and the coordinate information D20 received from the internal / external determination control device 3. It is executed (step S136), and the polygon information D13 "after division / rotation and the coordinate information D22 after rotation are transmitted to the inside / outside determination control device 3 (step S137).
  • Step S136 is the same process as step S33 shown in FIG. is there.
  • the inside / outside determination control device 3 transmits the polygon information D13 ′′ after division / rotation and the coordinate information D22 after rotation to the determination device 20 (step S138), and causes the inside / outside determination process to be executed. Based on the polygon information D13 "and the post-rotation coordinate information D22, it is determined whether or not the coordinates to be determined exist inside or outside the polygon for internal / external determination for each polygon for internal / external determination after division and rotation.
  • the inside / outside determination process is performed (step S139).
  • the inside / outside determination process is the same process as step S6 shown in FIG. Further, steps S140 and S141 shown in FIG. 24 are the same processes as steps S7 and S8 shown in FIG.
  • FIG. 25 is a diagram illustrating an experimental model.
  • one polygon as shown in FIG. 25 and 4000 vehicles are targeted.
  • the polygon shown in FIG. 25 is a road polygon having a long side of 7000 m, a short side of 35 m, and an interval between vertices of 1 m.
  • the vehicle provides three patterns of outside the MBR and outside the polygon, inside the MBR and outside the polygon, and inside the MBR and inside the polygon, and makes a comparison by adopting the average value of the determination results of 10 trials.
  • FIG. 26 is a diagram for explaining the PIP processing time in the case where the inside / outside determination is performed after the vertex reduction processing is performed and the case where the inside / outside determination is performed without executing the preprocessing.
  • the number of vertices was reduced to 1/2, 1/10, and 1/100 as compared with the case where the inside / outside judgment was performed without executing the preprocessing (“reference” in FIG. 26).
  • the processing time could be shortened to 0.5 times, 0.15 times, and 0.07 times the standard PIP time, respectively.
  • FIG. 27 is a diagram illustrating the division process performed in the verification.
  • the road polygon P14 (see (1) in FIG. 27) is divided into two equal parts into road polygons P14-1 and P-14-2 (see (2) in FIG. 27), and MBR44 (see FIG. 27 (2)).
  • 27 (see (1))) divided into MBR44-1, 44-2 (see (2) in FIG. 27), which has a smaller area than MBR44, and the PIP processing time without executing preprocessing.
  • the PIP processing time when the inside / outside judgment was performed was measured.
  • FIG. 28 is a diagram for explaining the PIP processing time in the case where the inside / outside determination is performed after the division processing is performed and the case where the inside / outside determination is performed without executing the preprocessing.
  • the experimental result is a model assuming that all 4000 vehicles are in a position to move out of the MBR by the division process. In this way, the model is extreme because it is used as the basis for the estimated value of how much the improvement effect of the method can be expected.
  • the total time required for 4000 vehicles in the MBR to be PIP processed was 7984 ms (“No division” in FIG. 28).
  • the division process is executed and the inside / outside determination is performed, all 4000 vehicles in the MBR are "outside the MBR", so the process is completed only by the simple determination. In other words, by the division process, the cross product calculation for the vehicle outside the MBR can be omitted. Therefore, when the division process was executed and the inside / outside determination was performed (“with division” in FIG. 28), the total time required for the inside / outside determination process for 4000 units outside the MBR was 1.4 ms.
  • the total processing time which is the sum of the division processing time and the PIP processing time, is shortened to 0.00018 times the processing time when the preprocessing is not executed. I was able to do it.
  • FIG. 29 is a diagram illustrating the rotation process performed in the verification.
  • the PIP processing time when the road polygon P14 (see (1) in FIG. 29) and the vehicle are rotated by 45 ° (see (2) in FIG. 29) is used.
  • the PIP processing time when the inside / outside judgment was performed without executing the preprocessing was measured.
  • the MBR becomes the MBR44-3 having a smaller area than the MBR44 according to the road polygon P15 rotated by 45 °.
  • the experimental results are based on the assumption that all 4000 vehicles are in a position to move out of the MBR by rotation processing. In this way, the model is extreme because it is used as the basis for the estimated value of how much the improvement effect of the method can be expected.
  • the rotation processing time was as short as 1/10000 or less of the PIP processing time.
  • FIG. 30 is a diagram for explaining the PIP processing time in the case where the inside / outside determination is performed after the rotation processing is performed and the case where the inside / outside determination is performed without executing the preprocessing.
  • the total time required for the 4000 vehicles in the MBR to be PIP-processed was 8127 ms (“no rotation” in FIG. 30).
  • the total processing time which is the sum of the rotation processing time and the PIP processing time, is shortened to 0.0004 times the processing time when the preprocessing is not executed. I was able to do it.
  • FIG. 31 is a diagram illustrating another application example of the determination system according to the first to fourth embodiments.
  • the determination system according to the first to fourth embodiments can be applied to the coordinate determination (region: sea route) of the ship on the sea route.
  • the width of the sea route is widened to Wm (W can be freely set).
  • the determination system according to the first to fourth embodiments replaces the road with a new sea route, replaces the automobile with a ship, and determines the position of the ship at sea.
  • the determination system according to the first to fourth embodiments can be applied to tracking fish (area: river) with a coordinate sensor. Specifically, the determination system according to the first to fourth embodiments replaces a road with a river, replaces an automobile with a fish, and determines the position of a fish on the river.
  • each component of the vertex reduction device 10 shown in FIG. 2, the determination device 20 shown in FIG. 4, the rotating device 210 shown in FIG. 11, and the dividing device 310 shown in FIG. 16 is functionally conceptual and is not necessarily physically illustrated. It does not need to be configured as. That is, the specific form of the distribution and integration of the functions of the vertex reduction device 10, the determination device 20, the rotating device 210, and the dividing device 310 is not limited to the one shown in the drawing, and all or a part thereof may be used in various loads or usage conditions. Depending on the unit, it can be functionally or physically distributed or integrated.
  • each process performed by the vertex reduction device 10, the determination device 20, the rotation device 210, and the division device 310 may be realized by a CPU and a program in which an arbitrary part is analyzed and executed by the CPU. Further, each process performed by the vertex reduction device 10 may be realized as hardware by wired logic.
  • FIG. 32 is a diagram showing an example of a computer in which the vertex reduction device 10, the determination device 20, the rotation device 210, and the division device 310 are realized by executing the program.
  • the computer 1000 has, for example, a memory 1010 and a CPU 1020.
  • the computer 1000 also has a hard disk drive interface 1030, a disk drive interface 1040, a serial port interface 1050, a video adapter 1060, and a network interface 1070. Each of these parts is connected by a bus 1080.
  • Memory 1010 includes ROM 1011 and RAM 1012.
  • the ROM 1011 stores, for example, a boot program such as a BIOS (Basic Input Output System).
  • BIOS Basic Input Output System
  • the hard disk drive interface 1030 is connected to the hard disk drive 1090.
  • the disk drive interface 1040 is connected to the disk drive 1100.
  • a removable storage medium such as a magnetic disk or an optical disk is inserted into the disk drive 1100.
  • the serial port interface 1050 is connected to, for example, a mouse 1110 and a keyboard 1120.
  • the video adapter 1060 is connected to, for example, the display 1130.
  • the hard disk drive 1090 stores, for example, an OS (Operating System) 1091, an application program 1092, a program module 1093, and program data 1094. That is, the program that defines each process of the vertex reduction device 10, the determination device 20, the rotating device 210, and the dividing device 310 is implemented as a program module 1093 in which a code that can be executed by the computer 1000 is described.
  • the program module 1093 is stored in, for example, the hard disk drive 1090.
  • the program module 1093 for executing the same processing as the functional configuration in the vertex reduction device 10, the determination device 20, the rotating device 210, and the dividing device 310 is stored in the hard disk drive 1090.
  • the hard disk drive 1090 may be replaced by an SSD (Solid State Drive).
  • the setting data used in the processing of the above-described embodiment is stored as program data 1094 in, for example, a memory 1010 or a hard disk drive 1090. Then, the CPU 1020 reads the program module 1093 and the program data 1094 stored in the memory 1010 and the hard disk drive 1090 into the RAM 1012 as needed, and executes the program.
  • the program module 1093 and the program data 1094 are not limited to those stored in the hard disk drive 1090, but may be stored in, for example, a removable storage medium and read by the CPU 1020 via the disk drive 1100 or the like. Alternatively, the program module 1093 and the program data 1094 may be stored in another computer connected via a network (LAN (Local Area Network), WAN (Wide Area Network), etc.). Then, the program module 1093 and the program data 1094 may be read by the CPU 1020 from another computer via the network interface 1070.
  • LAN Local Area Network
  • WAN Wide Area Network
  • Judgment system 2 Client terminal 3 Inside / outside judgment control device 10 Vertex reduction device 11,1,2,111,311 Communication unit 12,22,212,312 Storage unit 13,23,213,313 Control unit 20 Judgment Device 131 Vertex reduction part 231 Inside / outside judgment part 210 Rotating device 310 Splitting device 2131 Rotating part 3131 Dividing part

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Computer Graphics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Geometry (AREA)
  • General Engineering & Computer Science (AREA)
  • Computer Hardware Design (AREA)
  • Architecture (AREA)
  • Remote Sensing (AREA)
  • Image Generation (AREA)
  • Processing Or Creating Images (AREA)

Abstract

回転装置（２１０）は、判定対象である座標が内外判定用の多角形の内外に存在するかを判定する判定処理の前処理として、内外判定用の多角形の各頂点の座標情報と、内外判定用の多角形の各頂点の座標情報とを取得し、判定対象である座標と内外判定用の多角形とを回転する回転部（２１３１）と、回転後の内外判定用の多角形の各頂点の座標情報と、回転後の判定対象である座標とを回転後座標情報として出力する通信部（２１１）と、を有する。

Description

前処理装置、判定システム、前処理方法および前処理プログラム
　本発明は、前処理装置、判定システム、前処理方法および前処理プログラムに関する。
　特定の座標が、特定の多角形の内部に含まれるかを判定する多角形内外判定技術がある。多角形内外判定技術は、例えば、地理上の自動車等の座標が、道路領域を表現した多角形に含まれるかを判定する場合に適用される。
　例えば、従来の多角形内外判定技術として、Crossing　Number法およびWinding　Number法による判定技術がある（例えば、非特許文献１参照）。これらの判定技術は、判定対象の多角形の全ての辺と判定対象の座標の位置関係を集計することで、座標が多角形の内部に含まれるかを判定するものである。
　また、従来の多角形内外判定技術として、bounding　containerによる簡易判定技術がある（例えば、非特許文献２参照）。このbounding　containerとは、判定対象の多角形を含むような図形である。この技術は、bounding　containerとして、内外判定を高速に実行可能な図形を選択し、bounding　containerに含まれる座標のみにCrossing　Number法やWinding　Number法を適用することで、平均処理時間を削減する技術である。上記のbounding　containerとして、ＸＹ軸に平行な辺を持つ長方形（ＭＢＲ：Minimal　Bounding　Rectangle）が一般に用いられる。
"Inclusion　of　a　Point　in　a　Polygon",［online］，［令和１年８月２３日検索］，インターネット＜ＵＲＬ：http://geomalgorithms.com/a03-_inclusion.html＞ "Bounding　Containers　for　Point　Sets",［online］，［令和１年８月２３日検索］，インターネット＜ＵＲＬ：http://geomalgorithms.com/a08-_containers.html＞
　道路領域に地理上の自動車等が含まれるか否かの判定に多角形内外判定技術が適用される場合、この多角形は、道路領域を表現するため、多量の頂点を持ち、細長い形状をしているという特徴を有する。
　しかしながら、Crossing　Number法およびWinding　Number法は、処理時間が頂点数に比例するという性質があるため、多量の頂点を持つ多角形に対して判定を行うと、処理時間が長くなるという問題がある。また、ＭＢＲは、細長い多角形に対しては、多角形外の領域も多く含んでしまうという性質があるため、細長い形状を有する多角形に対して判定を行うと、平均処理時間の短縮効果が出にくいという問題がある。
　本発明は、上記に鑑みてなされたものであって、多角形内外判定処理に要する処理時間を短縮することができる前処理装置、判定システム、前処理方法および前処理プログラムを提供することを目的とする。
　上述した課題を解決し、目的を達成するために、本発明の前処理装置は、判定対象である座標が内外判定用の多角形の内外に存在するかを判定する判定処理の前処理として、内外判定用の多角形の各頂点の座標情報を取得し、内外判定用の多角形の頂点を削減する削減部と、削減部が頂点を削減した後の多角形の各頂点の座標情報を、判定処理を行う装置に出力する出力部と、を有することを特徴とする。
　また、本発明の判定システムは、判定対象である座標が内外判定用の多角形の内外に存在するか否かを判定する判定装置と、判定処理の前処理を行う第１の前処理装置と、を有する判定システムにおいて、第１の前処理装置は、内外判定用の多角形の各頂点の座標情報を取得し、内外判定用の多角形の頂点を削減する第１の前処理を行う削減部と、削減部が頂点を削減した後の多角形の各頂点の座標情報である削減後多角形情報を出力する出力部と、を有し、判定装置は、前処理後の情報を用いて、判定対象である座標が内外判定用の多角形の内外に存在するか否かを判定することを特徴とする。
　また、本発明の前処理方法は、前処理装置が行う前処理方法であって、判定対象である座標が内外判定用の多角形の内外に存在するかを判定する判定処理の前処理として、内外判定用の多角形の各頂点の座標情報を取得し、内外判定用の多角形の頂点を削減する工程と、頂点を削減された後の多角形の各頂点の座標情報を、判定処理を行う装置に出力する工程と、を含んだことを特徴とする。
　また、本発明の前処理プログラムは、判定対象である座標が内外判定用の多角形の内外に存在するかを判定する判定処理の前処理として、内外判定用の多角形の各頂点の座標情報を取得し、内外判定用の多角形の頂点を削減するステップと、頂点を削減された後の多角形の各頂点の座標情報を、判定処理を行う装置に出力するステップと、をコンピュータに実行させる。
　本発明によれば、多角形内外判定処理に要する処理時間を短縮することができる。
図１は、実施の形態１に係る判定システムの構成の一例を示すブロック図である。 図２は、図１に示す頂点削減装置の構成の一例を示すブロック図である。 図３は、多角形情報のデータ構成の一覧を示す図である。 図４は、図１に示す判定装置の構成の一例を示すブロック図である。 図５は、座標情報のデータ構成の一覧を示す図である。 図６は、頂点削減処理を説明する図である。 図７は、図１に示す判定システムによる判定処理の処理手順を説明するシーケンス図である。 図８は、図７に示す頂点削減処理の処理手順を示すフローチャートである。 図９は、図７に示す内外判定処理の処理手順を示すフローチャートである。 図１０は、実施の形態２に係る判定システムの構成の一例を示すブロック図である。 図１１は、図１０に示す回転装置の構成の一例を示すブロック図である。 図１２は、回転処理を説明する図である。 図１３は、図１０に示す判定システムによる判定処理の処理手順を説明するシーケンス図である。 図１４は、図１３に示す回転処理の処理手順を示すフローチャートである。 図１５は、実施の形態３に係る判定システムの構成の一例を示すブロック図である。 図１６は、図１５に示す分割装置の構成の一例を示すブロック図である。 図１７は、分割処理を説明する図である。 図１８は、図１５に示す判定システムによる判定処理の処理手順を説明するシーケンス図である。 図１９は、図１８に示す分割処理の処理手順を示すフローチャートである。 図２０は、実施の形態４に係る判定システムの構成の一例を示すブロック図である。 図２１は、図２０に示す判定システムによる判定処理の処理手順を説明するシーケンス図である。 図２２は、実施の形態４の変形例１における判定処理の処理手順を説明するシーケンス図である。 図２３は、実施の形態４の変形例２における判定処理の処理手順を説明するシーケンス図である。 図２４は、実施の形態４の変形例３における判定処理の処理手順を説明するシーケンス図である。 図２５は、実験モデルを説明する図である。 図２６は、頂点削減処理を実施した後に内外判定を行った場合と、前処理を実行せずに内外判定を行った場合とにおけるＰＩＰ処理時間を説明する図である。 図２７は、検証において実施した分割処理を説明する図である。 図２８は、分割処理を実施した後に内外判定を行った場合と、前処理を実行せずに内外判定を行った場合とにおけるＰＩＰ処理時間を説明する図である。 図２９は、検証において実施した回転処理を説明する図である。 図３０は、回転処理を実施した後に内外判定を行った場合と、前処理を実行せずに内外判定を行った場合とにおけるＰＩＰ処理時間を説明する図である。 図３１は、実施の形態１～４に係る判定システムの他の適用例を説明する図である。 図３２は、プログラムが実行されることにより、頂点削減装置、判定装置、回転装置及び分割装置が実現されるコンピュータの一例を示す図である。
　以下に、本願に係る前処理装置、判定システム、前処理方法および前処理プログラムの実施形態を図面に基づいて詳細に説明する。また、本発明は、以下に説明する実施形態により限定されるものではない。
［実施の形態１］
　まず、実施の形態１について説明する。本実施の形態１では、判定対象である座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理の前に、内外判定用の多角形の頂点を削減することによって、内外判定処理に要する処理時間を短縮する。
［判定システムの構成］
　図１は、実施の形態１に係る判定システムの構成の一例を示すブロック図である。図１に示すように、本実施の形態１に係る判定システム１は、クライアント端末２、内外判定制御装置３、頂点削減装置１０及び判定装置２０を有する。クライアント端末２、内外判定制御装置３は、ネットワーク等を介して接続する。内外判定制御装置３、頂点削減装置１０及び判定装置２０は、ネットワーク等を介して接続する。
　クライアント端末２は、判定システム１の利用者が使用する端末装置である。クライアント端末２は、判定対象である座標の座標情報Ｄ２０と、内外判定用の多角形の各頂点の座標情報である多角形情報Ｄ１０とを、内外判定制御装置３に送信し、判定依頼を行う。
　内外判定制御装置３は、頂点削減装置１０及び判定装置２０における処理を制御するサーバ装置である。内外判定制御装置３は、クライアント端末２による判定依頼を受けると、判定装置２０に、判定対象である座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理（判定処理）を実行させて、判定結果をクライアント端末２に返信する。また、本実施の形態１では、内外判定制御装置３は、判定装置２０が内外判定処理を実行する前に、内外判定処理の前処理を頂点削減装置１０に実行させる。
　頂点削減装置１０は、内外判定制御装置３から多角形情報Ｄ１０を受信し、内外判定用の多角形の頂点を削減する前処理を実行する。頂点削減装置１０は、頂点を削減した後の多角形の各頂点の座標情報である削減後多角形情報Ｄ１１を内外判定制御装置３に出力する。
　判定装置２０は、判定対象である座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う。この際、判定装置２０は、削減後多角形情報Ｄ１１と、判定対象である座標の座標情報Ｄ２０とを基に、内外判定処理を行う。判定装置２０は、判定結果を含む判定情報を内外判定制御装置３に出力する。
［頂点削減装置］
　次に、図１に示す頂点削減装置１０について説明する。図２は、図１に示す頂点削減装置１０の構成の一例を示すブロック図である。図２に示すように、頂点削減装置１０は、通信部１１、記憶部１２及び制御部１３を有する。
　通信部１１は、ネットワーク等を介して接続された他の装置との間で、各種情報を送受信する通信インタフェースである。通信部１１は、ＮＩＣ（Network　Interface　Card）等で実現され、ＬＡＮ（Local　Area　Network）やインターネットなどの電気通信回線を介した他の装置と制御部１３（後述）との間の通信を行う。
　通信部１１は、ネットワークを介して、内外判定制御装置３から多角形情報Ｄ１０を受信する。また、通信部１１は、削減後多角形情報Ｄ１１を、内外判定制御装置３に送信する。
　記憶部１２は、ＲＡＭ（Random　Access　Memory）、フラッシュメモリ（Flash　Memory）等の半導体メモリ素子、または、ハードディスク、光ディスク等の記憶装置によって実現され、頂点削減装置１０を動作させる処理プログラムや、処理プログラムの実行中に使用されるデータなどが記憶される。記憶部１２は、多角形情報Ｄ１０及び削減後多角形情報Ｄ１１を記憶する。
　多角形情報Ｄ１０は、内外判定用の多角形の各頂点の座標情報である。多角形情報Ｄ１０は、内外判定制御装置３から送信される。図３は、多角形情報Ｄ１０のデータ構成の一覧を示す図である。図３に示すように、多角形情報Ｄ１０は、内外判定用の多角形の頂点の座標のリストであり、例えば、内外判定用の多角形が１００個の頂点を有する場合には、１００組の座標を有する。
　削減後座標情報Ｄ１１は、内外判定用の多角形の各頂点に対する頂点削減部１３１（後述）の処理によって頂点が削減された多角形の各頂点の座標情報である。削減後座標情報Ｄ１１は、例えば、１００個から６０個に頂点が削減された多角形の各頂点の座標リストである。
　制御部１３は、頂点削減装置１０全体を制御する。制御部１３は、例えば、ＣＰＵ（Central　Processing　Unit）、ＭＰＵ（Micro　Processing　Unit）等の電子回路や、ＡＳＩＣ（Application　Specific　Integrated　Circuit）、ＦＰＧＡ（Field　Programmable　Gate　Array）等の集積回路である。また、制御部１３は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、内部メモリを用いて各処理を実行する。また、制御部１３は、各種のプログラムが動作することにより各種の処理部として機能する。制御部１３は、頂点削減部１３１（削減部）を有する。
　頂点削減部１３１は、内外判定処理の前処理として、多角形情報Ｄ１０を取得し、内外判定用の多角形の頂点を削減する。頂点削減部１３１は、内外判定用の多角形の頂点に対して、適当な間隔で間引きする処理を行う。例えば、頂点削減部１３１は、Ramer-Douglas-Peuckerのアルゴリズム（例えば、参考文献１参照）などを用いて、頂点削減処理を実現する。
　参考文献１：“Ramer－Douglas－Peucker　Algorithm”,［online］，［令和１年８月２３日検索］，インターネット＜ＵＲＬ：https://siguniang.wordpress.com/2012/07/16/ramer-douglas-peucker-algorithm/＞
　頂点削減部１３１は、内外判定用の多角形の各頂点に対する頂点削減処理によって頂点が削減された多角形の各頂点の座標情報である削減後座標情報Ｄ１１を、記憶部１２に格納するとともに、通信部１１を介して、この情報を内外判定制御装置３に出力する。
［判定装置］
　次に、図１に示す判定装置２０について説明する。図４は、図１に示す判定装置２０の構成の一例を示すブロック図である。図４に示すように、判定装置２０は、通信部２１、記憶部２２及び制御部２３を有する。
　通信部２１は、ネットワーク等を介して接続された他の装置との間で、各種情報を送受信する通信インタフェースであり、ＮＩＣ等で実現され、ＬＡＮやインターネットなどの電気通信回線を介した他の装置と制御部２３（後述）との間の通信を行う。通信部２１は、ネットワークを介して、内外判定制御装置３から、内外判定用の多角形の各頂点の座標情報として、削減後多角形情報Ｄ１１を受信するとともに、座標情報Ｄ２０を受信する。また、通信部２１は、内外判定部２３１（後述）の判定結果を、内外判定制御装置３に送信する。
　記憶部２２は、ＲＡＭ、フラッシュメモリ等の半導体メモリ素子、または、ハードディスク、光ディスク等の記憶装置によって実現され、判定装置２０を動作させる処理プログラムや、処理プログラムの実行中に使用されるデータなどが記憶される。記憶部２２は、削減後多角形情報Ｄ１１及び座標情報Ｄ２０を記憶する。
　座標情報Ｄ２０は、判定対象である座標の座標情報である。座標情報Ｄ２０は、内外判定制御装置３から送信される。図５は、座標情報Ｄ２０のデータ構成の一覧を示す図である。図５に示すように、座標情報Ｄ２０は、判定対象である座標の経度及び緯度を示す。
　制御部２３は、頂点削減装置１０全体を制御する。制御部２３は、例えば、ＣＰＵ、ＭＰＵ等の電子回路や、ＡＳＩＣ、ＦＰＧＡ等の集積回路である。また、制御部２３は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、内部メモリを用いて各処理を実行する。また、制御部２３は、各種のプログラムが動作することにより各種の処理部として機能する。制御部２３は、内外判定部２３１を行う。
　内外判定部２３１は、削減後多角形情報Ｄ１１と座標情報Ｄ２０とを基に、判定対象である座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う。内外判定部２３１は、ＭＢＲによる簡易判定後に、Crossing　Number法またはWinding　Number法による詳細判定を実行する。
［頂点削減処理］
　次に、頂点削減装置１０が実行する頂点削減処理について具体的に説明する。図６は、頂点削減処理を説明する図である。図６の（１）は、頂点削減処理前の内外判定用の多角形Ｐ１０を示し、図６の（２）は、頂点削減処理後の多角形Ｐ１１を示す。説明のために、図６は、ＭＢＲ４０、判定対象である座標Ｃ１，Ｃ２，Ｃ３も示す。
　図６の（１）に示す多角形Ｐ１０は、頂点の数が１６個である。頂点削減装置１０では、頂点削減部１３１が、Ramer-Douglas-Peuckerのアルゴリズムを用いて、多角形Ｐ１０の頂点を削減する。Ramer-Douglas-Peuckerのアルゴリズムは、（Ａ）ルートの始点、終点をプロット対象とし、（Ｂ）プロット対象をつなげた直線と、その間の各点との距離を調べ、許容距離以上離れた点で、最も離れた点を探し出し、（Ｃ）そこを新たにプロット対象とし、（Ｂ），（Ｃ）の処理を再帰的に繰り返し、（Ｄ）ε以上離れた点がなければ、終了とするアルゴリズムである。
　この処理により、図６の（２）に示すように、頂点削減部１３１は、頂点の数が１６個である多角形Ｐ１０と比して、頂点の数が１０個にまで削減された多角形Ｐ１１を生成する。そして、判定装置２０では、この多角形Ｐ１１を内外判定用の多角形として判定処理を行う。
　この場合、詳細判定が必要である座標Ｃ２，Ｃ３については、頂点が削減された多角形Ｐ１１を基に詳細判定が実行されるため、当初の内外判定用の多角形Ｐ１０を対象として詳細判定を行う場合と比較して、詳細判定処理の処理時間を短縮することができる。なお、座標Ｃ１については、ＭＢＲ４０の外側であるため、簡易判定のみで判定が終了となる。
［判定処理の処理手順］
　次に、判定システム１における判定処理の処理手順について説明する。図７は、図１に示す判定システム１による判定処理の処理手順を説明するシーケンス図である。
　まず、クライアント端末２は、判定対象である座標の座標情報Ｄ２０と、内外判定用の多角形の各頂点の座標情報である多角形情報Ｄ１０とを、内外判定制御装置３に送信し、判定依頼を行う（ステップＳ１）。内外判定制御装置３は、判定依頼を受けると、多角形情報Ｄ１０を頂点削減装置１０に送信し（ステップＳ２）、前処理を実行させる。
　頂点削減装置１０は、前処理として、内外判定制御装置３から受信した多角形情報Ｄ１０を基に、内外判定用の多角形の頂点を削減する頂点削減処理を実行し（ステップＳ３）、削減後多角形情報Ｄ１１を内外判定制御装置３に送信する（ステップＳ４）。
　内外判定制御装置３は、削減後多角形情報Ｄ１１と座標情報Ｄ２０とを判定装置２０に送信し（ステップＳ５）、内外判定処理を実行させる。内外判定制御装置３は、削減後多角形情報Ｄ１１と座標情報Ｄ２０とを基に、内外判定処理を行い（ステップＳ６）、判定情報を内外判定制御装置３に送信する（ステップＳ７）。内外判定制御装置３は、判定情報をクライアント端末２に送信する（ステップＳ８）。
［頂点削減処理の処理手順］
　次に、頂点削減処理（ステップＳ３）の処理手順について説明する。図８は、図７に示す頂点削減処理の処理手順を示すフローチャートである。
　図８に示すように、頂点削減装置１０は、内外判定制御装置３による多角形情報Ｄ１０の入力を受け付けると（ステップＳ１１）、内外判定用の多角形の頂点を削減する（ステップＳ１２）。頂点削減装置１０は、削減後多角形情報Ｄ１１を生成し、内外判定制御装置３に出力して（ステップＳ１３）、頂点削減処理を終了する。
［内外判定処理の処理手順］
　次に、内外判定処理（ステップＳ６）の処理手順について説明する。図９は、図７に示す内外判定処理の処理手順を示すフローチャートである。
　図９に示すように、判定装置２０は、判定対象の座標はＭＢＲの内側か否かを判定する簡易判定処理を行う（ステップＳ２１）。判定装置２０は、判定対象の座標はＭＢＲの内側でないと判定した場合（ステップＳ２１：Ｎｏ）、この座標は内外判定用の多角形の外側である（「false」）と判定する（ステップＳ２２）。
　一方、判定装置２０は、判定対象の座標はＭＢＲの内側であると判定した場合（ステップＳ２１：Ｙｅｓ）、Crossing　Number法またはWinding　Number法による詳細判定を行う。この場合、判定装置２０は、削減後多角形情報Ｄ１１に示された多角形を内外判定対象の多角形とし、判定対象の座標は内外判定用の多角形の内側か否かを判定する（ステップＳ２３）。
　判定装置２０は、判定対象の座標は内外判定用の多角形の内側でないと判定した場合（ステップＳ２３：Ｎｏ）、ステップＳ２２に進み、この座標は内外判定用の多角形の外側である（「false」）と判定する（ステップＳ２２）。
　これに対し、判定装置２０は、判定対象の座標は内外判定用の多角形の内側であると判定した場合（ステップＳ２３：Ｙｅｓ）、この座標は内外判定用の多角形の内側である（「true」）と判定する（ステップＳ２４）。
　判定装置２０は、判定対象の座標ごとにステップＳ２１～ステップＳ２４の処理を実行し、判定対象の座標ごとに判定結果を対応付けた判定情報を内外判定制御装置３に送信する。
［実施の形態１の効果］
　このように、実施の形態１では、内外判定用の多角形の頂点を削減する前処理を行い、頂点が削減された多角形を用いて各座標に対する多角形内外判定処理を行う。したがって、実施の形態１では、詳細判定処理時に、頂点が削減された多角形を基に詳細判定が実行されるため、当初の内外判定用の多角形を対象として詳細判定を行う場合と比較して、詳細判定処理の処理時間を短縮することができる。
　本実施の形態１は、特に、地理上の自動車等の座標が道路領域を表現した多角形に含まれるかの判定に適用された場合、多量の頂点を持つ道路領域を表現した多角形に対して予め頂点を削減してから詳細判定処理を行うため、判定処理の処理時間を高速化することができる。
　なお、本実施の形態１では、内外判定制御装置３は、頂点削減装置１０に対し、事前に内外判定用の多角形の頂点を削減させて、内外判定制御装置３の記憶領域に格納し、内外判定時に読み出して、判定装置２０に送信してもよい。
［実施の形態２］
　次に、実施の形態２について説明する。実施の形態２では、判定装置による内外判定処理の前に、内外判定用の多角形及び判定対象の座標を回転し、回転後の多角形を含むＭＢＲの領域を削減することによって、内外判定処理に要する処理時間を短縮する。
　図１０は、実施の形態２に係る判定システムの構成の一例を示すブロック図である。図１０に示すように実施の形態２に係る判定システム２０１は、図１に示す判定システム１と比して、頂点削減装置１０に代えて回転装置２１０（前処理装置、第１の前処理装置）を有する。
　回転装置２１０は、内外判定制御装置３から多角形情報Ｄ１０及び座標情報Ｄ２０を受信し、内外判定用の多角形及び判定対象の座標を回転する前処理を実行する。回転装置２１０は、回転後の多角形の各頂点の座標情報である回転後多角形情報Ｄ１２と、回転後の判定対象の座標の座標情報である回転後座標情報Ｄ２２を内外判定制御装置３に出力する。
　判定装置２０は、回転後多角形情報Ｄ１２と回転後座標情報Ｄ２２とを基に、回転後の判定対象の座標が、回転後の内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う。
［回転装置］
　次に、図１０に示す回転装置２１０について説明する。図１１は、図１０に示す回転装置２１０の構成の一例を示すブロック図である。図１１に示すように、回転装置２１０は、通信部２１１（出力部、第１の出力部）、記憶部２１２及び制御部２１３を有する。
　通信部２１１は、頂点削減装置１０における通信部１１と同様の機能を有する。通信部２１１は、ネットワークを介して、内外判定制御装置３から多角形情報Ｄ１０及び座標情報Ｄ２０を受信する。また、通信部２１１は、内外判定用の多角形及び判定対象の座標に対する回転部２１３１（後述）による回転処理によって生成された回転後多角形情報Ｄ１２と回転後座標情報Ｄ２２とを、内外判定制御装置３に送信する。
　記憶部２１２は、頂点削減装置１０における記憶部１２と同様の機能を有する。記憶部３１２は、多角形情報Ｄ１０、座標情報Ｄ２０、回転後多角形情報Ｄ１２及び回転後座標情報Ｄ２２を記憶する。
　制御部２１３は、頂点削減装置１０における制御部１３と同様の機能を有する。制御部２１３は、回転部２１３１を有する。
　回転部２１３１は、内外判定処理の前処理として、多角形情報Ｄ１０及び座標情報Ｄ２０を取得し、内外判定用の多角形と判定対象の座標とを回転する。例えば、回転部２１３１は、回転角の導出アルゴリズム（例えば、参考文献２参照）などを用いて、回転処理を実現する。
　参考文献２：“Minimum-Area　Rectangle　Containing　a　Set　of　Points”,［online］，［令和１年８月２３日検索］，インターネット＜ＵＲＬ：https://www.geometrictools.com/Documentation/MinimumAreaRectangle.pdf＞
　回転部２１３１は、回転後多角形情報Ｄ１２と回転後座標情報Ｄ２２とを、記憶部２１２に格納するとともに、通信部２１１を介して、これらの情報を内外判定制御装置３に出力する。
［回転処理］
　次に、回転装置２１０が実行する回転処理について具体的に説明する。図１２は、回転処理を説明する図である。図１２の（１）は、回転処理前の内外判定用の多角形Ｐ１０及び判定対象の座標Ｃ１，Ｃ２，Ｃ３を示し、図１２の（２）は、回転処理後の多角形Ｐ１１及び回転後の座標Ｃ１２，Ｃ２２，Ｃ３２を示す。また、説明のために、図１２は、回転処理前のＭＢＲ４０と、回転処理後に設定されるＭＢＲ４２も示す。
　図１２の（１）に示すように、多角形Ｐ１０に対するＭＢＲ４０は、座標Ｃ１，Ｃ２を含む略正方形である。回転装置２１０では、回転部２１３１が、回転角の導出のアルゴリズムを用いて、多角形Ｐ１０及び判定対象の座標Ｃ１，Ｃ２，Ｃ３を適宜回転する。
　この処理により、図１２の（２）に示すように、回転後の内外判定用の多角形Ｐ１２を含むＭＢＲとして、ＭＢＲ４０よりも領域が削減されたＭＢＲ４２を設定できる。さらに、判定対象の座標Ｃ２２は、回転により、新たなＭＢＲ４２外に位置することになり、簡易判定のみで判定が終了される。
　この結果、判定装置２０による判定処理では、領域が削減されたＭＢＲ４２を用いて簡易判定を行うため、簡易判定のみで、内外判定用の多角形外であると判定される座標が増え、詳細判定の実行回数を減らすことができる。図１２の例では、詳細判定の対象となる座標は、座標Ｃ１２，Ｃ２２，Ｃ２３のうち、座標Ｃ３２のみとなる。
［判定処理の処理手順］
　次に、判定システム２０１における判定処理の処理手順について説明する。図１３は、図１０に示す判定システム２０１による判定処理の処理手順を説明するシーケンス図である。
　図１３に示すステップＳ３１は、図７に示すステップＳ１と同じ処理である。内外判定制御装置３は、判定依頼を受けると、多角形情報Ｄ１０及び座標情報Ｄ２０を、回転装置２１０に送信し（ステップＳ３２）、前処理を実行させる。
　回転装置２１０は、前処理として、内外判定制御装置３から受信した多角形情報Ｄ１０及び座標情報Ｄ２０を基に、内外判定用の多角形と判定対象の座標とを回転する回転処理を実行し（ステップＳ３３）、回転後多角形情報Ｄ１２及び回転後座標情報Ｄ２２を内外判定制御装置３に送信する（ステップＳ３４）。
　内外判定制御装置３は、回転後多角形情報Ｄ１２及び回転後座標情報Ｄ２２を判定装置２０に送信し（ステップＳ３５）、内外判定処理を実行させる。判定装置２０は、回転後多角形情報Ｄ１２と、回転後座標情報Ｄ２２とを基に、回転後の判定対象の座標が、回転後の内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う（ステップＳ３６）。なお、内外判定処理は、図７に示すステップＳ６と同じ処理である。また、図１３に示すステップＳ３７，Ｓ３８は、図７に示すステップＳ７，Ｓ８と同じ処理である。
［回転処理の処理手順］
　次に、回転処理（ステップＳ３３）の処理手順について説明する。図１４は、図１３に示す回転処理の処理手順を示すフローチャートである。
　図１４に示すように、回転装置２１０は、内外判定制御装置３による多角形情報Ｄ１０及び座標情報Ｄ２０の入力を受け付けると（ステップＳ４１）、内外判定用の多角形及び判定対象の座標を回転する（ステップＳ４２）。回転装置２１０は、回転後多角形情報Ｄ１２及び回転後座標情報Ｄ２２を生成し、内外判定制御装置３に出力して（ステップＳ４３）、回転処理を終了する。
［実施の形態２の効果］
　このように、実施の形態２では、内外判定用の多角形及び判定対象の座標を回転する前処理を行い、回転前と比して領域が削減されたＭＢＲを用いて、回転後の判定対象の各座標に対する多角形内外判定処理を行う。したがって、実施の形態２では、領域が削減されたＭＢＲを用いて簡易判定を行うため、簡易判定のみで内外判定用の多角形外であると判定される座標が増える。これによって、実施の形態２では、詳細判定の実行回数を減らすことができ、判定処理の処理時間全体を短縮することができる。
　なお、本実施の形態２では、内外判定制御装置３は、回転装置２１０に対し、事前に内外判定用の多角形と判定対象の座標とを回転させて、内外判定制御装置３の記憶領域に格納し、内外判定時に読み出して、判定装置２０に送信してもよい。
［実施の形態３］
　次に、実施の形態３について説明する。実施の形態３では、判定装置による内外判定処理の前に、内外判定用の多角形を、領域の小さな複数の多角形に分割し、分割後の多角形に対する各ＭＢＲの領域を削減することによって、内外判定処理に要する処理時間を短縮する。
　図１５は、実施の形態３に係る判定システムの構成の一例を示すブロック図である。図１５に示すように実施の形態３に係る判定システム３０１は、図１に示す判定システム１と比して、頂点削減装置１０に代えて分割装置３１０（第２の前処理装置）を有する。
　分割装置３１０は、内外判定制御装置３から多角形情報Ｄ１０を受信し、内外判定用の多角形を分割する前処理を実行する。分割装置３１０は、内外判定用の多角形を分割して、分割後の各多角形の各頂点の座標情報を含む分割後多角形情報Ｄ１３を、内外判定制御装置３に出力する。
　判定装置２０は、分割後多角形情報Ｄ１３と座標情報Ｄ２０とを基に、分割後の内外判定用の多角形ごとに、判定対象の座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う。
［分割装置］
　次に、図１５に示す分割装置３１０について説明する。図１６は、図１５に示す分割装置３１０の構成の一例を示すブロック図である。図１６に示すように、分割装置３１０は、通信部３１１（第２の出力部）、記憶部３１２及び制御部３１３を有する。
　通信部３１１は、頂点削減装置１０における通信部１１と同様の機能を有する。通信部３１１は、ネットワークを介して、内外判定制御装置３から多角形情報Ｄ１０を受信する。また、通信部３１１は、内外判定用の多角形に対する分割部３１３１（後述）による分割処理によって生成された分割後多角形情報Ｄ１３を、内外判定制御装置３に送信する。
　記憶部３１２は、頂点削減装置１０における記憶部１２と同様の機能を有する。記憶部は、多角形情報Ｄ１０及び分割後多角形情報Ｄ１３を記憶する。
　制御部３１３は、頂点削減装置１０における制御部１３と同様の機能を有する。制御部３１３は、分割部３１３１を有する。
　分割部３１３１は、内外判定処理の前処理として、多角形情報Ｄ１０を取得し、内外判定用の多角形を複数の多角形に分割する。例えば、分割部３１３１は、多角形を三角形に分割するアルゴリズム（例えば、参考文献３参照）などを用いて、分割処理を実現する。
　参考文献３：“Polygon　triangulation　inO(n　log　logn)　time　with　simple　data　structures”,［online］，［令和１年８月２３日検索］，インターネット＜ＵＲＬ：https://link.springer.com/article/10.1007%2FBF02187846＞
　分割部３１３１は、内外判定用の多角形に対する分割処理によって分割された各多角形の各頂点の座標情報である分割後多角形情報Ｄ１３を記憶部３１２に格納するとともに、通信部２１１を介して、この情報を内外判定制御装置３に出力する。
［分割処理］
　次に、分割装置３１０が実行する分割処理について具体的に説明する。図１７は、分割処理を説明する図である。図１７の（１）は、分割処理前の内外判定用の多角形Ｐ１０及び判定対象の座標Ｃ１，Ｃ２，Ｃ３を示し、図１７の（２）は、分割処理後の多角形Ｐ１３－１，Ｐ１３－２，Ｐ１３－３を示す。また、説明のために、図１７は、ＭＢＲ４０と、分割後の各多角形Ｐ１３－１，Ｐ１３－２，Ｐ１３－３をそれぞれに対応するＭＢＲ４３－１，４３－２，４３－３と、判定対象である座標Ｃ１，Ｃ２，Ｃ３も示す。
　図１７の（１）に示すように、多角形Ｐ１０に対するＭＢＲ４０は、座標Ｃ１，Ｃ２を含む略正方形である。分割装置３１０では、分割部３１３１が、多角形を三角形に分割するアルゴリズムを用いて、多角形Ｐ１０を、例えば、３個の多角形Ｐ１３－１，Ｐ１３－２，Ｐ１３－３（図１７の（２）参照）に分割する。
　この処理により、図１７の（２）に示すように、分割後の内外判定用の多角形Ｐ１３－１，Ｐ１３－２，Ｐ１３－３をそれぞれ含むＭＢＲとして、ＭＢＲ４３－１，４３－２，４３－３を設定できる。図１７の（２）に示すように、これらのＭＢＲ４３－１，４３－２，４３－３は、ＭＢＲ４０よりも領域が削減されたものとなる。そして、図１７の（２）に示すように、ＭＢＲ４０内に位置する判定対象の座標Ｃ２は、新たなＭＢＲ４３－１，４３－２，４３－３外に位置することになり、簡易判定のみで判定が終了される。
　この結果、判定装置２０による判定処理では、領域が削減されたＭＢＲ４３－１，４３－２，４３－３を用いて簡易判定を行うため、簡易判定のみで、内外判定用の多角形外であると判定される座標が増え、詳細判定の実行回数を減らすことができる。図１７の例では、詳細判定の対象となる座標は、座標Ｃ１，Ｃ２，Ｃ３のうち、座標Ｃ３のみとなる。
［判定処理の処理手順］
　次に、判定システム３０１における判定処理の処理手順について説明する。図１８は、図１５に示す判定システム３０１による判定処理の処理手順を説明するシーケンス図である。
　図１８に示すステップＳ５１は、図７に示すステップＳ１と同じ処理である。内外判定制御装置３は、判定依頼を受けると、多角形情報Ｄ１０を、分割装置３１０に送信し（ステップＳ５２）、前処理を実行させる。
　分割装置３１０は、前処理として、内外判定制御装置３から受信した多角形情報Ｄ１０を基に、内外判定用の多角形を複数の多角形に分割する分割処理を実行し（ステップＳ５３）、分割後多角形情報Ｄ１３を内外判定制御装置３に送信する（ステップＳ５４）。
　内外判定制御装置３は、分割後多角形情報Ｄ１３及び座標情報Ｄ２０を判定装置２０に送信し（ステップＳ５５）、内外判定処理を実行させる。判定装置２０は、分割後多角形情報Ｄ１３と座標情報Ｄ２０とを基に、分割された内外判定用の多角形ごとに、判定対象の座標が、分割された内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う（ステップＳ５６）。なお、内外判定処理は、図７に示すステップＳ６と同じ処理である。また、図１７に示すステップＳ５７，Ｓ５８は、図７に示すステップＳ７，Ｓ８と同じ処理である。
［分割処理の処理手順］
　次に、分割処理（ステップＳ５３）の処理手順について説明する。図１９は、図１８に示す分割処理の処理手順を示すフローチャートである。
　図１４に示すように、回転装置２１０は、内外判定制御装置３による多角形情報Ｄ１０の入力を受け付けると（ステップＳ６１）、内外判定用の多角形を複数の多角形に分割する（ステップＳ６２）。分割装置３１０は、分割後多角形情報Ｄ１３を生成し、内外判定制御装置３に出力して（ステップＳ６３）、回転処理を終了する。
［実施の形態３の効果］
　このように、実施の形態３では、内外判定用の多角形を複数の多角形に分割する前処理を行い、分割前の多角形に対するＭＢＲと比して、全体として領域が削減された複数のＭＢＲを用いて、判定対象の各座標に対する多角形内外判定処理を行う。したがって、実施の形態３では、全体として領域が削減された複数のＭＢＲを用いて簡易判定を行うため、簡易判定のみで内外判定用の多角形外であると判定される座標が増える。これによって、実施の形態３では、詳細判定の実行回数を減らすことができ、判定処理の処理時間全体を短縮することができる。
　なお、本実施の形態３では、内外判定制御装置３は、分割装置３１０に対し、事前に内外判定用の多角形を複数の多角形に分割させて、内外判定制御装置３の記憶領域に格納し、内外判定時に読み出して、判定装置２０に送信してもよい。
［実施の形態４］
　次に、実施の形態４について説明する。実施の形態４では、実施の形態１～３で説明した前処理を順に実行することによって、内外判定処理に要する処理時間をさらに短縮する。
　図２０は、実施の形態４に係る判定システムの構成の一例を示すブロック図である。図２０に示すように実施の形態４に係る判定システム４０１は、前処理装置として、頂点削減装置１０、分割装置３１０及び回転装置２１０を有する。
　内外判定制御装置３は、例えば、最初に、頂点削減装置１０に多角形情報Ｄ１０を送信し、頂点削減装置１０による頂点削減処理を第１の前処理として実行させることにより、削減後多角形情報Ｄ１１を取得する。
　そして、内外判定制御装置３は、分割装置３１０に削減後多角形情報Ｄ１１を送信し、分割装置３１０による分割処理を第２の前処理として実行させる。これによって、内外判定制御装置３は、頂点削減後の多角形に対する分割後の頂点削減・分割後多角形情報Ｄ１３´を取得する。
　続いて、内外判定制御装置３は、回転装置２１０に頂点削減・分割後多角形情報Ｄ１３´及び座標情報Ｄ２０を送信し、回転装置２１０による回転処理を第３の前処理として実行させる。これによって、内外判定制御装置３は、頂点削減後に分割された内外判定用の各多角形に対する回転後の頂点削減・分割・回転後多角形情報Ｄ１２´と回転後座標情報Ｄ２２を取得する。
　判定装置２０は、頂点削減・分割・回転後多角形情報Ｄ１２´と回転後座標情報Ｄ２２とを基に、分割及び回転後の内外判定用の多角形ごとに、判定対象の座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う。
［判定処理の処理手順］
　次に、判定システム４０１における判定処理の処理手順について説明する。図２１は、図２０に示す判定システム４０１による判定処理の処理手順を説明するシーケンス図である。
　図２０に示すステップＳ７１～ステップＳ７４は、図７に示すステップＳ１～ステップＳ４と同じ処理である。内外判定制御装置３は、削減後多角形情報Ｄ１１を、分割装置３１０に送信し（ステップＳ７５）、前処理を実行させる。
　分割装置３１０は、前処理として、頂点削減後の多角形に対し、複数の多角形に分割する分割処理を実行し（ステップＳ７６）、頂点削減・分割後多角形情報Ｄ１３´を内外判定制御装置３に送信する（ステップＳ７７）。ステップＳ７６は、図１８に示すステップＳ５３と同じ処理である。
　そして、内外判定制御装置３は、頂点削減・分割後多角形情報Ｄ１３´及び座標情報Ｄ２０を、回転装置２１０に送信し（ステップＳ７８）、前処理を実行させる。回転装置２１０は、前処理として、内外判定制御装置３から受信した頂点削減・分割後多角形情報Ｄ１３´及び座標情報Ｄ２０を基に、内外判定用の各多角形と判定対象の座標とを回転する回転処理を実行し（ステップＳ７９）、頂点削減・分割・回転後多角形情報Ｄ１２´及び回転後座標情報Ｄ２２を内外判定制御装置３に送信する（ステップＳ８０）。ステップＳ７９は、図１３に示すステップＳ３３と同じ処理である。
　内外判定制御装置３は、頂点削減・分割・回転後多角形情報Ｄ１２´及び回転後座標情報Ｄ２２を判定装置２０に送信し（ステップＳ８１）、内外判定処理を実行させる。判定装置２０は、頂点削減・分割・回転後多角形情報Ｄ１２´と回転後座標情報Ｄ２２とを基に、分割及び回転後の内外判定用の多角形ごとに、判定対象の座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う（ステップＳ８２）。なお、内外判定処理は、図７に示すステップＳ６と同じ処理である。また、図２１に示すステップＳ８３，Ｓ８４は、図７に示すステップＳ７，Ｓ８と同じ処理である。
［実施の形態４の効果］
　このように、実施の形態４では、内外判定用の多角形に対する頂点削減処理、頂点削減後の内外判定用の多角形に対する回転処理、及び、頂点削減及び回転後の内外判定用の多角形に対する分割処理を、前処理として順次実行する。これによって、実施の形態４では、簡易判定のみで内外判定用の多角形外であると判定される座標が増えることが期待でき、実施の形態１～３と比して、内外判定処理に要する処理時間をさらに短縮することができる。
　なお、実施の形態４では、内外判定用の多角形に対する頂点削減処理、頂点削減後の内外判定用の多角形に対する回転処理、及び、頂点削減及び回転後の内外判定用の多角形に対する分割処理の順で前処理を行う場合を例に説明したが、前処理の順序に限定はない。
［実施の形態４の変形例１］
　また、実施の形態４として、前処理装置として、頂点削減装置１０、分割装置３１０及び回転装置２１０を有する例を説明したがこれに限らない。前処理装置は、頂点削減装置１０及び回転装置２１０の２つであってもよい。この場合の判定処理の処理手順について説明する。
　図２２は、実施の形態４の変形例１における判定処理の処理手順を説明するシーケンス図である。図２２に示すステップＳ９１～ステップＳ９４は、図７に示すステップＳ１～ステップＳ４と同じ処理である。内外判定制御装置３は、削減後多角形情報Ｄ１１と座標情報Ｄ２０とを、回転装置２１０に送信し（ステップＳ９５）、前処理を実行させる。
　回転装置２１０は、前処理として、内外判定制御装置３から受信した削減後多角形情報Ｄ１１と座標情報Ｄ２０とを基に、頂点削減後の内外判定用の多角形と判定対象の座標とを回転する回転処理を実行し（ステップＳ９６）、頂点削減・回転後多角形情報Ｄ１２″及び回転後座標情報Ｄ２２を内外判定制御装置３に送信する（ステップＳ９７）。ステップＳ９６は、図１３に示すステップＳ３３と同じ処理である。
　内外判定制御装置３は、頂点削減・回転後多角形情報Ｄ１２″及び回転後座標情報Ｄ２２を判定装置２０に送信し（ステップＳ９８）、内外判定処理を実行させる。判定装置２０は、頂点削減・回転後多角形情報Ｄ１２″と回転後座標情報Ｄ２２とを基に、頂点削減及び回転後の内外判定用の多角形ごとに、判定対象の座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う（ステップＳ９９）。なお、内外判定処理は、図７に示すステップＳ６と同じ処理である。また、図２１に示すステップＳ１００，Ｓ１０１は、図７に示すステップＳ７，Ｓ８と同じ処理である。
［実施の形態４の変形例２］
　また、前処理装置は、頂点削減装置１０及び分割装置３１０の２つであってもよい。この場合の判定処理の処理手順について説明する。
　図２３は、実施の形態４の変形例２における判定処理の処理手順を説明するシーケンス図である。図２３に示すステップＳ１１１～ステップＳ１１４は、図７に示すステップＳ１～ステップＳ４と同じ処理である。図２３に示すステップＳ１１５～ステップＳ１１７は、図２１に示すステップＳ７５～ステップＳ７７と同じ処理である。内外判定制御装置３は、頂点削減・分割後多角形情報Ｄ１３´と座標情報Ｄ２０とを、判定装置２０に送信し（ステップＳ１１８）、内外判定処理を実行させる。
　判定装置２０は、頂点削減・分割後多角形情報Ｄ１３´と座標情報Ｄ２０とを基に、頂点削減及び分割後の内外判定用の多角形ごとに、判定対象の座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う（ステップＳ１１９）。なお、内外判定処理は、図７に示すステップＳ６と同じ処理である。また、図２３に示すステップＳ１２０，Ｓ１２１は、図７に示すステップＳ７，Ｓ８と同じ処理である。
［実施の形態４の変形例３］
　また、前処理装置は、回転装置２１０及び分割装置３１０の２つであってもよい。この場合の判定処理の処理手順について説明する。
　図２４は、実施の形態４の変形例３における判定処理の処理手順を説明するシーケンス図である。図２４に示すステップＳ１３１～ステップＳ１３４は、図１８に示すステップＳ５１～ステップＳ５４と同じ処理である。
　そして、内外判定制御装置３は、分割後多角形情報Ｄ１３及び座標情報Ｄ２０を、回転装置２１０に送信し（ステップＳ１３５）、前処理を実行させる。回転装置２１０は、前処理として、内外判定制御装置３から受信した分割後多角形情報Ｄ１３及び座標情報Ｄ２０を基に、内外判定用の各多角形と判定対象の座標とを回転する回転処理を実行し（ステップＳ１３６）、分割・回転後多角形情報Ｄ１３″及び回転後座標情報Ｄ２２を内外判定制御装置３に送信する（ステップＳ１３７）。ステップＳ１３６は、図１３に示すステップＳ３３と同じ処理である。
　内外判定制御装置３は、分割・回転後多角形情報Ｄ１３″及び回転後座標情報Ｄ２２を判定装置２０に送信し（ステップＳ１３８）、内外判定処理を実行させる。判定装置２０は、分割・回転後多角形情報Ｄ１３″と回転後座標情報Ｄ２２とを基に、分割及び回転後の内外判定用の多角形ごとに、判定対象の座標が内外判定用の多角形の内外に存在するかを判定する内外判定処理を行う（ステップＳ１３９）。なお、内外判定処理は、図７に示すステップＳ６と同じ処理である。また、図２４に示すステップＳ１４０，Ｓ１４１は、図７に示すステップＳ７，Ｓ８と同じ処理である。
［検証］
　本実施の形態１～３における判定システムを用いた判定方法の、従来の判定方法に対する性能比較を検証した。図２５は、実験モデルを説明する図である。本検証では、図２５に示すような１つの多角形と車両４０００台とを対象とする。図２５に示す多角形は、具体的には、長辺が７０００ｍ、であり、短辺が３５ｍであり、頂点間の間隔が１ｍである道路ポリゴンである。そして、本検証は、車両が、ＭＢＲ外かつポリゴン外、ＭＢＲ内かつポリゴン外、ＭＢＲ内かつポリゴン内の３つパターンを設け、１０回試行した判定結果の平均値を採用して比較を行う。
　まず、前処理として道路ポリゴンに対する頂点削減処理を実施した後に内外判定を行った場合と、前処理を実行せずに内外判定を行った場合との比較結果について説明する。前処理として、道路ポリゴンの頂点数を１／２、１／１０、１／１００に削減した場合のＰＩＰ処理時間と、前処理を実行せずに内外判定を行った場合のＰＩＰ処理時間を測定した。
　図２６は、頂点削減処理を実施した後に内外判定を行った場合と、前処理を実行せずに内外判定を行った場合とにおけるＰＩＰ処理時間を説明する図である。図２６に示すように、前処理を実行せずに内外判定を行った場合（図２６の「基準」）と比して、頂点数を１／２、１／１０、１／１００に削減した場合、それぞれ、基準におけるＰＩＰ時間の０．５倍、０．１５倍、０．０７倍にまで処理時間を短縮することができた。
　次に、前処理として道路ポリゴンを複数の多角形に分割する分割処理を実施した後に内外判定を行った場合と、前処理を実行せずに内外判定を行った場合との比較結果について説明する。図２７は、検証において実施した分割処理を説明する図である。
　本検証では、前処理として、道路ポリゴンＰ１４（図２７の（１）参照）を道路ポリゴンＰ１４－１，Ｐ－１４－２（図２７の（２）参照）に２等分し、ＭＢＲ４４（図２７の（１）参照）を、ＭＢＲ４４よりも領域が削減されたＭＢＲ４４－１，４４－２（図２７の（２）参照）に分割した場合のＰＩＰ処理時間と、前処理を実行せずに内外判定を行った場合のＰＩＰ処理時間を測定した。
　図２８は、分割処理を実施した後に内外判定を行った場合と、前処理を実行せずに内外判定を行った場合とにおけるＰＩＰ処理時間を説明する図である。実験結果は、車両４０００台全てが分割処理によりＭＢＲ外に移動する位置にいることを想定したモデルとなっている。このように、モデルが極端であるのは、手法の改善効果がどの程度見込めるかの試算値のベースとするためである。
　分割処理を実行せずに内外判定を行った場合、ＭＢＲ内にある車両４０００台がＰＩＰ処理されるまでに要した合計時間は、７９８４ｍｓであった（図２８の「分割なし」）。これに対し、分割処理を実行して内外判定を行った場合は、ＭＢＲ内にある車両４０００台全てが「ＭＢＲ外」になったため、簡易判定のみで処理が終了する。言い換えると、分割処理によって、ＭＢＲ外となった車両に対する外積演算が省略することができる。このため、分割処理を実行して内外判定を行った場合（図２８の「分割あり」）、ＭＢＲ外の４０００台に対する内外判定処理に要した合計時間は、１．４ｍｓであった。
　この結果、分割処理を実施した後に内外判定を行った場合、分割処理時間とＰＩＰ処理時間とを合計した合計処理時間を、前処理を実行しない場合の処理時間の０．０００１８倍まで短縮することができた。
　そして、前処理として道路ポリゴンと車両を回転する回転処理を実施した後に内外判定を行った場合と、前処理を実行せずに内外判定を行った場合との比較結果について説明する。図２９は、検証において実施した回転処理を説明する図である。
　図２９に示すように、本検証では、前処理として、道路ポリゴンＰ１４（図２９の（１）参照）と車両とを４５°回転した場合（図２９の（２）参照）のＰＩＰ処理時間と、前処理を実行せずに内外判定を行った場合のＰＩＰ処理時間を測定した。図２９の（２）に示すように、４５°回転された道路ポリゴンＰ１５に応じて、ＭＢＲは、ＭＢＲ４４よりも領域が削減されたＭＢＲ４４－３となる。なお、実験結果は、車両４０００台全てが回転処理によりＭＢＲ外に移動する位置にいることを想定したモデルとなっている。このように、モデルが極端であるのは、手法の改善効果がどの程度見込めるかの試算値のベースとするためである。また、回転処理時間は、ＰＩＰ処理時間の１／１００００以下と短い時間であった。
　図３０は、回転処理を実施した後に内外判定を行った場合と、前処理を実行せずに内外判定を行った場合とにおけるＰＩＰ処理時間を説明する図である。回転処理を実行せずに内外判定を行った場合、ＭＢＲ内にある車両４０００台がＰＩＰ処理されるまでに要した合計時間は、８１２７ｍｓであった（図３０の「回転なし」）。
　これに対し、回転処理を実行して内外判定を行った場合（図３０の「回転あり」）、ＭＢＲ内にある車両４０００台全てが「ＭＢＲ外」になったため、簡易判定のみで処理終了する。言い換えると、回転処理によって、ＭＢＲ外となった車両に対する外積演算が省略することができる。このため、回転処理を実行して内外判定を行った場合（図３０の「回転あり」）、ＭＢＲ外の４０００台に対する内外判定処理に要した合計時間は、３．３ｍｓであった。
　この結果、回転処理を施した後に内外判定を行った場合、回転処理時間とＰＩＰ処理時間とを合計した合計処理時間を、前処理を実行しない場合の処理時間の０．０００４倍まで短縮することができた。
［他の適用例］
　図３１は、実施の形態１～４に係る判定システムの他の適用例を説明する図である。実施の形態１～４に係る判定システムは、海路上の船の座標判定（領域：海路）に適用が可能である。まず、海路（図３１の（１）に示す実線）を基に、海路の幅をＷｍ（Ｗは自由に設定できる。）まで広げる。そして、実施の形態１～４に係る判定システムは、道路を新たな海路に置き換え、自動車を船に置き換えて、海上の船の位置判定を行う。
　また、実施の形態１～４に係る判定システムは、座標センサをつけた魚の追跡（領域：河川）に適用が可能である。具体的には、実施の形態１～４に係る判定システムは、道路を河川に置き換え、自動車を魚に置き換え、河川上の魚の位置判定を行う。
［実施形態のシステム構成について］
　図２に示す頂点削減装置１０、図４に示す判定装置２０、図１１に示す回転装置２１０、図１６に示す分割装置３１０の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、頂点削減装置１０、判定装置２０、回転装置２１０及び分割装置３１０の機能の分散および統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
　また、頂点削減装置１０、判定装置２０、回転装置２１０及び分割装置３１０においておこなわれる各処理は、全部または任意の一部が、ＣＰＵおよびＣＰＵにより解析実行されるプログラムにて実現されてもよい。また、頂点削減装置１０においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
　また、実施の形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的に行うこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述および図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
［プログラム］
　図３２は、プログラムが実行されることにより、頂点削減装置１０、判定装置２０、回転装置２１０及び分割装置３１０が実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
　メモリ１０１０は、ＲＯＭ１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic　Input　Output　System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
　ハードディスクドライブ１０９０は、例えば、ＯＳ（Operating　System）１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、頂点削減装置１０、判定装置２０、回転装置２１０及び分割装置３１０の各処理を規定するプログラムは、コンピュータ１０００により実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、頂点削減装置１０、判定装置２０、回転装置２１０及び分割装置３１０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid　State　Drive）により代替されてもよい。
　また、上述した実施の形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
　なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local　Area　Network）、ＷＡＮ（Wide　Area　Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
　以上、本発明者によってなされた発明を適用した実施の形態について説明したが、本実施の形態による本発明の開示の一部をなす記述および図面により本発明は限定されることはない。すなわち、本実施の形態に基づいて当業者等によりなされる他の実施の形態、実施例および運用技術等はすべて本発明の範疇に含まれる。
　１，２０１，３０１，４０１　判定システム
　２　クライアント端末
　３　内外判定制御装置
　１０　頂点削減装置
　１１，２１，２１１，３１１　通信部
　１２，２２，２１２，３１２　記憶部
　１３，２３，２１３，３１３　制御部
　２０　判定装置
　１３１　頂点削減部
　２３１　内外判定部
　２１０　回転装置
　３１０　分割装置
　２１３１　回転部
　３１３１　分割部

Claims (5)

  1. 　判定対象である座標が内外判定用の多角形の内外に存在するかを判定する判定処理の前処理として、前記内外判定用の多角形の各頂点の座標情報と、前記内外判定用の多角形の各頂点の座標情報とを取得し、前記判定対象である座標と前記内外判定用の多角形とを回転する回転部と、
    　回転後の前記内外判定用の多角形の各頂点の座標情報と、回転後の判定対象である座標とを回転後座標情報として出力する出力部と、
    　を有することを特徴とする前処理装置。
  2. 　判定対象である座標が内外判定用の多角形の内外に存在するか否かを判定する判定処理を行う判定装置と、前記判定処理の前処理を行う第１の前処理装置と、を有する判定システムにおいて、
    　前記第１の前処理装置は、
    　前処理として、前記内外判定用の多角形の各頂点の座標情報と、前記内外判定用の多角形の各頂点の座標情報とを取得し、前記判定対象である座標と前記内外判定用の多角形とを回転する回転部と、
    　回転後の前記内外判定用の多角形の各頂点の座標情報と、回転後の判定対象である座標とを回転後座標情報として出力する第１の出力部と、
    　を有し、
    　前記判定装置は、
    　前記前処理後の情報を用いて、前記判定対象である座標が前記内外判定用の多角形の内外に存在するか否かを判定する
    　ことを特徴とする判定システム。
  3. 　前記判定処理の前処理を行う第２の前処理装置をさらに有し、
    　前記第２の前処理装置は、
    　前処理として、前記内外判定用の多角形の各頂点の座標情報を取得し、前記内外判定用の多角形を複数の多角形に分割する分割部と、
    　分割した内外判定用の各多角形の各頂点の座標情報を、分割後多角形情報として出力する第２の出力部と、
    　を有することを特徴とする請求項２に記載の判定システム。
  4. 　前処理装置が行う前処理方法であって、
    　判定対象である座標が内外判定用の多角形の内外に存在するかを判定する判定処理の前処理として、前記内外判定用の多角形の各頂点の座標情報と、前記内外判定用の多角形の各頂点の座標情報とを取得し、前記判定対象である座標と前記内外判定用の多角形とを回転する工程と、
    　回転後の前記内外判定用の多角形の各頂点の座標情報と、回転後の判定対象である座標とを回転後座標情報として出力する工程と、
    　を含んだことを特徴とする前処理方法。
  5. 　判定対象である座標が内外判定用の多角形の内外に存在するかを判定する判定処理の前処理として、前記内外判定用の多角形の各頂点の座標情報と、前記内外判定用の多角形の各頂点の座標情報とを取得し、前記判定対象である座標と前記内外判定用の多角形とを回転するステップと、
    　回転後の前記内外判定用の多角形の各頂点の座標情報と、回転後の判定対象である座標とを回転後座標情報として出力するステップと、
    　をコンピュータに実行させるための前処理プログラム。
PCT/JP2019/035988 2019-09-12 2019-09-12 前処理装置、判定システム、前処理方法および前処理プログラム Ceased WO2021048992A1 (ja)

Priority Applications (5)

Application Number Priority Date Filing Date Title
PCT/JP2019/035988 WO2021048992A1 (ja) 2019-09-12 2019-09-12 前処理装置、判定システム、前処理方法および前処理プログラム
EP19944858.0A EP4009280B1 (en) 2019-09-12 2019-09-12 Preprocessing device, determining system, preprocessing method, and preprocessing program
JP2021545063A JP7168099B2 (ja) 2019-09-12 2019-09-12 前処理装置、判定システム、前処理方法および前処理プログラム
US17/640,354 US11954812B2 (en) 2019-09-12 2019-09-12 Preprocessing device, determination system, preprocessing method, and preprocessing program
CN201980100208.1A CN114424248B (zh) 2019-09-12 2019-09-12 预处理装置、判定系统、预处理方法以及记录介质

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2019/035988 WO2021048992A1 (ja) 2019-09-12 2019-09-12 前処理装置、判定システム、前処理方法および前処理プログラム

Publications (1)

Publication Number Publication Date
WO2021048992A1 true WO2021048992A1 (ja) 2021-03-18

Family

ID=74866320

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2019/035988 Ceased WO2021048992A1 (ja) 2019-09-12 2019-09-12 前処理装置、判定システム、前処理方法および前処理プログラム

Country Status (5)

Country Link
US (1) US11954812B2 (ja)
EP (1) EP4009280B1 (ja)
JP (1) JP7168099B2 (ja)
CN (1) CN114424248B (ja)
WO (1) WO2021048992A1 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12602481B1 (en) 2025-04-19 2026-04-14 The Crown And The Cross Llc Neural override verification and constraint architecture for sovereign AGI execution

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP4012657B1 (en) * 2019-09-12 2023-10-25 Nippon Telegraph And Telephone Corporation Preprocessing device, determination system, preprocessing method, and preprocessing program
JP7355216B2 (ja) * 2020-03-05 2023-10-03 日本電信電話株式会社 管理装置、管理方法及び管理プログラム

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07182532A (ja) * 1993-12-22 1995-07-21 Sega Enterp Ltd 領域内外判定方法
JP2000251081A (ja) * 1999-02-26 2000-09-14 Canon Inc 内点判定方法、グラフィック描画装置およびプログラム記憶媒体
JP2003085577A (ja) * 2001-09-10 2003-03-20 Canon Inc 内外点判定アルゴリズム

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS63118982A (ja) * 1986-11-07 1988-05-23 Fujio Yamaguchi 多角形に対する点の内外判定演算処理方法
JPH1055166A (ja) * 1996-08-09 1998-02-24 Mitsubishi Electric Corp 多角形塗りつぶしアクセラレータ
US6320580B1 (en) * 1997-11-07 2001-11-20 Sega Enterprises, Ltd. Image processing apparatus
JP3829014B2 (ja) * 1998-06-03 2006-10-04 株式会社コナミデジタルエンタテインメント ビデオゲーム装置
CN100377170C (zh) * 2006-08-22 2008-03-26 北京方正奥德计算机系统有限公司 一种图像线性几何变形自动矫正的方法
US8730261B2 (en) * 2006-09-13 2014-05-20 Panasonic Corporation Image processing device, image processing integrated circuit, image processing system, input assembler device, and input assembling integrated circuit
US8374391B1 (en) * 2010-04-16 2013-02-12 The Boeing Company Model of visibility of targets
US8930245B2 (en) * 2010-06-23 2015-01-06 Justin Streich Methods, systems and machines for identifying geospatial compatibility between consumers and providers of goods or services
DE102012103011A1 (de) * 2012-04-05 2013-10-10 Krauss-Maffei Wegmann Gmbh & Co. Kg Verfahren zur synchronen Wiedergabe einer virtuellen Realität in einer verteilten Simulationsvorrichtung
CN103793145B (zh) * 2014-02-21 2016-09-07 湖南省交通规划勘察设计院 一种基于AutoCAD的图框参数识别与图纸输出方法
CN105204629B (zh) * 2015-09-02 2018-11-13 成都上生活网络科技有限公司 一种3d手势识别方法
WO2019012539A1 (en) * 2017-07-13 2019-01-17 Stratasys Ltd. METHOD OF PRINTING A 3D MODEL FROM POINT CLOUD DATA

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH07182532A (ja) * 1993-12-22 1995-07-21 Sega Enterp Ltd 領域内外判定方法
JP2000251081A (ja) * 1999-02-26 2000-09-14 Canon Inc 内点判定方法、グラフィック描画装置およびプログラム記憶媒体
JP2003085577A (ja) * 2001-09-10 2003-03-20 Canon Inc 内外点判定アルゴリズム

Non-Patent Citations (6)

* Cited by examiner, † Cited by third party
Title
BOUNDING CONTAINERS FOR POINT SETS, 23 August 2019 (2019-08-23), Retrieved from the Internet <URL:http://geomalgorithms.com/a08-_containers.html>
INCLUSION OF A POINT IN A POLYGON, 23 August 2019 (2019-08-23), Retrieved from the Internet <URL:http://geomalgorithms.com/a03-inclusion.html>
MINIMUM-AREA RECTANGLE CONTAINING A SET OF POINTS, 23 August 2019 (2019-08-23), Retrieved from the Internet <URL:https://www.geometrictools.com/Documentation/MinimumAreaRectangle>
POLYGON TRIANGULATION INO(N LOG LOGN) TIME WITH SIMPLE DATA STRUCTURES, 23 August 2019 (2019-08-23), Retrieved from the Internet <URL:https://link.springer.com/article/10.1007%2FBF02187846>
RAMER-DOUGLAS-PEUCKER ALGORITHM, 23 August 2019 (2019-08-23), Retrieved from the Internet <URL:https://siguniang.wordpress.com/2012/07/16/ramer-douglas-peucker-algorithm/>
See also references of EP4009280A4

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12602481B1 (en) 2025-04-19 2026-04-14 The Crown And The Cross Llc Neural override verification and constraint architecture for sovereign AGI execution

Also Published As

Publication number Publication date
EP4009280A4 (en) 2023-05-03
US20220327791A1 (en) 2022-10-13
US11954812B2 (en) 2024-04-09
JPWO2021048992A1 (ja) 2021-03-18
EP4009280A1 (en) 2022-06-08
CN114424248A (zh) 2022-04-29
EP4009280B1 (en) 2024-09-04
CN114424248B (zh) 2025-07-15
JP7168099B2 (ja) 2022-11-09

Similar Documents

Publication Publication Date Title
CN110458854B (zh) 一种道路边缘检测方法和装置
CN113095336B (zh) 关键点检测模型的训练方法和检测目标对象关键点的方法
US9510154B2 (en) Location determination, mapping, and data management through crowdsourcing
WO2021048992A1 (ja) 前処理装置、判定システム、前処理方法および前処理プログラム
US10510154B2 (en) Adaptive processing of spatial imaging data
US12511932B2 (en) Authentication system using object fingerprinting
US20130094397A1 (en) Method and apparatus for localized and scalable packet forwarding
CN113689270B (zh) 黑产设备的确定方法、电子设备、存储介质及程序产品
CN114170257A (zh) 一种拟合弯曲目标轮廓的、装置、计算机设备及存储介质
WO2021048987A1 (ja) 前処理装置、判定システム、前処理方法および前処理プログラム
CN111105435A (zh) 标志物匹配方法、装置及终端设备
CN109073398B (zh) 一种建立地图的方法、定位方法、装置、终端及存储介质
CN110544159B (zh) 一种地图信息处理方法、装置、可读存储介质和电子设备
WO2021048993A1 (ja) 前処理装置、判定システム、前処理方法および前処理プログラム
US9916663B2 (en) Image processing method and process simulation apparatus
CN115166754A (zh) 一种激光雷达点云的处理方法、装置、电子设备及介质
JP7067627B2 (ja) 検知装置、判定方法、及びプログラム
CN117876410A (zh) 点云数据分割方法、装置、电子设备及可读存储介质
CN113886386B (zh) 一种GeoHash确定方法、装置、设备及介质
CN117370473A (zh) 基于完整性攻击的数据处理方法、装置、设备及存储介质
CN118114076A (zh) 一种点云聚类的方法、装置、设备及存储介质
CN115957517A (zh) 游戏对象刷新方法、装置、电子设备及可读存储介质
CN114926533A (zh) 目标对象定位的地图表示方法、装置和计算机设备
JP2006277349A (ja) 近接点算出方法および装置

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 19944858

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2021545063

Country of ref document: JP

Kind code of ref document: A

ENP Entry into the national phase

Ref document number: 2019944858

Country of ref document: EP

Effective date: 20220303

NENP Non-entry into the national phase

Ref country code: DE

WWG Wipo information: grant in national office

Ref document number: 201980100208.1

Country of ref document: CN