From:	Shawn Hargreaves <Shawn AT talula DOT demon DOT co DOT uk>
Newsgroups:	comp.os.msdos.djgpp
Subject:	Re: point inside polygon detection
Date:	Fri, 27 Mar 1998 19:27:46 +0000
Organization:	None
Message-ID:	<mK3qWCAy2$G1Ewpd@talula.demon.co.uk>
References:	<6fce42$md4 AT bgtnsc02 DOT worldnet DOT att DOT net>
NNTP-Posting-Host:	talula.demon.co.uk
MIME-Version:	1.0
Lines:	27
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp

Steve Patton writes:
>  Is there a quick easy way to detect whether a point lies within the
>boundaries of a 2d polygon?

Assuming that your polys are all stored in a right handed coordinate
system, for the triangle XYZ and the point P evaluate:

A = cross product of the vector X->Y and the vector Y->P
B = cross product of the vector Y->Z and the vector Z->P

Note this is done in 3d coordinates, using the x/y locations of your 2d
points and a z depth of zero. Now look at the sign of the z components
for your resulting A and B vectors: if they are both positive (or maybe
both negative: I can't remember which way around this is) the point lies
inside the poly.

That math can then be simplified a great deal, because you don't need to
bother with the full 3d cross product calculation when you only care
about the sign of the result.

btw. this question would really be more appropriate for
comp.graphics.algorithms: it doesn't have anything to do with djgpp!


--
Shawn Hargreaves - shawn AT talula DOT demon DOT co DOT uk - http://www.talula.demon.co.uk/
"Pigs use it for a tambourine" - Frank Zappa

- Raw text -