Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rochester!cornell!batcomputer!garry
From: garry@batcomputer.tn.cornell.edu (Garry Wiegand)
Newsgroups: comp.graphics
Subject: Re: Line-Polygon Intersection
Message-ID: <1573@batcomputer.tn.cornell.edu>
Date: Sun, 23-Nov-86 23:32:55 EST
Article-I.D.: batcompu.1573
Posted: Sun Nov 23 23:32:55 1986
Date-Received: Mon, 24-Nov-86 21:56:00 EST
Reply-To: garry%cadif-oak@cu-arpa.cs.cornell.edu
Organization: Cornell Engineering && Flying Moose Graphics
Lines: 33

In a recent article falk@sun.uucp (Ed Falk) wrote:
>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...
>...
>Note that you don't actually have to compute the points of intersection,
>just test for their existance (method left to the student).

Yes, I think you do have to compute the intersection in one special
case - the case where you *know* the full-line intersects but the half-
line begins somewhere within the edge in question. See the method I posted 
a few days ago for the glitch point. (Or am I not seeing something?)

>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.

Yes, this is simpler, but it involves more computation than the half-line
method. Specifically, the half-line method requires two or three comparisons
per point, and only looking at half the points (average convex case), while the
dot-products require 4 subtracts and 2 multiplies per point, and looking
at *every* point. Also, if you're working in floating-point you still have
to worry about roundoff errors, and if you're in integers you probably have 
to use long ints to avoid overflows.

Anyhow, I've noticed since my first posting that if the points are stored
in an array rather than a list, and if there are enough of them to make
more computation per step worthwhile, then the convex case can be reduced 
from O(n) to O(log n)!   (Do a binary search.)

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