Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!sri-spam!sri-unix!hplabs!tektronix!uw-beaver!ubc-vision!alberta!calgary!pearce
From: pearce@calgary.UUCP
Newsgroups: sci.math
Subject: Re: point inside a polygon (triangl
Message-ID: <489@vaxb.calgary.UUCP>
Date: Sat, 1-Nov-86 14:17:17 EST
Article-I.D.: vaxb.489
Posted: Sat Nov  1 14:17:17 1986
Date-Received: Tue, 4-Nov-86 01:32:25 EST
References: <1482@jade.BERKELEY.EDU> <8900037@osiris> <5299@dartvax.UUCP> <1284@ttrdc.UUCP>
Organization: U. of Calgary, Calgary, Ab.
Lines: 27
Summary: for graphics...

In article <1284@ttrdc.UUCP>, levy@ttrdc.UUCP (Daniel R. Levy) writes:
>>>	   Count Vector on Sesame Street says: I love watching
>>>	   the ray crossing the curve and creating either an
>>>	   odd or even number of intersection points that I
>>>	   may count! Very splendid! Very splendid! HA! HA!
>>>	   HA! HA! HA! HA! HA! HA! HA! HA! HA! AH! HA! HA!
>>
>>Close, but not quite. You get a nasty exception to the rule when your
>>ray hits a vertex of the polygon. 
>
>So what?  Perturb the ray a little to get it off of the vertex and try again.
>
>(One thing about this kind of solution which seems a bit clumsy to me is
>that one needs to check every segment of the polygon to see if it does or
>does not intersect the ray.)

I use this type of check to determine if a ray has struck the inside of a
polygon - a vetex counts as .5 of an edge, and simple extent checks can
eliminate the need to intersect *every* segement, most will just need 
min/max comparisions. This is, in general, much faster than performing a
cross product with every edge, and this method works for concave polygons as
well. (or has this already been brought up?) It does take more code to handle
the many conditions though :-(

   Andrew Pearce                        [The Now Feeling]
   UUCP  : pearce@calgary.UUCP
   USENET: ...{ihnp4,ubc-vision}!alberta!calgary!pearce