home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9490 < prev    next >
Encoding:
Text File  |  1992-07-24  |  3.3 KB  |  76 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!pilchuck!fnx!sgihbtn!wangl
  3. From: wangl@sierra.com (Larry Wang)
  4. Subject: Find all polygon?
  5. Message-ID: <wangl.711931119@sierra.com>
  6. Sender: news@sierra.com
  7. Nntp-Posting-Host: grumpy
  8. Organization: Sierra Geophysics Inc.,  Kirkland, Wa
  9. Date: Thu, 23 Jul 1992 22:38:39 GMT
  10. Lines: 64
  11.  
  12.     A method to find all polygons which do not contain any other points within
  13. a polygon for graphs like the following one:
  14.  
  15.  
  16.             v.....................................................v
  17.  
  18.  
  19.  
  20.            v.............v.....................v.................v
  21.                         .                       .
  22.                        .                         .
  23.                       .                           .
  24.                      .                             .
  25.                     .                               .
  26.                    v..............v..................v
  27.                   .               .                    .
  28.                  .                .                     .
  29.                 .                 .                      .
  30.                .                  v.......................v.
  31.               .                  .                         .
  32.              v                  .                           .
  33.                                .                             .
  34.                               .                               .
  35.                              .                                 .
  36.                             v                                   .
  37.                                                                  .
  38.                                                                   v
  39.  
  40. v = vertex
  41.  
  42. The finished graph should like this:
  43.  
  44.  
  45.          v.......................................................v
  46.           x                                                      x
  47.           x                       1                              x
  48.           x                                                     x
  49.           v..............v.....................v................v
  50.            x            .                       .               x
  51.            x           .                         .              x
  52.            x   2      .            3              .      4      x
  53.            x         .                             .            x
  54.            x        .                               .           x
  55.            x       v..............v..................v          x
  56.            x      .               .                    .        x
  57.            x     .                .         6           .       x
  58.            x    .                 .                      .      x
  59.            x   .                  v.......................v     x
  60.            x  .      7           .                         .    x
  61.             v                   .                           .   x
  62.               x                .                            .   x
  63.                 x             .             8                .  x
  64.                   x          .                                . x
  65.                     x       .                                 . x
  66.                        x   .                                   .x
  67.                          v x x x x x xx x x x x xx x  xx x x x xv 
  68.  
  69.  
  70. 1, 2, ..., 8 are the polygons found.
  71. --
  72.     Gary Beckman            
  73.     Unix Systems Manager
  74.     Sierra Geophysics    
  75.     11255 Kirkland Way
  76.