Algorithm 671: FARB-E-2D: fill area with bicubics on rectangles—a contour plot program

ABSTRACT

An algorithm plotting contour lines for discrete values zij, given at the nodes of a rectangular mesh is described. A bicubic Hermite polynomial f(x, y) is determined for every rectangle of the mesh, interpolating the zij and the derivatives zx, zy, and zxy. The derivatives are optionally computed by the algorithm. The contours found are normally smooth curves. They consist of polygons approximating intersections with the bicubics. It is possible to fill the areas between them with certain colors or patterns. This is done with a piecewise technique rectangle by rectangle. The method for finding the points of the polygons is shortly reviewed, and some numerical problems are pointed out. The algorithm has a flexible, easy-to-use interface and is easily installed with all plotting systems, provided that a fill-area command is available. A GKS interface may be used.

REFERENCES

• 1: Hiroshi Akima, A New Method of Interpolation and Smooth Curve Fitting Based on Local Procedures, Journal of the ACM (JACM), v.17 n.4, p.589-602, Oct. 1970 [doi>10.1145/321607.321609]
• 2: Hiroshi Akima, A method of bivariate interpolation and smooth surface fitting based on local procedures, Communications of the ACM, v.17 n.1, p.18-20, Jan. 1974 [doi>10.1145/360767.360779]
• 3: AKIMA, H. Algorithm 474: Bivariate interpolation and smooth surface fitting based on local procedures. Coll. Alg. from CACM, (474-P 1-0 to 474-P 7-0).
• 4: David F. McAllister , John A. Roulier, An Algorithm for Computing a Shape-Preserving Osculatory Quadratic Spline, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.331-347, Sept. 1981 [doi>10.1145/355958.355964]
• 5: Dennis S. Arnon, Topologically reliable display of algebraic curves, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.219-227, July 1983
• 6: BECHLARS, J., AND BUHTZ, R. GKS in der Praxis, Springer-Verlag, New York, 1986.
• 7: BRUNET, P. Increasing the smoothness of bicubic spline surfaces. Comput. Aided Geom. Des. 2 (Sept. 1985), 157-164.
• 8: T A Foley, Scattered data interpolation and approximation with error bounds, Computer Aided Geometric Design, v.3 n.3, p.163-177, Nov. 1986 [doi>10.1016/0167-8396(86)90034-8]
• 9: FRITSCH, F. i., AND CARLSON, R.n. Monotonicity preserving bicubic interpolation: A progress report. Comput. Aided Geom. Des. 2, 2 (Sept. 1985), 117-121.
• 10: F. R.A. Hopgood , D. A. Duce , J. R. Gallop , D. C. Sutcliffe, Introduction to the Graphical Kernel System (GKS) (2nd ed. revised for international standard), Academic Press Ltd., London, UK, 1986
• 11: Albrecht Preusser, Algorithm 626 TRICP: a contour plot program triangular meshes, ACM Transactions on Mathematical Software (TOMS), v.10 n.4, p.473-475, Dec. 1984 [doi>10.1145/2701.2772]
• 12: Albrecht Preusser, Computing area filling contours for surfaces defined by piecewise polynomials, Computer Aided Geometric Design, v.3 n.4, p.267-279, 1987 [doi>10.1016/0167-8396(86)90003-8]
• 13: SAraN, M. A. Contouring--the state of the art. In Fundamental Algorithms for Computer Graphics, R. A. Earnshaw, Ed., NATO ASI Series, Springer-Verlag, New York, 1985.
• 14: William V. Snyder, Algorithm 531: Contour Plotting [J6], ACM Transactions on Mathematical Software (TOMS), v.4 n.3, p.290-294, Sept. 1978 [doi>10.1145/355791.355800]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design