Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!sdd.hp.com!zaphod.mps.ohio-state.edu!wuarchive!mit-eddie!bloom-beacon!eru!hagbard!sunic!liuida!isy!lysator.liu.se!zap
From: zap@lysator.liu.se (H}kan Andersson)
Newsgroups: comp.graphics
Subject: Re: Point in Polygon; a few more comments
Message-ID: <233@lysator.liu.se>
Date: 7 Sep 90 07:16:12 GMT
References: <1990Sep06.124709.996@eye.com>
Sender: news@isy.liu.se (Lord of the News)
Organization: Lysator Computer Club, Linkoping University, Sweden
Lines: 82

erich@eye.com (	Eric Haines) writes:

>(Here's my big chance to test out our own real live news feed!  Maybe it'll
>work this time...)

>Mark VandeWettering writes about the point in polygon test:
>>[... much talk of the shoot a ray to the right & count crossings method ...]
>>Hardly my own idea.  It was shown to me by Eric Haines originally, but I 
>>don't think he claims credit for it either.  Any takers?  Is it patented 
>>by Unisys as well :-)?

>	Anyway, having an ego and all that, I do indeed claim to be the
>inventor of the "consider all points on the line to be above the line"


>	Historical note:  the earliest reference I have to the point in
>polygon test is the classic "A Characterization of Ten Hidden-Surface
>Algorithms" by Ivan Sutherland et al, 1974, ACM Computing Surveys v6 n1.  This
>has both the ray crossing test and the sum of the angles test, plus the convex
>polygon test (check if the point is inside all lines by substitution into each
>edge's 2D line equation).

>	Computational geometry fiends noted that the method has the problem of
>being indeterminate on edges:  if your intersection point is exactly on an
>edge, it's arbitrary whether the point is determined to be inside or outside
>the polygon (that is, do you consider an edge crossing the point to be to the
>right or left of the point, or do you want a third category, such as "on"?).

>	However, there is a general consistency to the ray crossing test for
>ray tracing.  If the point being tested is along the edge joining two visible
>polygons (which both face the same general direction, i.e. not a silhouette
>edge) and the polygons are projected consistently upon the plane perpendicular
>to the ray, the point is guaranteed to be considered to be inside one and only
>one of the polygons.  That is, no point will be considered within any two
>non-overlapping polygons, nor will it "fall in the crack" between polygons.

>	Think about it this way:  if points on the left edges of the polygon
>are considered outside, then the points on the right edges will be considered
>inside.  This is because we would then consider an edge crossing the x axis at
>exactly 0 as being to the right of the test point.  Since one polygon's left
>edge is another's right edge, it all balances out to make each point be inside
>only one polygon in a polygon mesh.  Horizontal edges are treated the same
>way:  if a point is actually on such an edge, when tested, the point will be
>categorized as "below" the edge consistently.  This will lead it to be inside
>one and only one polygon in a mesh.

>	In reality, when ray tracing you very rarely get points that are
>exactly on an edge, so this is something of a non-problem.  But if you really
>really care about this possibility, make sure to always cast your polygons
>onto the plane perpendicular to the ray (this plane is also good for
>consistency if you want to get edges for Gouraud RGB interpolation, Phong
>normal interpolation, etc).

/* Eric blatheres on.... */

>Eric Haines
>erich@eye.com

>P.S.  As our patent on the 90 degree angle was successful, the pending patent
>on the Jordan Curve Theorem should come through any day now... ;-)


As I Think I Posted earlier, this is somewhat similar to my own approach in
getting rid of special cases: Assume we are testing for a ray along X axis...
For all line segments, swap 'em, so it's "first" point is upwards (Have a lower
Y coordinate). Then, for each segment, test if the point's Y > firstY. If not,
discard (This, in essence, is a version of Eric's idea, only mine :-) then,
check if Y <= lastY. If not, discard. IMPORTANT ISSUE HERE is that I actually
CARE about the 'second' point of the line, and include it in the check, thats
MY way of getting rid of problem of a corner pointing downwards: It will yield
2 intersections, Eric's method yields none. No big Deal, really.... after
this simple boundstest, it's time for the dreary math on checking if the
intersection is on POSITIVE X, i.e. if X > firstX && X > lastX, discard, and
last but not least, check the real intersection with som math (Left as an exer-
cise for the reader :-).

OBTW, fr'gor! FIRST, you check if (LastY - Y) * (FirstY - Y) is > 0. If so,
discard.

All for now.

"Zap" Andersson