Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rochester!udel!klaiber
From: klaiber@udel.EDU (Alexander Klaiber)
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited... A NEW APPROACH
Message-ID: <284@louie.udel.EDU>
Date: Wed, 17-Jun-87 11:40:19 EDT
Article-I.D.: louie.284
Posted: Wed Jun 17 11:40:19 1987
Date-Received: Sun, 21-Jun-87 09:43:34 EDT
References: <948@elrond.CalComp.COM> <790@thumper.UUCP>
Sender: usenet@udel.EDU
Reply-To: klaiber@udel.EDU (Alexander Klaiber)
Organization: University of Delaware
Lines: 96
Keywords: ray tracing, graphics, polygon intersection


Any other suggestions?  Well, there IS another way, which requires a little
preprocessing, but otherwise is quite efficient: (concave polygons only)
for n edges, we need 3*n multiplications and 4*n additions/subtractions/tests

Preprocessing is affordable, given it's only performed once whereas
intersection tests occur kinda frequently in raytracing. (It's rather
simple, anyway)

Now for those that aren't familiar with the normal-form of a plane: A plane
in 3-space can either be represented by one point on the plane and two
non-collinear vectors spanning the plane.
Example: r=r0+lambda*u+mu*v, 	where r0 is the point on the plane, lambda
and mu are parameters and u and v are the vectors spanning the plans.

Very often another representation, the normal form, is desirable. Here a
plane is defined by its normal vector and its distance from the origin of
the coordinate-system.
Example: r*n - d = 0, 	where n is the normal vector, '*' is the dot
product and d is the distance of the plane from the origin. Note that d may
be computed by simply picking a point on the plane, say r0, and computing
d=r0*n. Note that d will be positive if the origin lies "on the other side"
of the plane withrespect to the direction of the normal vector. I.e. the
direction of the normal vector defines an "up" and a "down" side of the
plane. This will be important.
To see where a point given by vector r lies with respect to the plane, all
you do is plug it in above formula, i.e. compute r*n-d. There are tree
cases for the result:
	>0	the point is on the side of the plane the normal points to
	=0	the point is on the plane
	<0	the point is on the "other" side of the plane

	       the plane normal
		    ^
		    |   (>0 here)
		    |
                    |
        ----------------------------- the plane (=0 on the plane)

			(<0 here)


NOW: assume the Polygon is specified by its vertices P1...Pn. Assume these all
lie in the same pane. Also, assume we have a point PI which is known to be
inside the polygon (use 1/n*(P1+P2+...+Pn), for example).

Now we'll represent the polygon by 
(1) the plane it lies in 
(2) planes, 1 per edge, that "stand up" perpendicular to the polygon-plane 
    and that are erected over "their" respective edges.

Think of the polygon lying flat on the table, then the (projection onto the
table of the) planes in (2) (which stand up vertically from the table)
represent the "cuts" you'd have to make to cut out the polygon from a sheet
of paper.

Now, representing each of these "walls" in the normal-form (normal ni and
distance di), all we have to do is select the direction of the ni's such
that our sample point PI is on the side the normal ni points to, that is,
	rPI * ni - di >0, 	where rPI is the space vector for PI
this is simple: Just plug PI into the formula and if the result is<0, jus
reverse the signs of ni and di.

FINALLY: Given a point P (vector r) that lies on the polygon-plane. To
detect whether it is also inside the polygon, do the following:
      For every edge i (now given by ni,di):
	 compute temp := r * ni - di
	 if temp<0, then exit with "point outside polygon"
      end
      "if we reach end of FOR: point is inside"

ANALYSIS: 
* time: For two 3-vectors x=(x1 x2 x3) and y=(y1 y2 y3), the dot product is
	x1*y1 + x2*y2 + x3*y3. This requires 3 multiplications and 2
	additions. Moreover, we have one subtraction (-di) and one test
	(<0) per edge. For n edges, this gives a worst case of
		3n mult's and 4n add's
	the worst case occurs, if the point indeed is inside the polygon,
	which is of course not always the case.
* space: After preprocessing, we can of course throw away the points P1..Pn
        and the inner point, PI. What we keep is:
	(1) the polygon plane in normal form: normal n and dist d
	(2) for each edge: ni and di
	{(1) is needed to find the intersection of the ray with the poly
	 plane in the first place}
	Assuming 3-vectors, a polygon with n edges requires
		4(n+1)
	real numbers.

The beauty of this method is that it's fast enough, works entirely in
world-coordinates and does not have any of the problems of the other
proposal.


---------------------------------------------------------------------------
Standard disclaimer etc etc etc.