home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 12111 < prev    next >
Encoding:
Internet Message Format  |  1992-11-19  |  1.9 KB
  1. Path: sparky!uunet!olivea!charnel!sifon!thunder.mcrcim.mcgill.edu!snorkelwacker.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 (or point) within an arbitrary polygon
  5. Message-ID: <1egv39INNj29@life.ai.mit.edu>
  6. Date: 19 Nov 92 20:57:13 GMT
  7. References: <HINKER.92Nov19081251@cocker.acl.lanl.gov>
  8. Sender: sundar@fiber-one (Sundar Narasimhan)
  9. Reply-To: sundar@ai.mit.edu
  10. Organization: MIT Artificial Intelligence Laboratory
  11. Lines: 23
  12. NNTP-Posting-Host: fiber-one.ai.mit.edu
  13.  
  14. In article <HINKER.92Nov19081251@cocker.acl.lanl.gov>, hinker@acl.lanl.gov (Paul J. Hinker) writes:
  15. |>    I have Polygon1 and Polygon2 described by their respective vertice
  16. |> lists and bounding boxes and I would like to find out whether or not
  17. |> Polygon1 *contains* Polygon2.  Nothing else is known about either
  18. |> polygon.
  19. This problem (like the polygon intersection problem) can be solved
  20. by computing the convolution of the two polygons -- for which linear
  21. time algorithms exist in the plane. 
  22.  
  23. Let's say you have polygon A, B. First let's consider determining
  24. if A intersects B. To do this imagine shrinking B to a point, and growing A
  25. by the similar amount. Now if the point representing B is in the 
  26. grown polygon GO_B(A) (read that as "grown obstacle A relative to B),
  27. then they must intersect. What do I mean by "growing A by a similar amount"?
  28. I mean that A is replaced by the convolution of the two polygons A and
  29. -B (negated copy of B where every vertex V_i in B has been replaced by -V_i).
  30. Thus queries about intersection can be reduced to the point in polygon
  31. problem. 
  32.  
  33. Your containment problem is essentially the same. If you consider
  34. the complement of A, your problem is deciding if B intersects complement of
  35. A. Note that generating complements is extremely easy (just switch
  36. the signs of edge-normal information - or change ccw polygons to cw ones).
  37.