Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!uwvax!puff!upl
From: upl@puff.WISC.EDU (Future Unix Gurus)
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited...
Message-ID: <801@puff.WISC.EDU>
Date: Tue, 16-Jun-87 17:33:58 EDT
Article-I.D.: puff.801
Posted: Tue Jun 16 17:33:58 1987
Date-Received: Sun, 21-Jun-87 07:49:30 EDT
References: <948@elrond.CalComp.COM$ <4644@utah-cs.UUCP$
Reply-To: upl@puff.WISC.EDU (Future Unix Gurus)
Organization: U of Wisconsin CS Dept
Lines: 22
Keywords: ray tracing, graphics, polygon intersection


In article <4644@utah-cs.UUCP$ shebs@utah-cs.UUCP (Stanley Shebs) writes:
$In article <948@elrond.CalComp.COM$ amamaral@elrond.CalComp.COM (Alan Amaral) writes:
$
$$To recap, the theorum put forth was that given a bounded area on a plane
$$and a point on the plane, one could determine whether the point was inside
$$the area, or outside the area by determining how many edges an arbitrary
$$ray starting at the given point crossed. (and a partridge in a pear tree...)
$$If the ray crossed an even number of edges, then the point is outside of the
$$area, and it's inside if the number of crossings is odd.
$$
$$This all works well and good, EXCEPT for one particular case. What if the
$$ray happens to cross 2 edges at exactly the same point (i.e. at a corner)?
$
A solution that I always liked for its simplicity is to double the resolution
horizontally and place your verticies on even lines and your scanned points
on odd ones, or vice versa. Note that this is directly analogous to defining
your verticies as being in the middle of a pixel location, rather than at
its boundry.

Jeff Kesselman
upl@puff (temporarily, until I accept a job offer and move!)