home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / os / msdos / programm / 9040 < prev    next >
Encoding:
Internet Message Format  |  1992-09-03  |  1.7 KB
  1. Path: sparky!uunet!usc!sol.ctr.columbia.edu!destroyer!ubc-cs!mala.bc.ca!epp
  2. From: epp@mala.bc.ca (Lorne Epp)
  3. Newsgroups: comp.os.msdos.programmer
  4. Subject: Re: Algorithm for ordering vertices of a polygon
  5. Message-ID: <1992Sep3.175519.735@mala.bc.ca>
  6. Date: 3 Sep 92 17:55:19 -0700
  7. References: <1992Sep3.194209.10620@athena.mit.edu>
  8. Organization: Malaspina College
  9. Lines: 45
  10.  
  11. In article <1992Sep3.194209.10620@athena.mit.edu>, gleung@athena.mit.edu (Gilbert Leung) writes:
  12. >     I have a polygon with known vertices, but these points are
  13. > arranged in random order.  I need an algorithm to put these points
  14. > in an order such that I can trace the perimeter of this polygon.
  15. > 
  16.  
  17. It can't be done in general.  Look at these points:
  18.  
  19.         *   *     
  20.   
  21.       *   *
  22.   
  23.         *   *
  24.    
  25. You could connect them like this:
  26.  
  27.         *---*     
  28.        /    |
  29.       *   * |
  30.        \ / \|
  31.         *   *
  32.  
  33. or like this:
  34.  
  35.         *   *     
  36.        / \ /|
  37.       *   * |
  38.        \    |
  39.         *---*
  40.  
  41. There are more possibilities, even without allowing edges to cross.
  42.  
  43. For polygons with only 3 vertices there is no problem.  If you allow 
  44. only convex polygons you should be able to do it as well (sorry, I
  45. don't have an algorithm handy).
  46.  
  47. > Note that this arbitrary polygon can be concave and weird-shaped,
  48. > but it is simple enough that there is only ONE way to connect all
  49. > these points to form a polygon.
  50.  
  51. The only way I can see for there to be only one way to connect the
  52. points is if the polygon is a triangle.  In that case it doesn't matter
  53. in what order you connect the dots.
  54. ----------------------------------------------------------------------
  55. Lorne Epp                                               epp@mala.bc.ca
  56.