Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!mit-eddie!genrad!decvax!ucbvax!ucdavis!egg-id!ui3!wsucshp!mike
From: mike@wsucshp.UUCP (Mike Kibler - CSB2056)
Newsgroups: comp.graphics
Subject: Re: Point inside of polygon revisited...
Message-ID: <80005@wsucshp.UUCP>
Date: Thu, 18-Jun-87 01:43:15 EDT
Article-I.D.: wsucshp.80005
Posted: Thu Jun 18 01:43:15 1987
Date-Received: Mon, 22-Jun-87 04:11:57 EDT
References: <948@elrond.CalComp.COM>
Organization: WSU Computer Science
Lines: 48



Another approach is one that I used in a a polygon clipper.
It is derived from Sutherland and Hodgman's polygon
clipping algorithm described in Foley and Van Dam, Fundamentals
of Interactive Computer Graphics, July 1984. pp 450-455.

An application which could work for you, although expensive is:

It assumes the vertices are ordered in a clockwise manner. 
At least three vertices in polygon.
Right handed coordinate system

   still_in = true               

   v1 = Ist vertex in polygon.
   v2 = 2nd vertex in polygon.
   v3 = 3rd vertex in polygon.
   polygon_outer_normal = cross_product(v3-v2,v1-v2)
   more_vertices = num_vertices_in_polygon

   While (more_vertices and still-in) do

       more_vertices--
       v2=next vertex in polygon

       if (same_direction(cross product(v2-v1,point-v1),
           polygon_outer_normal)) still-in = false
       else
          v1 = v2

   end while


Of course all the normal cross product boundary checking must
be done. 





 ---- Mike  ( Those who can do, do, those who can't simulate! )

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 Michael K. Kibler        CSNET:  mike%cs1.wsu.edu@RELAY.CS.NET
 Computer Science Dept.   UUCP:   ..!ucbvax!ucdavis!egg-id!ui3!wsucshp!mike
 Washington State Univ.   BITNET: kibler@wsuvm1.BITNET
 Pullman, WA. 99164-1210  PHONE:  509-335-2723 or 509-335-6636