home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2529 < prev    next >
Encoding:
Internet Message Format  |  1992-08-29  |  1.6 KB
  1. Path: sparky!uunet!stanford.edu!bcm!rice!news.rice.edu!dougm
  2. From: dougm@titan.cs.rice.edu (Doug Moore)
  3. Newsgroups: comp.programming
  4. Subject: Re: How to decide if a point is inside a polygon?
  5. Message-ID: <DOUGM.92Aug28232651@titan.cs.rice.edu>
  6. Date: 29 Aug 1992 05:26:51 GMT
  7. References: <7121@bigbird.hri.com.hri.com> <schnitzi.714934670@eola.cs.ucf.edu>
  8.     <1992Aug27.153902@is.morgan.com> <schnitzi.715017774@eola.cs.ucf.edu>
  9.     <1992Aug28.134203@is.morgan.com> <schnitzi.715032142@eola.cs.ucf.edu>
  10.     <thompson.715056569@malthus.econ.umn.edu>
  11. Sender: news@rice.edu (News)
  12. Organization: Rice University Computer Science, Houston, Texas
  13. Lines: 20
  14. In-Reply-To: thompson@atlas.socsci.umn.edu's message of 29 Aug 1992 02:49:29 GMT
  15.  
  16. schnitzi@cs.ucf.edu (Mark Schnitzius) writes:
  17. >You are right; sorry, I misunderstod your earlier point.  So how can we
  18. >get this to work for all cases?  Just find a direction to extend the
  19. >infinite line that doesn't intersect any vertices?
  20.  
  21. This is not hard to solve.  From the point, extend a ray infinitely
  22. far in the +x direction.  Count a side of the polygon if it intersects
  23. the ray with one of its endpoints strictly below the ray and the other
  24. on-or-above the ray.  If the ray hits a vertex and both sides
  25. containing that vertex are below the ray, both are counted.  If both
  26. sides are above, neither is counted.  If one is above and one is
  27. below, exactly one is counted.  If the segment lies on the ray, it is
  28. not counted.
  29.  
  30. This algorithm is O(n), for an n-sided polygon.  With O(n)
  31. preprocessing, inside/outside queries can be answered in O(log n) time
  32. per query.
  33.  
  34. Doug Moore
  35. (dougm@cs.rice.edu)
  36.