Abstract:
Aiming at the problems of high combinatorial computation time consumption and initial value sensitivity in traditional subdivision methods for shortest distance calculation between NURBS curves, this paper proposes an efficient algorithm based on competitive flow matching and quasi-polygon control point mapping. Firstly, hierarchical subdivision is used to split NURBS curves into Bézier curve segments, construct quasi-polygons tightly wrapping curves and calculate error upper bounds for rapid invalid region pruning. And then, a competitive flow traversal strategy is introduced, significantly reducing the time complexity of distance calculation; that is, linear time complexity is achievable when the number of local nearest point pairs is fixed. Finally, high-precision initial values are obtained via proportional mapping from quasi-polygon control points to curves, and Newton’s iteration method achieves the global closest distance. Compared with prevailing methods, this approach consistently outperforms in computation time for complex curves while maintaining the given precision and robustness.