From:	hughett AT chaplin DOT med DOT upenn DOT edu (Paul Hughett)
Newsgroups:	comp.os.msdos.djgpp
Subject:	Re: point inside polygon detection
Date:	27 Mar 1998 22:42:07 GMT
Organization:	University of Pennsylvania
Lines:	28
Message-ID:	<6fh9vv$kh0$1@netnews.upenn.edu>
References:	<6fce42$md4 AT bgtnsc02 DOT worldnet DOT att DOT net>
NNTP-Posting-Host:	chaplin.med.upenn.edu
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp

Steve Patton (leaphe AT pemail DOT net) wrote:

:   Is there a quick easy way to detect whether a point lies within the
: boundaries of a 2d polygon?  Right now I'm dealing with a four sided
: polygon.  This shape could be a rectangle (at any rotation angle, or
: distortion), trapazoid, etc, any 4 sided polygon.  This has to be checked a
: LOT, so I would appreciate an efficient algorithm.  Source code is not
: neccessary, if you can give me an idea, I can run with it.  Thanks!

Yes, there is a fast and even elegant method for this.  Let Q be the
point possibly within the polygon, and P1, ..., PN the vertices of the
polygon.  Let Qx be the ray (half line) extending from the point Q
to infinity in the direction of the positive X axis (or any other
direction).  For each side of the polygon P1-P2, P2-P3, ... P(N-1)-PN,
PN-P1, determine whether that side misses Qx, passes through it going
upwards, or passes through it going downwards.  Assign the values
0, +1, -1 to each of these cases and add up the values obtained for
each side.  If the sum is zero, Q is outside the polygon.  If it is
negative, the polygon surrounds Q in a clockwise direction; if positive,
the polygon surrounds Q counterclockwise.  There are various special
cases to consider:  A side may intersect Q.  The polygon may wind around
Q more than once.  By the way, that number that you've computed is
known as the winding number.  For more details, see a book on
computer graphics, where point/polygon problems are often treated in
detail.

Paul Hughett

- Raw text -