Date: Fri, 24 Oct 1997 16:07:30 +1100
From: Bill Currie <billc AT blackmagic DOT tait DOT co DOT nz>
Subject: Re: Polygon inside point detection
In-reply-to: <199710240216.PAA02680@teleng1.tait.co.nz gatekeeper.tait.co.nz>
To: guporras AT calvin DOT univalle DOT edu DOT co
Cc: djgpp AT delorie DOT com
Message-id: <199710240304.QAA02940@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
References: <Pine DOT GSO DOT 3 DOT 96 DOT 971023145200 DOT 19770B-100000 AT calvin DOT univalle DOT edu DOT co>
Comments: Authenticated sender is <billc AT blackmagic DOT tait DOT co DOT nz>
Precedence: bulk

On 24 Oct 97 at 15:19, Bill Currie wrote:
> 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

Just realized that will only work for 2d triangles, for 3d ('*' is 
being used as the dot operator):

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

Should work for 3d ( (p3 - p1) x (p2 - p1) is the normal to the plane 
defined by the triangle).

I just realized, you will still have to test whether the point is on 
the plane, but I can't remember how to do that ((p - p1) * ((p3 - p1) 
x (p2 - p1)) == 0 I think).

Bill
--
Leave others their otherness.