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

David Vranek
Technical University of Brno

This paper appears in issue Volume 7, Number 1.
Purchase this issue from the akpeters.com web site.

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 the 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 the paper.

Author Information

David Vranek, Technical University of Brno, Faculty of Civil Engineering, Veveri 95662 37 Brno, Czech Republic vranek@hotmail.com

Source Code

C++ source code for the circle-circle and circle-line calculations, along with the test programs whose results are described in the paper, are contained in this downloadable archive: ccdist.zip (50K)

Appendix

This appendix derives the point-circle distance formula that is used in the circle-circle distance calculation: Appendix.doc (65K MS Word document).

BibTeX Entry

@article{Vranek02,
  author = "David Vranek",
  title = "Fast and Accurate Circle-Circle and Circle-Line 3D Distance Computation",
  journal = "journal of graphics, gpu, and game tools",
  volume = "7",
  number = "1",
  pages = "23-32",
  year = "2002",
}