Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!sri-spam!ames!ptsfa!ihnp4!alberta!obed!stephen
From: stephen@obed.UUCP
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited... (It's easy)
Message-ID: <402@pembina.UUCP>
Date: Mon, 29-Jun-87 22:23:13 EDT
Article-I.D.: pembina.402
Posted: Mon Jun 29 22:23:13 1987
Date-Received: Fri, 3-Jul-87 06:49:46 EDT
References: <948@elrond.CalComp.COM> <260@brandx.rutgers.edu> <1365@xanth.UUCP> <3731@spool.WISC.EDU>
Organization: U. of Alberta, Edmonton, AB
Lines: 31
Keywords: ray tracing, graphics, polygon intersection
Summary: I don't think there are special cases that actually cause problems.

In article <3731@spool.WISC.EDU>, planting@colby.WISC.EDU ( W. Harry Plantinga) writes:

 : 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.

You are ASSUMING problems here: for example: There is little problem with
roundoff error if the 'arbitrary line' is parallel to the X axis. All that
needs to be checked in that case is the 'y' values of the endpoints.
An intersecting line with both Y values the same is parallel. a non-zero
difference means it is non-parallel. Any roundoff error will be offset
in succeeding line segments. This assumes, of course, that the endpoints
of two ajacent lines are at exactly the same point (ignoring non-closure).

If you feel that I am wrong here, please send me an actual counter-example.

	Stephen Samuel
	{seismo!mnetor,ihnp4,vax135,ubc-vision}!alberta!obed!stephen