From: robert@slipknot.rain.com (Robert Reed)
Subject: Re: Point inside a triangle
Reply-To: robert@slipknot.rain.com.UUCP (Robert Reed)
Organization: Home Animation Ltd.
Date: Mon, 16 Nov 1992 22:43:03 GMT

In article <1992Nov16.115211.23169@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes:
|In article <BxsLL1.5H5@slipknot.rain.com> robert@slipknot.rain.com.UUCP (Robert Reed) writes:
|>The standard edge crossing test, which works for any other polygon, should
|>work fine here.
|
|	Although this is a matter of taste, I find this inferior to
|the algorithm that I use, which tests if the point is left-of-or-on
|the three directed lines determined by pairs of vertices of the triangle.
|In the edge crossing code, one must deal with the ray crossing a
|vertex, being parallel to an edge, being collinear with an edge:
|
|			       /\
|			      /  \
|			     /    \
|			*---+------+------>

The special cases are trivial to discard, if the ray intersects a vertex, the
adjacent vertices must have Y values of opposite sign (assuming a horizontal
ray) to represent a crossing.  If the point is collinear with an edge, discard
it.  You don't need it.  In the case above, the horizontal edge is discarded
(by discarding one of the colinear vertices) and the result is no crossing
because the new adjacent points (collapsed in the case of a triangle to a
single point) have the same Y sign.  0 crossings mark the point as exterior.

                                                /       ___        
                                               / *  ___/           
                                              / ___/               
                                            _/_/                   
                                        ___//                      
                      __            ___/   /                       
                        \__     ___/      /                        
                           \___/      *  /                         
                        ___/  \__       /                          
                       /         \__   /                           
                                    \_/                            
                                     / \__                         
                                    /     \__                      
                                   /    *    \                     
                                                                             


Now, it's not clear from your description how your left-of-or-on algorithm
works, or in particular how it would distinguish between the three points
marked with asterisks in the above triangle, each of which has two lines to the
left and one to the right.
________________________________________________________________________________
Robert Reed			Home Animation Ltd.		503-656-8414
robert@slipknot.rain.com	5686 First Court, West Linn, OR 97068

I got on the bus and worked my way to the back where I sat down next to a
beautiful blond chinese girl. 
"Hi" I said, "Isn't it an amazing day?" 
"Oh I guess so." she replied.  
"Why so glum?" I asked.  
She started to tell me but stopped and said, "Why would I want to tell a
stranger?" 
I told her that some times it's a good idea to unload on a perfect stranger
in the back of a bus.
She thought about this for a while and replied, "Well, I just came from my
analyst and he can't help any more.  You see......I am a nymphomaniac who
only gets turned on by Jewish cowboys!" 
I told her how sorry I was when she asked, "By the way, what is your name?"
to which I immediately replied, "Buckaroo Goldstein!!"
--Steven Wright
________________________________________________________________________________
Newsgroups: comp.graphics