Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!ut-sally!utah-cs!shebs
From: shebs@utah-cs.UUCP (Stanley Shebs)
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited...
Message-ID: <4649@utah-cs.UUCP>
Date: Wed, 17-Jun-87 11:20:09 EDT
Article-I.D.: utah-cs.4649
Posted: Wed Jun 17 11:20:09 1987
Date-Received: Sun, 21-Jun-87 09:37:59 EDT
References: <948@elrond.CalComp.COM> <790@thumper.UUCP>
Reply-To: shebs@utah-cs.UUCP (Stanley Shebs)
Organization: PASS Research Group
Lines: 28
Keywords: ray tracing, graphics, polygon intersection

In article <790@thumper.UUCP> sdh@thumper.UUCP writes:

>[...]
>The most effective way to do this is to make sure that every point on the
>polygonis not on the ray.  The problem with this is that you have to check
>every point.  Too slow.

Huh?  You have to check intersections with every edge anyway, looking at the
endpoints specifically comes almost for free.

>[...] use a vector that is defined by the given point and the midpoint
>of a particular edge.  The only reasone for this is that it will be fast,
>and only less fallable in the sense that you know it will definitely cross
>ONE edge without intersecting a point.

This seems like a useless piece of information - you still have to check
every edge of the polygon, and you still have to do *something* if a vertex
is right on the ray.  It's easy enough to construct polygons and points with
a ray going to a midpoint on an edge, with nearly half the vertices on the
ray also.

If all this is for ray tracing, then to get speed you want to avoid the
full-blown polygon interior calculation as much as possible.  Use bounding
boxes at least, cut arbitrary polygons into convex ones, use coherence.
A little preprocessing goes a long way...

>Steve Hawley
						stan shebs