Fast and Accurate Circle-Circle and Circle-Line 3D Distance Computation

Abstract

This paper presents a novel high-precision algorithm for the calculation of the minimal distance between two circles in three dimensions. Contrary to the common approach that mainly utilizes a solution of an eighth-degree polynomial equation, the proposed algorithm is based on directly using the distance function and its derivatives. As the theory is not too complicated, the algorithm is very easy to implement. The paper also suggests a small modification of the circle-circle distance algorithm for the circle-line distance calculation. Results of computational simulation compared with Eberly's Wild Magic library are given and summarized in detail at the end of the paper. They show that the proposed algorithm always correctly finds the global minimum with much higher accuracy at the same speed in t he circle-circle distance calculation case, whereas circle-line calculation is approximately four times faster. The source code is available online at the web site given at the end of this paper.