An Algorithm to Compute the Distance of 2D Line Segments based on Local Coordinate System

The calculation of distances between basic geometric elements is a key algorithm in CAD geometry engines, which are widely applied in CAD software, including ship design and VLSI design. As the underlying high-frequency algorithm, the speed of distance calculation significantly affects the efficiency of the upper CAD software. In particular, distance calculation of planar line segments plays a very important role in VLSI design, Boolean operation and sketch design. In this paper, we propose a method for calculating the distance between two line segments based on the local coordinate system, and classify the distance calculation into 12 cases based on the end position of the two line segments. By calculating the position of the nearest point of two line segments, the distance calculation between two planar line segments is converted into the distance calculation between two nearest points. At the end of the paper, the efficiency of this algorithm is compared with the existing algorithms, and the efficiency of distance calculation between two line segments is improved by 23%-35% compared with the most efficient existing algorithm.