webber@athos.rutgers.edu (Bob Webber) (02/28/88)
I see comp.graphics is getting a resurrection of last summer's discussion
of the point-in-polygon problem. This problem is quite difficult. Ultimately,
the difficulty rests in problems in translating between continuous and
discrete models of geometries.
The best reference seems to still be:
A. R. Forrest's ``Computational Geometry in Practice''
which appeared in: Fundamental Algorithms for Computer Graphics
Rae A. Earnshaw (editor)
Springer-Verlag, New York, 1985. pages 707-724.
[which is the Proceedings of the NATO Advanced
Study Institute on Fundamental Algorithms for
Computer Graphics held at Ilkley, Yorkshire,
England, March 30 - April 12, 1985.]
I strongly urge you to read the original. The conclusion was:
Simply by examining an apparently trivial operation which must have
been implemented thousands of times in practice, we have shown that
such operations are by no means trivial. It is doubtful indeed
whether any completely sucessful implementations exist or indeed
can ever exist. We tend to take for granted in many algorithms
the ability to implement these primitives successfully and we must
realise that we do so at our peril. Implementation requires careful
attention to the various geometric cases which must be correctly
identified, and to all the arithmetic operations involved. The
precision to which these operations must be carried out is considerably
higher than many realise.
The article is quite readable and convincing. Similar themes were explored
in the Siggraph'87 Panel ``Pretty Pictures Aren't So Pretty Anymore: A Call
for Better Theoretical Foundations'' chaired by Rae Earnshaw with panelists
Jack E. Bresenham, Dvaid P. Dobkin, A. Robin Forrest, and Leo J. Guibas
(briefly described on page 345 of the SIGGRAPH'87 Conference Proceedings
[distributed by the ACM]). Of related interest is: Wm. Randolph Franklin's
``Problems with raster graphics algorithms'' (Data Structures for Raster
Graphics, L. R. A. Kessener, F. J. Peters, and M. L. P. van Lierop (eds.),
Springer-Verlag, 1986. pages 1-7.). Somewhere in the back issues of the
JACM is an article on limit properties of line digitization criteria that
addresses many of the fundamental problems of trying to connect talk about
straight lines with talk about pixels (it was on my desk just a minute ago,
now it is probably lost forever...
--- BOB (webber@athos.rutgers.edu ; rutgers!athos.rutgers.edu!webber)