home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / 10807 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  3.5 KB
  1. Path: sparky!uunet!olivea!decwrl!sun-barr!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sample.eng.ohio-state.edu!purdue!mentor.cc.purdue.edu!noose.ecn.purdue.edu!samsung!balrog!web.ctron.com!wilson
  2. From: wilson@web.ctron.com (David Wilson)
  3. Newsgroups: sci.math
  4. Subject: Re: Polygon point enclosure
  5. Message-ID: <4923@balrog.ctron.com>
  6. Date: 1 Sep 92 18:26:25 GMT
  7. Sender: usenet@balrog.ctron.com
  8. Reply-To: wilson@web.ctron.com (David Wilson)
  9. Organization: Cabletron Systems INc.
  10. Lines: 70
  11.  
  12.  
  13.  
  14.     Given a point P and polygon POLY in a plane, to determine if the
  15.     point lies inside, outside, or on POLY to within a tolerance TOL.
  16.     The following is a suped-up version of ray-crossing algorithm.
  17.  
  18.     -------------------------------------------------------------------
  19.  
  20.     Translate POLY so that P is at the origin, that is, translate POLY
  21.     by -P.
  22.  
  23.     Let A be the closed halfplane y >= 0, and let B be the open
  24.     halfplane y < 0.  Let PARITY be the parity of the number of times
  25.     POLY crosses from A to B to the right of P.  Initialize PARITY to
  26.     0.
  27.  
  28.     Loop through each edge E of POLY
  29.  
  30.     If the origin is within tolerance of E, then the point is
  31.     on POLY, and we are done.*
  32.  
  33.     If one endpoint of E is in A, and the other is in B, then
  34.     locate the x-intercept of E.  If its x-coordinate is positive,
  35.     complement PARITY (i.e., let PARITY = 1-PARITY).
  36.  
  37.     end loop
  38.  
  39.     If PARITY is 0, then the point is outside POLY, if odd,
  40.     the point is inside POLY, and we are done.
  41.  
  42.     -------------------------------------------------------------------
  43.  
  44.     Since we count crossings from A to B rather than crossing of the
  45.     positive x-axis, we avoid the messiness associated with polygon
  46.     vertices on the x-axis.
  47.  
  48.     If you need to determine if the point is on the polygon to within
  49.     tolerance, then most of the work of the algorithm will be done in
  50.     trying to decide if the origin is within tolerance of an edge.
  51.     Preliminary extents checking will reduce the number of times the
  52.     perpendicular distance from the origin to the edge segment need be
  53.     calculated, but this calculation cannot be entirely avoided.  If
  54.     you are not fussy about the polygon vertices, you may use the L1
  55.     norm in lieu of the L2 norm, or omit testing the polygon vertices
  56.     altogether.  Otherwise, you can avoid retesting vertices by
  57.     ordering the edges in polygon order and checking only one vertex
  58.     per edge (the second vertex of that edge will then be the first
  59.     vertex of the next edge, and will be tested in the next loop).
  60.  
  61.     If you are satisfied with an inside/outside answer, that is, you do
  62.     not care if the point is on the polygon, you can dispense with
  63.     checking the edge against the origin altogether (which means that
  64.     the tolerance is unnecessary).  This is accomplished by omitting
  65.     the line with the asterisk from the above algorithm.  This omission
  66.     results in significant speedup of the loop.
  67.  
  68.     In higher dimensions, we first test if P is in the plane of the
  69.     polygon to within tolerance.  If not, clearly P is not in the
  70.     polygon.  Otherwise, project both P and the polygon to two
  71.     dimensions and perform the above algorithm on the projected point
  72.     and plane.  Judicious choice of the projection plane, reduces the
  73.     projection to selection of two coordinates from each projected
  74.     point.
  75.  
  76.  
  77. -- 
  78. David W. Wilson (wilson@web.ctron.com)
  79.  
  80. Disclaimer: "Truth is just truth...You can't have opinions about truth."
  81. - Peter Schikele, introduction to P.D.Q. Bach's oratorio "The Seasonings."
  82.