Date: Fri, 24 Oct 1997 15:19:29 +1100
From: Bill Currie <billc AT blackmagic DOT tait DOT co DOT nz>
Subject: Re: Polygon inside point detection
In-reply-to: <Pine.GSO.3.96.971023145200.19770B-100000@calvin.univalle.edu.co>
To: Guillermo Porras <guporras AT calvin DOT univalle DOT edu DOT co>, djgpp AT delorie DOT com
Message-id: <199710240216.PAA02680@teleng1.tait.co.nz gatekeeper.tait.co.nz>
Organization: Tait Electronics Limited
MIME-version: 1.0
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7BIT
Comments: Authenticated sender is <billc AT blackmagic DOT tait DOT co DOT nz>
Precedence: bulk

On 23 Oct 97 at 14:54, Guillermo Porras wrote:

> 
> Gruess Got,alle.
> 
> How can i know if a given point is inside a given 2d Polygon,...
> ..well at least a triangle. Thank you all.

Well, I think I just figured it out for a triangle.  If the three 
points defining the triangle (p1,p2 and p3) are defined so that they 
go counter-clockwise:

     p3
     /\
    /* \
 p1<__p_> p2

and p is the point in question, p will be inside the triangle if 
(`x' is the vector cross product):

(p - p1) x (p2 - p1) >= 0 &&
(p - p2) x (p3 - p2) >= 0 &&
(p - p3) x (p1 - p3) >= 0

If your points go in the other direction, either reverse the operands 
to `x' (for those unfamilliar with vector math, cross products are 
NOT commutable ('+' and '*' with numbers are)

Now, I could possibly be wrong, but it looks right on paper.
Also, I'm pretty sure the math can be simplified significantly 
(obviously, 2d will be cheaper than 3d).

hth

Bill
--
Leave others their otherness.