Computing the minimum distance between two Bézier curves

Xiao-Diao Chen (1) , Linqiang Chen (2) , Yigang Wang (2) , Gang Xu (2) , Jun-Hai Yong (1, 3) , Jean-Claude Paul (3, 1)

1 THSS - School of Software
2 HDU - Hangzhou Dianzi University
3 CAD - Computer Aided Design

A sweeping sphere clipping method is presented for computing the minimum distance between two Bézier curves. The sweeping sphere is constructed by rolling a sphere with its center point along a curve. The initial radius of the sweeping sphere can be set as the minimum distance between an end point and the other curve. The nearest point on a curve must be contained in the sweeping sphere along the other curve, and all of the parts outside the sweeping sphere can be eliminated. A simple sufficient condition when the nearest point is one of the two end points of a curve is provided, which turns the curve/curve case into a point/curve case and leads to higher efficiency. Examples are shown to illustrate efficiency and robustness of the new method.

Domaines: Géométrie algorithmique [cs.CG]

Xiao-Diao Chen, Linqiang Chen, Yigang Wang, Gang Xu, Jun-Hai Yong, et al.. Computing the minimum distance between two Bézier curves. Journal of Computational and Applied Mathematics, 2009, 229 (1), pp.194-301. ⟨10.1016/j.cam.2008.10.050⟩. ⟨inria-00518351⟩