“Shading of regions on vector display devises” by Lee

  • ©D. T. Lee




    Shading of regions on vector display devises



    Given an arbitrary simple polygon with N vertices we present an algorithm for shading the interior of the polygon with a set of parallel lines where the slope and the distance between lines are prespecified. If the number of shading line segments is M, the algorithm described in the paper runs in 0(N log N + M) time. The algorithm is generalizable to shade any region or regions of an arbitrary planar subdivision.


    1. Brassel, K. E. and Fegeas, R., “An Algorithm for Shading of Regions on Vector Display Devices,” Computer Graphics, Vol. 13, No. 2, Aug. 1979, pp. 126-133.
    2. Lee, D. T. and Preparata, F. P., “Location of a Point in a Planar Subdivision and Its Applications,” Siam J.Comput., Vol 6, No. 3, Sept. 1977, pp. 594-606.
    3. Shamos, M. I., Computational Geometry, Springer-Verlag, Berlin/New York, 1977.
    4. Knuth, D. E., The Art of Computer Programming, Second Edition, Vol. 1, Addison-Wesley, Reading, Mass., 1973.
    5. Newman, W. M. and Sproull, R. F., Principles of Interactive Computer Graphics, Second Edition, McGraw-Hill, 1979.
    6. Watkins, G. S., “A Real-Time Visible Surface Algorithm”, Univ. Utah Comput. Sci. Dept., UTEC-CSc-70-101, June 1970.

ACM Digital Library Publication: