Improved algorithms for determining the injectivity of 2D and 3D rational Bézier curves

Abstract

Bézier curves and surfaces are important to computer-aided design applications. This paper presents algorithms for checking the injectivity of 2D and 3D Bézier curves. An injective Bézier curve or surface is one that has no self-intersections. The proposed algorithms use recently proposed sufficient and necessary conditions under which Bézier curves are guaranteed to be non-self-intersecting. As well as a rigorous derivation of the proposed algorithms, we present a series of examples and derive the complexity and computation times of the proposed algorithms. We find that the complexity our algorithms is approximately O(m), representing an improvement over previous injectivity-checking algorithms.

Keywords

• injectivity
• bézier curve
• monotone chain
• algorithm analysis