HIGHLY PARALLELIZABLE ALGORITHM FOR DETECTING INTERSECTION OF SHAPE

摘要

PROBLEM TO BE SOLVED: To provide a method and a system for determining intersection between a plurality of two-dimentional (2D) real-world shapes.;SOLUTION: Shapes may be represented by data and may be provided as input or be generated by some embodiments. The shapes (and/or data) may include segments of the 2D real-world shapes having start point and end point vertices. A plurality of reference lines are defined. Each reference line intersects at least one of the vertices along a given axis. The reference lines are processed in parallel by classifying the vertices of the two-dimensional (2D) real-world shapes along the reference lines. Based on the classification, it is determined whether any of the vertices of the two-dimensional (2D) real-world shapes along the reference lines are part of a real-world shape that intersects another of the two-dimensional (2D) real-world shapes.;SELECTED DRAWING: Figure 1;COPYRIGHT: (C)2019,JPO&INPIT