NetNews Usenet Archive 1992 #19/NN_1992_19.iso/spool/comp/programm/2503

Text File | 1992-08-27 | 1.6 KB | 33 lines

Newsgroups: comp.programming
Path: sparky!uunet!usc!cs.utexas.edu!uwm.edu!csd4.csd.uwm.edu!markh
From: [e-mail] (Mark)
Subject: Re: How to decide if a point is inside a polygon?
Message-ID: <[e-mail]>
Sender: [e-mail] (USENET News System)
Organization: Computing Services Division, University of Wisconsin - Milwaukee
References: <[e-mail]>
Date: Thu, 27 Aug 1992 17:03:49 GMT
Lines: 21

In article <[e-mail]> [e-mail] writes:
>I am in need of an algorithm to compute whether or not a given
>point exists within or without a polygon. Any help or pointers to
>where to look would be much appreciated.

Implement a polygon by putting its vertices in counter-clockwise order in a
circular list.  A line drawn from a point inside to each of the vertices of
the list will move in a counter clockwise direction as you go through each
vertex in the list.  In other words, the sum of the angles AVB where V is the
point in question and A and B are adjacent items in the circular list, where
each angle is measured in a counterclockwise direction, will be 360 degrees.
If the point lies outside the polygon, this sum will be 0.  If the point, V,
lies ON the polygon, the sum will be 360.

So, this algorithm is linear in the number of vertices in the polygon.

In order to verify that you properly implemented the polygon, you have to
perform a one-time check to make sure that the sum of all the angles ABC,
where A, B, and C are adjacent items in the circular list, is 180*(N - 2)
degrees, where N is the number of points in the polygon.  Again, the angles
are measured in a counterclockwise direction.