home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / graphics / 13373 < prev    next >
Encoding:
Internet Message Format  |  1993-01-04  |  2.1 KB

  1. Path: sparky!uunet!spool.mu.edu!olivea!mintaka.lcs.mit.edu!ai-lab!fiber-one!sundar
  2. From: sundar@fiber-one.ai.mit.edu (Sundar Narasimhan)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Polygon-polygon intersection
  5. Message-ID: <1iadoeINN2hj@life.ai.mit.edu>
  6. Date: 4 Jan 93 22:29:34 GMT
  7. References: <7418@tivoli.UUCP> <1993Jan4.195436.2889@cis.uab.edu>
  8. Sender: sundar@fiber-one (Sundar Narasimhan)
  9. Reply-To: sundar@ai.mit.edu
  10. Organization: MIT Artificial Intelligence Laboratory
  11. Lines: 34
  12. NNTP-Posting-Host: fiber-one.ai.mit.edu
  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. This seems to come up repeatedly, and it DOES have a simple answer,
  21. (simple, oh no, there's that word again :-) -- maybe this should be in the
  22. FAQ. 
  23.  
  24. Polygon intersection can be reduced to point in polygon in linear time. 
  25. Basically convolve A & B, reducing A to a point and growing B by the
  26. corresponding amount. Now test if the reference point of A is within the
  27. grown B. In 2-D the convolution of two polygons is still a polygon, and in
  28. 3-D two polyhedra convolved will give another polyhedron and the problem
  29. reduces to point in polyhedron. 
  30.  
  31. Note that in 2-D a polygon has 3 degrees of freedom. Thus, if only one
  32. of your polygons is moving, you can construct a convolution in 2+1D
  33. and test for intersection extremely fast just given the moving polygon's
  34. configuration.
  35.  
  36. I have code to do this which I am presently using for my thesis, but I
  37. can strip out the convolvers if you are desparate. (In 2-D my algorithm
  38. is essentially that of Guibas et al. the reference to whose paper, I've
  39. included below). 
  40.  
  41. %Y Conference
  42. %A Guibas, L., Ramshaw, L., and Stolfi, J.
  43. %T A Kinetic Framework for Computational Geometry
  44. %J Proc. of the 24'th Annual IEEE Conference on the Foundations of Computer Science
  45. %C Tucson
  46. %P 100-111
  47. %D 1983
  48.