home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / graphics / 13381 < prev    next >
Encoding:
Text File  |  1993-01-05  |  1.0 KB  |  24 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!news.smith.edu!orourke
  3. From: orourke@sophia.smith.edu (Joseph O'Rourke)
  4. Subject: Re: Polygon-polygon intersection
  5. Message-ID: <1993Jan5.015648.19923@sophia.smith.edu>
  6. Organization: Smith College, Northampton, MA, US
  7. References: <7418@tivoli.UUCP> <1993Jan4.195436.2889@cis.uab.edu> <1iadoeINN2hj@life.ai.mit.edu>
  8. Date: Tue, 5 Jan 1993 01:56:48 GMT
  9. Lines: 13
  10.  
  11. In article <1iadoeINN2hj@life.ai.mit.edu> sundar@ai.mit.edu writes:
  12. >|> In article <7418@tivoli.UUCP> twb@tivoli.com (Tom Bereiter) writes:
  13.  
  14. >|> >I'm looking for an efficient test for whether two 2D polygons intersect.
  15.  
  16. >This seems to come up repeatedly, and it DOES have a simple answer,
  17. >Polygon intersection can be reduced to point in polygon in linear time. 
  18. >Basically convolve A & B, [etc.]
  19.  
  20.     This does come up repeatedly.  Last time it did I pointed out
  21. that the Minkowski sum (convolution) can be computed in linear time
  22. on for two *convex* polygons.  For two arbitrary simple polygons of
  23. n vertices each, there are examples that require n^4 time!
  24.