Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!sri-spam!ames!ucbcad!ucbvax!decvax!tektronix!uw-beaver!cornell!batcomputer!garry
From: garry@batcomputer.tn.cornell.edu (Garry Wiegand)
Newsgroups: comp.graphics
Subject: Re: Line-Polygon Intersection
Message-ID: <1547@batcomputer.tn.cornell.edu>
Date: Wed, 19-Nov-86 22:49:37 EST
Article-I.D.: batcompu.1547
Posted: Wed Nov 19 22:49:37 1986
Date-Received: Thu, 20-Nov-86 22:46:05 EST
Reply-To: garry%cadif-oak@cu-arpa.cs.cornell.edu
Organization: Cornell Engineering && Flying Moose Graphics
Lines: 50

In a recent article scm@onion.cs.reading.Ac.Uk (Stephen Marsh) wrote:
>...     What I need is NOT the line-plane intersection point,
>but an algorithm which tests to see if the intersection point
>is contained within the 3D polygon.

The simple minded approach is to project it down into a convenient
2-D plane and apply the usual point-in-polygon algorithms. For
example, given the 3-D intersection point and polygon, and given
(for this example) that the polygon is not perpendicular to the
XY plane, project it down into that plane. Do this by ignoring
the Z-values! 

Once there, start anywhere on the polygon and walk around. At each 
step, test to see if the edge passes above-to-below or below-to-above
with respect to the test point. (Note: For purposes of "passing", the 
start vertex of the edge does NOT count, and the end vertex DOES count.) 

If it *does* pass, figure whether it passes to the left or right of the 
test point: If the test edge is horizontal and includes the test point, 
declare it "in" and exit. If the edge is horizontal and doesn't include the
test point, forget it. If it's not horizontal, see if the edge is completely
left or right of the test point. If it's not completely left or right, then
compute the intersection with the horizontal and see whether *that* is 
left or right. If the intersection is right on top, declare the point "in" 
and exit.

Remember how many times you pass to the left, say. If this ends up odd, 
the point's in. Otherwise it's out. 

In the normal "in" case you'll need to compute maybe *one* edge/axis 
intersection.

Whew. (We need a picture.)

You can improve the computation with bounding boxes and other such
tricks. If you know the polygon's convex, you of course won't need
a counter, and you'll only need to look at at most (n+1)/2 edges 
(often far fewer) (exercise left for the reader.)

(If you're working in floating-point, be careful about tests-for-
equality!)

(If the original polygon WAS perpendicular to the XY plane, project into
the YZ plane, say, and apply a tweaked version of the above algorithm.)

I trust I've been complete. Wonder if it's right - I've never gotten 
around to reading about this subject (who said computer graphics 
wasn't ffun ? :-)

garry wiegand   (garry%cadif-oak@cu-arpa.cs.cornell.edu)