home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2530 < prev    next >
Encoding:
Internet Message Format  |  1992-08-29  |  3.7 KB

  1. Path: sparky!uunet!sun-barr!ames!agate!mickey!bsmith
  2. From: bsmith@mickey.NoSubdomain.NoDomain (Brian Smith)
  3. Newsgroups: comp.programming
  4. Subject: Re: How to decide if a point is inside a polygon?
  5. Date: 29 Aug 1992 05:15:35 GMT
  6. Organization: University of California, Berkeley
  7. Lines: 78
  8. Sender: bsmith@mickey (Brian Smith)
  9. Distribution: world
  10. Message-ID: <17n15nINNehp@agate.berkeley.edu>
  11. References: <7121@bigbird.hri.com.hri.com> <schnitzi.714934670@eola.cs.ucf.edu> <1992Aug27.153902@is.morgan.com> <schnitzi.715017774@eola.cs.ucf.edu> <1992Aug28.134203@is.morgan.com> <schnitzi.715032142@eola.cs.ucf.edu> <thompson.715056569@malthus.econ.umn.edu>
  12. NNTP-Posting-Host: mickey.cs.berkeley.edu
  13.  
  14. I got this off the net a while ago.  The original poster was Michael J.
  15. Zehr, from MIT at the time.  It uses a clever version of the "scan in any
  16. direction any see how many times the point crosses the polygon" test that, as
  17. far as I know, handles the special cases correctly.
  18.  
  19. ------------------
  20.  
  21. (in pseudo C:)
  22.  
  23.   edge[] is an array of edges
  24.   an edge has two fields, end1 and end2, plus four precomputed values
  25. to speed up the actual check: slope, intercept, minx and maxx
  26.     slope = (end2.y - end1.y)/(end2.x - end1.x)
  27.     intercept = end2.y - slope*end2.x
  28.     minx = min(end1.x, end2.x)
  29.     maxx = max(end1.x, end2.x)
  30.   an "end" has two fields, x and y
  31.  
  32. {this isn't the same datastructure i'm using, so i'm paraphrasing
  33. for simplicity and readability}
  34.  
  35. flag = FALSE;
  36. for (k=0; k<num_edges; k++)
  37.     if ((x > edge[k].end1.x) ^ (x > edge[k].end2.x))
  38.         {
  39.         if (y < (temp = edge[k].intercept + edge[k].slope*x)
  40.             flag = !flag;
  41.         else if (y==temp) 
  42.             /* point is on an edge so do whatever you want with it */;
  43.         }
  44.     else if (edge[k].end1.x == edge[k].end2.x)
  45.         if ((y > edge[k].end1.y) ^ (y > edge[k].end2.y))
  46.             /* point is on an edge so do whatever you want with it */;
  47.  
  48. after it's checked each edge, flag == TRUE implies it's inside,
  49. flag == FALSE implies it's outside the polygon.
  50.  
  51. the multiply only occurs when a vertical line extended from the point
  52. being tested intersects with the edge. it then computes the intersection
  53. point, and checks if the point is below the edge.  if so, it counts as
  54. an intersection.  the multiply is only executed when there is a possible
  55. intersection, which is zero, one or two times for a convex polygon. 
  56. this works as-is for concave, but doesn't guarantee only two multiplies.
  57. depending on your compiler and specific machine, it may be marginally 
  58. faster to keep track of the lowest and highest end of each edge, and
  59. put another if statement before the one that computes the actual
  60. intersection, but i haven't tried this to see
  61. then you'd have:
  62.  
  63. if (y < edge[k].min_y) flag^= TRUE;
  64. else if (y <= edge[k].max_y) 
  65.         if (y < (temp= ....
  66.  
  67. Also, if your polygon are usually short and fat then you'd want to 
  68. change that to a horizontal line test instead of the current vertical
  69. line test.  Also, if your polygons are guaranteed convex, you could count
  70. the number of times the x tested true, and after the second one you
  71. wouldn't have to look at any more edges.
  72.  
  73. BTW, there's a faster way to code the tests, at least for my
  74. hardware/compiler combination:  precompute a max and min x and y for
  75. each edge (uses up a lot of space, but does really help for a lot of
  76. tests).  Then instead of:
  77.  
  78. ((x > edge[k].end1.x) ^ (x > edge[k].end2.x))
  79.  
  80. use:
  81.  
  82. ((x > edge[k].minx) && (x <= edge[k].maxx))
  83.  
  84. you avoid always having to do both compares, which is the where most of
  85. the speed comes from.  in addition, some compilers don't produce good
  86. code for the first code fragment.
  87.  
  88. -----
  89. Brian C. Smith                arpa:  bsmith@cs.Berkeley.EDU
  90. University of California, Berkeley    uucp: uunet!ucbvax!postgres!bsmith
  91. Computer Sciences Department        phone: (510)642-9585
  92.