home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / os / msdos / programm / 9050 < prev    next >
Encoding:
Text File  |  1992-09-03  |  1.8 KB  |  63 lines
  1. Nntp-Posting-Host: yrsa.ifi.uio.no
  2. Newsgroups: comp.os.msdos.programmer
  3. Path: sparky!uunet!mcsun!sunic!aun.uninett.no!nuug!ifi.uio.no!espenk
  4. From: espenk@ifi.uio.no (Espen Frimann Koren)
  5. Subject: Re: Algorithm for ordering vertices
  6. Message-ID: <1992Sep4.075841.25885@ifi.uio.no>
  7. Sender: espenk@ifi.uio.no (Espen Frimann Koren)
  8. Organization: Dept. of Informatics, University of Oslo, Norway
  9. Date: Fri, 4 Sep 1992 07:58:41 GMT
  10. Lines: 50
  11. Originator: espenk@yrsa.ifi.uio.no
  12.  
  13.  
  14. In article <1992Sep3.194209.10620@athena.mit.edu> you write:
  15. >     I have a polygon with known vertices, but these points are
  16. > arranged in random order.  I need an algorithm to put these points
  17. > in an order such that I can trace the perimeter of this polygon.
  18. > Note that this arbitrary polygon can be concave and weird-shaped,
  19. > but it is simple enough that there is only ONE way to connect all
  20. > these points to form a polygon.
  21. > 
  22. >     Any help would be greatly appreciated.  Thanks in advance.
  23. > 
  24. > Gilbert
  25. > 
  26.  
  27.  
  28. An arbitrary set of vertices does not always become a polygon. It could
  29. turn up to be a line. What you need to sort, is the EDGES of the polygon.
  30. Then you can trace the perimeter easy.
  31.  
  32. You represent the egdes on the form (xmin, ymin, xmax, ymax) and if you
  33. sort after these criterias:
  34.  
  35.     ymin, xmin, m  (where m is the elevation of the edge, that is
  36.                         m = (ymax-ymin)/(xmax-xmin))
  37.  
  38. then a polygon like this (the P's are the crosspoints)
  39.  
  40.  
  41.  
  42.  
  43.                 Pp
  44.                p  pp  (4)
  45.                p    pp
  46.          (3)  p       pP
  47.              p         p
  48.             p          p
  49.             p          p
  50.            Ppp        p  (2)
  51.               ppp     p
  52.              (1) ppp  p
  53.                     ppP
  54.  
  55. be sorted after the shown numbering.
  56.  
  57. (This is in fact the way you sort edges if you are going to graphicly fill the
  58.  polygon using scan-conversion)
  59.  
  60. Espen.
  61.  
  62.  
  63.