TOPOLOGICALLY RELIABLE APPROXIMATION OF COMPOSITE BEZIER CURVES

We present an efficient method of approximating a set of mutually noni ntersecting simple composite planar and space Bezier curves within a p rescribed tolerance using piecewise linear segments and ensuring the e xistence of a homeomorphism between the piecewise linear approximating segments and the actual nonlinear curves. Equations and a robust solu tion method relying on the interval projected polyhedron algorithm to determine significant points of planar and space curves are described. Preliminary approximation is obtained by computing those significant points on the input curves. This preliminary approximation, providing the most significant geometric information of input curves, is especia lly valuable when a coarse approximation of good quality is required s uch as in finite element meshing applications, The main approximation, which ensures that the approximation error is within a user specified tolerance, is next performed using adaptive subdivision. A convex hul l method is effectively employed to compute the approximation error. W e prove the existence of a homeomorphism between a set of mutually non -intersecting simple composite curves and the corresponding heap of li near approximating segments which do not have inappropriate intersecti ons. For each pair of linear approximating segments, an intersection c heck is performed to identify possible inappropriate intersections. If these inappropriate intersections exist, further local refinement of the approximation is performed, A bucketing technique is used to ident ify the inappropriate intersections, which runs in O(n) time on the av erage where n is the number of linear approximating segments, Our appr oximation scheme is also applied to interval composite Bezier curves.