home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 11956 < prev    next >
Encoding:
Text File  |  1992-11-17  |  3.9 KB  |  77 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!tessi!eaglet!slipknot!robert
  3. From: robert@slipknot.rain.com (Robert Reed)
  4. Subject: Re: Point inside a triangle
  5. Message-ID: <Bxtz3s.6xA@slipknot.rain.com>
  6. Reply-To: robert@slipknot.rain.com.UUCP (Robert Reed)
  7. Organization: Home Animation Ltd.
  8. References: <7bv1svg@rpi.edu> <BxsLL1.5H5@slipknot.rain.com> <1992Nov16.115211.23169@sophia.smith.edu>
  9. Date: Mon, 16 Nov 1992 22:43:03 GMT
  10. Lines: 65
  11.  
  12. In article <1992Nov16.115211.23169@sophia.smith.edu> orourke@sophia.smith.edu (Joseph O'Rourke) writes:
  13. |In article <BxsLL1.5H5@slipknot.rain.com> robert@slipknot.rain.com.UUCP (Robert Reed) writes:
  14. |>The standard edge crossing test, which works for any other polygon, should
  15. |>work fine here.
  16. |
  17. |    Although this is a matter of taste, I find this inferior to
  18. |the algorithm that I use, which tests if the point is left-of-or-on
  19. |the three directed lines determined by pairs of vertices of the triangle.
  20. |In the edge crossing code, one must deal with the ray crossing a
  21. |vertex, being parallel to an edge, being collinear with an edge:
  22. |
  23. |                   /\
  24. |                  /  \
  25. |                 /    \
  26. |            *---+------+------>
  27.  
  28. The special cases are trivial to discard, if the ray intersects a vertex, the
  29. adjacent vertices must have Y values of opposite sign (assuming a horizontal
  30. ray) to represent a crossing.  If the point is collinear with an edge, discard
  31. it.  You don't need it.  In the case above, the horizontal edge is discarded
  32. (by discarding one of the colinear vertices) and the result is no crossing
  33. because the new adjacent points (collapsed in the case of a triangle to a
  34. single point) have the same Y sign.  0 crossings mark the point as exterior.
  35.  
  36.                                                 /       ___        
  37.                                                / *  ___/           
  38.                                               / ___/               
  39.                                             _/_/                   
  40.                                         ___//                      
  41.                       __            ___/   /                       
  42.                         \__     ___/      /                        
  43.                            \___/      *  /                         
  44.                         ___/  \__       /                          
  45.                        /         \__   /                           
  46.                                     \_/                            
  47.                                      / \__                         
  48.                                     /     \__                      
  49.                                    /    *    \                     
  50.                                                                              
  51.  
  52.  
  53. Now, it's not clear from your description how your left-of-or-on algorithm
  54. works, or in particular how it would distinguish between the three points
  55. marked with asterisks in the above triangle, each of which has two lines to the
  56. left and one to the right.
  57. ________________________________________________________________________________
  58. Robert Reed            Home Animation Ltd.        503-656-8414
  59. robert@slipknot.rain.com    5686 First Court, West Linn, OR 97068
  60.  
  61. I got on the bus and worked my way to the back where I sat down next to a
  62. beautiful blond chinese girl. 
  63. "Hi" I said, "Isn't it an amazing day?" 
  64. "Oh I guess so." she replied.  
  65. "Why so glum?" I asked.  
  66. She started to tell me but stopped and said, "Why would I want to tell a
  67. stranger?" 
  68. I told her that some times it's a good idea to unload on a perfect stranger
  69. in the back of a bus.
  70. She thought about this for a while and replied, "Well, I just came from my
  71. analyst and he can't help any more.  You see......I am a nymphomaniac who
  72. only gets turned on by Jewish cowboys!" 
  73. I told her how sorry I was when she asked, "By the way, what is your name?"
  74. to which I immediately replied, "Buckaroo Goldstein!!"
  75. --Steven Wright
  76. ________________________________________________________________________________
  77.