home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 12086 < prev    next >
Encoding:
Text File  |  1992-11-19  |  2.0 KB  |  47 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!nntp.msstate.edu!willis1.cis.uab.edu!sloan
  3. From: sloan@cis.uab.edu (Kenneth Sloan)
  4. Subject: Re: Polygon (or point) within an arbitrary polygon
  5. Message-ID: <1992Nov19.162151.12862@cis.uab.edu>
  6. Organization: CIS, University of Alabama at Birmingham
  7. References: <HINKER.92Nov19081251@cocker.acl.lanl.gov>
  8. Date: Thu, 19 Nov 1992 16:21:51 GMT
  9. Lines: 36
  10.  
  11. In article <HINKER.92Nov19081251@cocker.acl.lanl.gov> Paul J. Hinker <hinker@acl.lanl.gov> writes:
  12. >...
  13. >   
  14. >   I would like to take the point in a triangle question a step
  15. >further and ask if there is an efficient way to decide whether or not
  16. >a polygon (or point for that matter) is contained by another polygon.
  17. >
  18.  
  19. Point-in-polygon has been thrashed out here - Eric Haines has the
  20. history.  Beware of solutions whose idea of "inside" differs from yours.
  21.  
  22. Polygon-in-polygon seems to me to be a very hard problem.  Let's see: if
  23. al you want is a YES/NO answer to the question 'does polygon P lie
  24. entirely inside polygon Q', then:
  25.  
  26.     *all vertices of P must lie inside Q (see Eric)
  27.     *all segments of the perimeter of P must lie inside Q
  28.   
  29. The first condition is necessary, but not sufficient.  The second
  30. condition is both necessary and sufficient (but probably has
  31. sub-problems just like the first condition).
  32.  
  33. I would expect a practical solution to this problem to consist of
  34. several "quick-kill" tests (all giving the answer "NO") followed by one
  35. very expensive test to make sure the answer is "YES".  I can't
  36. immediately see any alternative to intersecting every segment of P's
  37. perimeter with every segment of Q's perimeter (plus one Point-in-Polygon
  38. test to distinguish between totally-in and totally-out.
  39.  
  40. You could always announce a contest...
  41.  
  42. -- 
  43. Kenneth Sloan                   Computer and Information Sciences
  44. sloan@cis.uab.edu               University of Alabama at Birmingham
  45. (205) 934-2213                  115A Campbell Hall, UAB Station 
  46. (205) 934-5473 FAX              Birmingham, AL 35294-1170
  47.