From: Shawn Hargreaves Newsgroups: comp.os.msdos.djgpp Subject: Re: point inside polygon detection Date: Fri, 27 Mar 1998 19:27:46 +0000 Organization: None Message-ID: 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 Precedence: bulk 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