home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / graphics / 13494 < prev    next >
Encoding:
Text File  |  1993-01-07  |  1.6 KB  |  40 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!ira.uka.de!math.fu-berlin.de!informatik.tu-muenchen.de!lrz-muenchen.de!regent!har
  3. From: har@regent.e-technik.tu-muenchen.dbp.de (Hans Ranke)
  4. Subject: Re: Polygon-polygon intersection
  5. Message-ID: <har.726414217@regent.e-technik.tu-muenchen.de>
  6. Sender: news@regent.e-technik.tu-muenchen.de (News System)
  7. Organization: Technical University of Munich, Germany
  8. References: <7418@tivoli.UUCP> <1993Jan4.195436.2889@cis.uab.edu>
  9. Date: Thu, 7 Jan 1993 13:43:37 GMT
  10. Lines: 28
  11.  
  12. sloan@cis.uab.edu (Kenneth Sloan) writes:
  13.  
  14. >In article <7418@tivoli.UUCP> twb@tivoli.com (Tom Bereiter) writes:
  15. >>I'm looking for an efficient test for whether two 2D polygons intersect.
  16. >>The brute force approach seems to be: do a point-in-polygon test for each
  17. >>point of polyA in polyB, but if that says false you still have to check for
  18. >>line intersections.  This feels like the sort of problem, like area of
  19. >>a polygon, which has a non-obvious trivial answer.
  20. >>
  21. >Sorry, but I don't think there is a "non-obvious trivial answer".  In
  22. >the final analysis, I think you need:
  23.  
  24. >    *for all Va - is Va inside Pb
  25. >    *for all Vb - is Vb inside Pa
  26. >    *for all Ea - does Ea interect any Eb
  27.  
  28. I think it is sufficient to test
  29.  
  30.     *for only one Va - is Va inside Pb
  31.     *for only one Vb - is Vb inside Pa
  32.     *for all Ea - does Ea interect any Eb
  33.  
  34. Assuming that the polygons are not self-intersecting,
  35. the edge intersection test can be done in O(nlogn)
  36. using sweep line techniques.
  37.  
  38. --
  39. Hans Ranke   ranke@regent.e-technik.tu-muenchen.de
  40.