From: cbfalconer AT my-dejanews DOT com
Newsgroups: comp.os.msdos.djgpp
Subject: Re: point detection in triangles
Date: Wed, 04 Nov 1998 17:47:58 GMT
Organization: Deja News - The Leader in Internet Discussion
Lines: 31
Message-ID: <71q40e$b0n$1@nnrp1.dejanews.com>
References: <19981104121444 DOT 28324 DOT qmail AT hotmail DOT com> <Pine DOT SUN DOT 3 DOT 91 DOT 981104164758 DOT 28192B-100000 AT is>
NNTP-Posting-Host: 208.31.20.66
X-Article-Creation-Date: Wed Nov 04 17:47:58 1998 GMT
X-Http-User-Agent: Mozilla/3.0Gold (Win95; I)
X-Http-Proxy: 1.0 x4.dejanews.com:80 (Squid/1.1.22) for client 208.31.20.66
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

In article <Pine DOT SUN DOT 3 DOT 91 DOT 981104164758 DOT 28192B-100000 AT is>,
  djgpp AT delorie DOT com wrote:
>
> On Wed, 4 Nov 1998, a j wrote:
>
> > can anyone explain how you detect if a point is
> > inside or outside a triangle.. in a simple 2D x-y co-ord system.
>
> Draw a line from the point in any direction.  If it crosses the sides of
> the triangle an odd number of times, the point is inside; otherwise, it's
> outside.
>
> Depending on whether you care, there are some borderline cases when the
> point is exactly on one of the sides.
>
> > or offer some C code.. or a reference for places to get this info.
>
> I think I posted a general solution (good for any polygon, not just a
> triangle) a year or so ago.  Try searching the DJGPP forum archives at
> http://www.delorie.com/djgpp/mail-archives/ for words like "polygon".
>

I believe the subject, and that algorithm, is covered nicely in Sedgewicks
"Algorithms".  He also has methods for the peculiar cases.  I could be in
error on the book involved, don't have it here.

--
    Chuck Falconer (Charles_Falconer AT NOSPAMapsnet DOT com)

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own