Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utcs!poslfit
From: poslfit@utcs.UUCP
Newsgroups: comp.graphics
Subject: Re: Line-Polygon Intersection
Message-ID: <1986Nov20.014128.19427@utcs.uucp>
Date: Thu, 20-Nov-86 01:41:28 EST
Article-I.D.: utcs.1986Nov20.014128.19427
Posted: Thu Nov 20 01:41:28 1986
Date-Received: Thu, 20-Nov-86 02:41:53 EST
References: <90@onion.cs.reading.ac.uk>
Reply-To: poslfit@utcs.UUCP (John J. Chew, III)
Organization: The Poslfit Committee
Lines: 27
Checksum: 37514
Summary:  It's a 2-D problem

In article <90@onion.cs.reading.ac.uk> scm@onion.cs.reading.Ac.Uk (Stephen Marsh) writes:
> 
>         Can anyone help me with some 3D geometry? I am looking
> for an algorithm which will enable me to test if a line in a
> three-coordinate system with equation r=a+lambda*b intersects
> a polygon with vertices v1,v2,....,vn (n>=3,v = (x,y,z)) which
> lies in the plane n.r/|n| = p.
>         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.

As far as I can tell, this is a 2-D problem.

Unless the polygon is perpendicular to the x-y plane (i.e. its normal is //z)
project it and the line-polygon intersection point into said plane by dropping
z co-ordinates.  Then treat it as a two-dimensional problem.  Remember that if
the line and polygon are generally independently chosen and the polygon is
nice and convex, you'd probably save comparisons by testing non-consecutive
polygon edges (n-s-e-w rather than n-e-s-w order).  Of course, if the polygon
is _|_ to x-y, just project it onto the x-z or y-z plane.
--
from the serial port of john j. chew (v3.0) a/k/a poslfit@utcs.UUCP
just another ninja toad dicing with death and looking for that Talisman
-- 
*** THIS LINE HAS BEEN REPLACED BY...
from the serial port of john j. chew (v3.0) a/k/a poslfit@utcs.UUCP
just another ninja toad dicing with death and looking for that Talisman