home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 12084 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  2.0 KB
  1. Path: sparky!uunet!dtix!darwin.sura.net!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!dog.ee.lbl.gov!hellgate.utah.edu!lanl!newshost.lanl.gov!hinker
  2. From: hinker@acl.lanl.gov (Paul J. Hinker)
  3. Newsgroups: comp.graphics
  4. Subject: Polygon (or point) within an arbitrary polygon
  5. Message-ID: <HINKER.92Nov19081251@cocker.acl.lanl.gov>
  6. Date: 19 Nov 92 15:12:51 GMT
  7. Sender: news@newshost.lanl.gov
  8. Reply-To: Paul J. Hinker <hinker@acl.lanl.gov>
  9. Organization: Advanced Computing Lab, LANL, NM
  10. Lines: 34
  11.  
  12.  
  13.    Let me start out by saying that I've very much enjoyed the recent
  14. threads concerning point in a triangle and convexity of a polygon
  15. since they both relate directly to some things I've been working on.
  16.    
  17.    I would like to take the point in a triangle question a step
  18. further and ask if there is an efficient way to decide whether or not
  19. a polygon (or point for that matter) is contained by another polygon.
  20.  
  21.    The problem goes like this :
  22.  
  23.    I have Polygon1 and Polygon2 described by their respective vertice
  24. lists and bounding boxes and I would like to find out whether or not
  25. Polygon1 *contains* Polygon2.  Nothing else is known about either
  26. polygon.
  27.  
  28.    My first thought was to place a point outside Polygon1 and check to
  29. see if a segment drawn between it and Polygon2 intersects any of the
  30. segments that make up Polygon1.  This method is easily foiled.
  31.  
  32.    Next I thought that if I triangulated Polygon1 I could check each
  33. of the generated triangles to see if they contained the point in
  34. question.
  35.  
  36.    This last method seems to work well but it is very slow.  The test
  37. is carried out many thousands (hundreds of thousands) of times.
  38.  
  39.    Thanks in advance for any pointers,
  40.  
  41. --
  42. Paul Hinker hinker@acl.lanl.gov    ///  If it works, it's not state-of-the-art
  43. MS B287        505-665-6396          ///                           --Hansen's Law
  44. Los Alamos National Labs ACL  \\\///    All our stuff is broke
  45. Los Alamos, NM  87545          \XX/                    --Forslund's Corollary
  46.