The Development of Programs for the Processing of Parametric Curves

Abstract

This paper presents the development of a suite of programs for the processing of parametrically defined curves in two and three dimensions. The programs are presented in Dijkstra-s non-deterministic guarded command notation. The development of the proof of correctness for the programs is also described. Three typical curve processing tasks, such as drawing, curve path following and intersection detection, are described.The algorithms used in these programs are all based on the "divide and conquer (subdivision)" paradigm. Deviation from linearity and Euclidean bounds are two curve shape properties that are used in many of the curve processing tasks. We present fast methods of computing these properties from the algebraic representation of the curve. In particular the paper considers the cubic and the rational quadratic forms of representation.