home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / graphics / 13367 < prev    next >
Encoding:
Text File  |  1993-01-04  |  1.8 KB  |  48 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!wupost!emory!cs.utk.edu!willis1.cis.uab.edu!sloan
  3. From: sloan@cis.uab.edu (Kenneth Sloan)
  4. Subject: Re: Polygon-polygon intersection
  5. Message-ID: <1993Jan4.195436.2889@cis.uab.edu>
  6. Organization: CIS, University of Alabama at Birmingham
  7. References: <7418@tivoli.UUCP>
  8. Date: Mon, 4 Jan 1993 19:54:36 GMT
  9. Lines: 37
  10.  
  11. In article <7418@tivoli.UUCP> twb@tivoli.com (Tom Bereiter) writes:
  12. >I'm looking for an efficient test for whether two 2D polygons intersect.
  13. >The brute force approach seems to be: do a point-in-polygon test for each
  14. >point of polyA in polyB, but if that says false you still have to check for
  15. >line intersections.  This feels like the sort of problem, like area of
  16. >a polygon, which has a non-obvious trivial answer.
  17. >
  18. Sorry, but I don't think there is a "non-obvious trivial answer".  In
  19. the final analysis, I think you need:
  20.  
  21.     *for all Va - is Va inside Pb
  22.     *for all Vb - is Vb inside Pa
  23.     *for all Ea - does Ea interect any Eb
  24.  
  25. But - depending on your distribution of polygons, there may be numerous
  26. "quick kills" - usually "trivial reject"-type tests.  Whether trying
  27. these first is "efficient" or not depends on your set of polygons.
  28.  
  29. I would try (in order):
  30.  
  31.     *X-overlap
  32.     *Y-overlap
  33.     *all Va outside convex hull of Pb
  34.     *all Vb outside convex hull of Pa
  35.  
  36. and then bite the bullet and go for the three tests above.
  37.  
  38. But....this is probably only worthwhile if your polygons are complicated
  39. (have a lot of vertices, or are concave).  If your polygons are
  40. triangles, or convex quadrilaterals...start with brute force.
  41.  
  42.  
  43. -- 
  44. Kenneth Sloan                   Computer and Information Sciences
  45. sloan@cis.uab.edu               University of Alabama at Birmingham
  46. (205) 934-2213                  115A Campbell Hall, UAB Station 
  47. (205) 934-5473 FAX              Birmingham, AL 35294-1170
  48.