home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / graphics / 13493 < prev    next >
Encoding:
Text File  |  1993-01-07  |  1.4 KB  |  41 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!news.univie.ac.at!hp4at!cophos!js
  3. From: js@cophos.co.at (Jodok Schaeffler)
  4. Subject: Polygon with holes
  5. Message-ID: <1993Jan6.135808.6337@cophos.co.at>
  6. Organization: COPHOS Development Team, ZUMtOBEL Licht GmbH, Dornbirn, AUSTRIA
  7. Distribution: comp.graphics
  8. Date: Wed, 6 Jan 1993 13:58:08 GMT
  9. Lines: 30
  10.  
  11. I have a problem with polygons, specifically with the holes
  12. within a polygon. 
  13.  
  14. There are (at least) two ways to specify such a polygon:
  15.  - as a structure of polygons, holes beeing represented
  16.    as polygons within polygons
  17.  - as a closed line, following the edges of the polygon
  18.    and the holes. To connect all holes to the actual polygon,
  19.    the closed line needs to cross the interior of the polygon.
  20.    The closed line comes back to the point where it left the edge 
  21.    at the same position, but with opposite direction.
  22.  
  23. What I am looking for: 
  24.    An algorithm to find a line connecting all
  25.    holes within a polygon.
  26.  
  27. My idea: to construct something like a Voronoi diagramm to find
  28.          the 'minimal spanning tree' of all holes within the 
  29.          polygon.
  30.  
  31. The problem seems similar to the traveling salesman problem, as
  32. I have to find any (not even an 'optimal') connection between
  33. the holes. My problem is to construct a Voronoi diagram from
  34. polygons, not from points.
  35.  
  36. If someone can help me, point me to a direction to go, or
  37. even knows a source for code, I would appreciate this.
  38.  
  39.  
  40. Jodok Schaeffler
  41.