“An algorithm for shading of regions on vector display devices” by Brassel and Fegeas

The display of shaded polygons by line, cross-hatch, and dot patterns on vector devices is a task frequently used in computer graphics and computer cartography. In applications such as the production of shaded maps polygon shading turns out to be critical with respect to time requirements, and the development of efficient algorithms is of importance. Given an arbitrary polygon in the plane without self-crossing edges (simply-connected polygon), the task at hand is to shade this polygon with one or two sets of parallel lines where for each set a shading angle and a line distance are given. The basic concept of this new algorithm is to decompose the polygon into a set of mutually exclusive trapezoids (in special cases triangles) where the parallel edges of the trapezoids are parallel to the desired shading lines. These trapezoids and triangles are then shaded in a fast procedure. In its present form the algorithm handles regions with up to 300 islands. Possible extensions include the construction of dash and cross patterns.

1. Baxter, R.S., Choropleth Mapping Program By Computer, Manuscript, Building Research Establishment, Garstom, Watford, U.K., 26 pgs.
2. Bouknight, W.J., 1970, “A Procedure for Generation of Three-dimensional Half-toned Computer Graphics Representations”, Communications ACM, Vol. 13, No. 9, pp. 527 – 536.
3. Brassel, K.E. and J.J. Utano, 1979, “Design Strategies for Continuous-tone Area Mapping”, The American Cartographer, Vol.6, No. 1 (forthcoming).
4. Coleman, P.R., R.C. Durfee, and R.G. Edwards, “Application of a Hierarchical Polygon Structure in Spatial Analysis and Cartographic Display”, Harvard Papers on Geographical Information Systems, Vol. 3, 20 pgs.
5. Jarvis, J.F., C.N. Judice, and W.H. Ninke, 1976, “A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays”, Computer Graphics and Image Processing, Vol. 5, pp.13-40.
6. Kern, H., 1978, “Neuere Techniken der Flaechenschraffur und der Herstellung von Farbauszuegen in der automatisierten thematischen Kartographie” (Recent Techniques of Area Shading and Color Separation in Automated Thematic Cartography), Kartographische Nachrichten, Vol. 28, No. 1, pp. 1-11.
7. Knowlton, K. and L. Harmon, 1972, “Computer-Produced Grey Scales”, Computer Graphics and Image Processing, Vol. 1, pp. 1-20.
8. Laboratory for Computer Graphics and Spatial Analysis, 1976, CALFORM User’s Manual. Cambridge: Harvard University.
9. Lieberman, H., 1978, “How to Color In A Coloring Book”, Computer Graphics, Vol. 12, No. 3, pp. 111-116.
10. Negroponte, N., 1977, “Raster Scan Approaches to Computer Graphics”, Computers and Graphics, Vol. 2, pp. 179-193.
11. Newman, W.M. and R.F. Sproull, 1973, Principles of Interactive Computer Graphics. New York: McGraw-Hill.
12. Monmonier, M.S., and D.M. Kirchoff, 1977, “Choroplethic Plotter Mapping for a Small Minicomputer”, Proceedings of the American Congress on Surveying and Mapping, 37th Annual Meeting, Wash., D.C., pp. 318-338.
13. Pavlidis, Th., 1978, “Filling Algorithms for Raster Graphics”, Computer Graphics, Vol. 12, No. 3, pp. 161-164.
14. Rase, W.D., SRAFOF shading subroutine, private communication.
15. Rase, W.D., 1978, “Computer-assisted Thematic Mapping for Federal Planning”, Nachrichten aus dem Karten- und Vermessungswesen, Series II: Translations, No. 35, pp. 77-83.
16. Rosenfeld, A. and V.C. Kak, 1976, Digital Image Processing. New York/London: Academic Press.
17. Salomon, K.B., 1978, “An Efficient Point-in-Polygon Algorithm”, Computers and Geosciences, Vol. 4, pp.173-178.
18. Shamos, M.I., 1977, Computational Geometry. Berlin/New York: Springer-Verlag.
19. Southerland, I.E., R.F. Sproull and R.A. Schumacker, 1974, “A Characterization of Ten Hidden-Surface Algorithms”, Computing Surveys, Vol. 6, No. 1, pp. 1-55.
20. Tobler, W.R., 1971, Choropleth Mapping Programs. Cartographic Laboratory Report No.6, Dept. of Geography, Univ. of Michigan, Ann Arbor.
21. Tobler, W.R., 1973, “Choropleth Maps without Class Intervals?”, Geographical Analysis, Vol. 5, pp. 262-265.
22. U.S. Geological Survey, Geography Program: Routine SHADT, personal communication.
23. Watkins, G.S., 1970, A Real-Time Visible Surface Algorithm, Computer Science Department, University of Utah, UTECH-CSc-70-101.
24. Waugh, T.C., and D.R.F. Taylor, 1976, “GIMMS / An Example of an Operational System for Computer Cartography”, The Canadian Cartographer, Vol. 13, No. 2, pp. 158-166.
25. Wood, P.M., and D.M. Austin, 1975, “CARTE: A Thematic Mapping Program”, Computers and Graphics, Vol. 1, No. 2/3, pp. 239-250.
26. Wood, P.M., 1978, “Interactive Display of Polygonal Data”, Harvard Papers on Geographic Information Systems, Vol. , 20 pgs.