Highly parallelizable algorithm for detecting intersections of shapes

A computer system for determining intersections among a plurality of two-dimensional (2D) real-world shapes, the system comprising:

• a plurality of processors;
• and
• memory including (i) computer code instructions stored thereon and (ii) data representing the two-dimensional (2D) real-world shapes, the data including segments including portions of the two-dimensional (2D) real-world shapes, the segments representing start point and end point vertices of the portions of the two-dimensional (2D) real-world shapes, the memory operatively coupled to the plurality of processors such that, when executed by the plurality of processors, the computer code instructions cause the computer system to implement a computing module configured to:
• define a plurality of reference lines, each reference line intersecting at least one of the vertices along a given axis;
• process the reference lines in parallel by classifying the vertices of the two-dimensional (2D) real-world shapes along the reference lines;
• and
• determine, based on the classifying, 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 intersect another of the two-dimensional (2D) real-world shapes.

A non-transitory computer readable medium having stored thereon a sequence of instructions which, when loaded and executed by a processor coupled to an apparatus, causes the apparatus to:

• define a plurality of reference lines, each reference line intersecting at least one of start point and end point vertices of segments representing portions of two-dimensional (2D) real-world shapes;
• process the reference lines in parallel by classifying the vertices of the two-dimensional (2D) real-world shapes along the reference lines;
• and
• determine, based on the classifying, 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 intersect another of the two-dimensional (2D) real-world shapes.