Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!husc6!uwvax!colby!planting
From: planting@colby.WISC.EDU ( W. Harry Plantinga)
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited... (It's easy)
Message-ID: <3731@spool.WISC.EDU>
Date: Mon, 22-Jun-87 23:25:39 EDT
Article-I.D.: spool.3731
Posted: Mon Jun 22 23:25:39 1987
Date-Received: Wed, 24-Jun-87 02:53:00 EDT
References: <948@elrond.CalComp.COM> <260@brandx.rutgers.edu> <1365@xanth.UUCP>
Sender: news@spool.WISC.EDU
Reply-To: planting@colby.WISC.EDU ( W. Harry Plantinga)
Organization: U of Wisconsin CS Dept
Lines: 66
Keywords: ray tracing, graphics, polygon intersection
Summary: Is it really?

Concerning the point-in-polygon problem the following appeared:
>]
>]A rather interesting article was written on the problem of this
>]method:
>]      A. R. Forrest, ``Computational geometry in practice,'' appeared in:
>]      R. A. Earnshaw (ed.), Fundamental Algorithms for Computer
>]      Graphics, NATO ASI Seires Vol. F17, Springer-Verlag, 1985, 707-724.
>]    
>]Said author's conclusions were:
>]
>]      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 various geometric cass which must
>]      be correctly identified and to all arithmetic operations involved.
>]      The precision to which these operations must be carried out is 
>]      considerably higher than many realise.
>]

To which Kent Dolan (kent@xanth.UUCP) replied:

>Oh, come on:  "Anything I don't know how to do must be extremely difficult, and
>probably requires magic to accomplish?  And besides that, it probably isn't
>even possible, so why bother to try?"  Really!
>
>The problem is trivial, and so is the solution . . .; 
>it took five minutes thought after I saw that the problem existed, and there
>are probably thousands (well, dozens) of other people who did it right, too,
>thought nothing about it, and went on about their jobs.
>

To which I say:

On the contrary, the problem is not trivial to solve for every
possible case.  Your solution, for example, will very likely fail for
some instances of the problem.  One problem that Forrest was speaking
of is the large number of special cases in geometrical problems.
These you may have solved correctly (but your solution shows that
Forrest is right, there are lots of special cases).  

The other problem that Forrest mentions is that of the precision to
which the arithmetic is carried out, even assuming the locations of
the points are known exactly.  You didn't mention taking any special
precautions to avoid problems arising from numerical imprecision in 
determining whether line segments intersect, whether points are equal, 
etc.  If you didn't, then your algorithm will fail in certain bad 
cases, for example, for lines that are very nearly parallel.  In that 
case, numerical problems will cause your algorithm to judge some line 
segments to intersect when in fact they don't, or some line segments 
not to intersect when they do.  In that case your algorithm will not 
correctly determine whether the point is in the polygon.  

Forrest is right that "we tend to take for granted in many algorithms
the ability to implement . . . primitives successfully."  The wisdom
of recognizing false assumptions here is made the more pungent by the
vehemence with which others believe them to be true.

Harry Plantinga
University of Wisconsin CS Department
planting@cs.wisc.edu
{allegra,ihnp4,heurikon,seismo}!speedy!planting
(608) 233-1386