Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!rutgers!sri-unix!hplabs!decwrl!sun!falk
From: falk@sun.UUCP
Newsgroups: comp.graphics
Subject: Re: Line-Polygon Intersection
Message-ID: <9569@sun.uucp>
Date: Sun, 23-Nov-86 15:05:48 EST
Article-I.D.: sun.9569
Posted: Sun Nov 23 15:05:48 1986
Date-Received: Mon, 24-Nov-86 01:46:58 EST
References: <90@onion.cs.reading.ac.uk> <765@gcc-milo.ARPA>
Organization: Sun Microsystems, Inc.
Lines: 53

> > 
> >         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.
> 
> Last time I did this was for ray tracing polygons (where is Jim Kajia
> when you need him?). And the easiest way I found was to find the point
> of intersection between the line and the plane formed by three of the
> vertices (let's assume they're co-planer) . This yields a 3d point.
> Then, I translated the point and verticies into 2d (actually, I just translated
> the point as the plane was defined via a plane equation) and then performed
> the following:
> 
> 	Calculate the sum of the angles formed by two adjacent verticies
> 	and the point. i.e. draw lines from the point to two adjacent 
> 	vertices. Do this for all the sets of vertices. If the sum of the
> 	angles is != 360, you are outside of the polygon.
> 
> Does this make sense? The idea is correct, but the particulars may be off.

This is one of the classic ways to test for point-inside-polygon.  The
problem is that it requires some trigonometry for each vertex of the
polygon (inverse tangent).  That's kind of expensive.  Also, you're dealing
with real numbers and approximations, so there's going to be an error
that has to be tolerated. I.e. the sum will never be EXACTLY 360 or 0.

A faster, but harder to implement algorithm is where you project half-lines
from the point being tested to infinity (preferably along one of the
axes).  Intersect this half-line with all of the edges of the polygon
and count the intersections.  If it's odd, the point is inside the polygon.
When the half-line exactly intersects a vertex, you have a special case
because that's only supposed to count as one intersection.  The solution
to this special case is to only count vertex intersections at the "endpoint"
of the edges and not the "startpoint".

Note that you don't actually have to compute the points of intersection,
just test for their existance (method left to the student).

If the polygon is known to be convex, it becomes a much simpler problem.
For instance, take the dot-products of all of the pairs of vectors from
the test point to adjecent vertices.  These dot-products will be strictly
negative or strictly positive if the test point is inside the polygon.

> Good Sex is easier than a good slow roll. ("Left Stick! Right Rudder!...")

Yeah, but right after a slow roll, you're ready for another.

-- 
		-ed falk, sun microsystems
terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.
(The above is food for the NSA line eater.)