home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 12064 < prev    next >
Encoding:
Text File  |  1992-11-18  |  2.3 KB  |  61 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: <BxxoH3.BAH@slipknot.rain.com>
  6. Reply-To: robert@slipknot.rain.com.UUCP (Robert Reed)
  7. Organization: Home Animation Ltd.
  8. References: <1992Nov17.132302.6345@sophia.smith.edu> <BxvnnI.90x@slipknot.rain.com> <1992Nov18.003415.9990@cis.uab.edu>
  9. Date: Wed, 18 Nov 1992 22:43:50 GMT
  10. Lines: 49
  11.  
  12. In article <1992Nov18.003415.9990@cis.uab.edu> sloan@cis.uab.edu (Kenneth Sloan) writes:
  13. |In article <BxvnnI.90x@slipknot.rain.com> robert@slipknot.rain.com.UUCP (Robert Reed) writes:
  14. |>
  15. |>A trivial modification to the algorithm as I suggested it would correct for
  16. |>this.  If the boundaries of any polygon are to be considered interior, then if
  17. |>a bounding edge is collinear with the test point, it is sufficient to test
  18. |>whether the point is within the interval of the edge.  If it is not, the edge
  19. |>is trivially rejected as before.  If it is, the algorithm can be prematurely
  20. |>terminated with a TRUE result.
  21. |
  22. |Your "trivial modification" is virtually *all* of Professor O'Rourke's
  23. |algorithm!  By the time you make this trivial modification to your
  24. |algorithm, you might just as well throw away your algorithm.
  25.  
  26. Hardly.  My test is:
  27.  
  28.     if (t[n].y == t[n+1].y) {
  29.         if (t[n].y == p.y) {
  30.             if (t[n].x < t[n+1].x) {
  31.                 l = t[n].x;
  32.                 r = t[n+1].x;
  33.             }
  34.             else {
  35.                 r = t[n].x;
  36.                 l = t[n+1].x;
  37.             }
  38.             if (p.x >= l && p.y <= r)
  39.                 return (TRUE);
  40.         }
  41.  
  42.         /* discard point t[n+1] */
  43.     }
  44.  
  45. Note that most of this code gets executed only in the rare case that point p is
  46. collinear with a triangle edge which is horizontal.  I forget which one was
  47. "O'Rourke's Algorithm" so I can't address how much of that this is.
  48.  
  49. Given the explanation of the LeftOfOrOn algorithm, it may be slightly more
  50. efficient in the case of triangles, substituting three cross products for at
  51. most two intersection tests, but it certainly doesn't scale to polygons of more
  52. than three points.
  53. ________________________________________________________________________________
  54. Robert Reed            Home Animation Ltd.        503-656-8414
  55. robert@slipknot.rain.com    5686 First Court, West Linn, OR 97068
  56.  
  57. Outside of a dog, a book is a man's best friend; 
  58. and inside a dog, it's too dark to read.
  59. -- Grouch Marx
  60. ________________________________________________________________________________
  61.