用于检测形状的交叉的可高度并行化算法

摘要

用于确定多个二维(2D)现实世界形状当中的交叉的方法和系统。通过一些实施例，形状可由数据表示并且可作为输入提供或被生成。形状(和/或数据)可以包括具有起点顶点和终点顶点的2D现实世界形状的段。定义多个参考线。每个参考线与沿给定轴线的顶点中的至少一个交叉。通过对沿参考线的二维(2D)现实世界形状的顶点进行分类，来并行地处理参考线。基于分类，确定沿参考线的二维(2D)现实世界形状中的顶点中的任意一个是否是与二维(2D)现实世界形状中的另一个交叉的现实世界形状的部分。