home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / CH_6.1 / XVOR / VOR.C < prev    next >
Encoding:
C/C++ Source or Header  |  1999-09-11  |  3.8 KB  |  143 lines
  1. /* 
  2.  * vor.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9. /*
  10.  * VOR.C
  11.  *
  12.  */
  13.  
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include <math.h>
  17. #include "vor.h"
  18.  
  19. #undef    DEBUG_VOR
  20.  
  21.  
  22. /*
  23.  * voronoi()
  24.  *   DESCRIPTION:
  25.  *     voronoi analysis on a site
  26.  *      implicit parameters: 
  27.  *           nsites, sqrt_nsites, 
  28.  *           xmin, xmax, ymin, ymax, deltax, deltay (can all be estimates).
  29.  *      performance suffers if they are wrong; 
  30.  *      better to make nsites, deltax, and deltay too big than too small.
  31.  *   ARGUMENTS:
  32.  *     nextsite: site on which to do voronoi analysis (struct Site *)
  33.  *     imgIO: image for drawing (Image *)
  34.  *     value: grayscale value for drawing (int)
  35.  *   RETURN VALUE:
  36.  *     none
  37.  */
  38.  
  39. void
  40. voronoi (nextsite, imgIO, value)
  41.      struct Site *(*nextsite) ();
  42.      Image *imgIO;
  43.      int value;
  44. {
  45.   struct Site *newsite, *bot, *top, *temp, *p;
  46.   struct Site *v;
  47.   struct Point newintstar;
  48.   int pm;
  49.   struct Halfedge *lbnd, *rbnd, *llbnd, *rrbnd, *bisector;
  50.   struct Edge *e;
  51.  
  52.  
  53. #ifdef DEBUG_VOR
  54.   printf ("\n...VORONOI:\n");
  55.   printf ("   parameters: nsites: %4d\n", nsites);
  56.   printf ("   extrema: %f %f %f %f\n", xmin, xmax, ymin, ymax);
  57.   printf ("delx, dely: %f %f\n", deltax, deltay);
  58. #endif
  59.  
  60.   PQinitialize ();
  61.   bottomsite = (struct Site *) (*nextsite) ();
  62.   out_site (bottomsite, imgIO, value);
  63.   ELinitialize ();
  64.  
  65.   newsite = (struct Site *) (*nextsite) ();
  66.   while (1) {
  67. #ifdef DEBUG_VOR
  68.     printf ("...VORONOI: processing site %f %f\n",
  69.             newsite->coord.x, newsite->coord.y);
  70. #endif
  71.     if (PQempty () == 0)
  72.       newintstar = PQ_min ();
  73.  
  74.     if ((newsite != (struct Site *) NULL)
  75.         && (PQempty ()
  76.             || newsite->coord.y < newintstar.y
  77.             || (newsite->coord.y == newintstar.y
  78.                 && newsite->coord.x < newintstar.x))) {  /* new site is smallest */
  79.       out_site (newsite, imgIO, value);
  80.       lbnd = ELleftbnd (&(newsite->coord));
  81.       rbnd = ELright (lbnd);
  82.       bot = rightreg (lbnd);
  83.       e = bisect (bot, newsite, imgIO, value);
  84.       bisector = HEcreate (e, le);
  85.       ELinsert (lbnd, bisector);
  86.       if ((p = intersect (lbnd, bisector)) != (struct Site *) NULL) {
  87.         PQdelete (lbnd);
  88.         PQinsert (lbnd, p, dist (p, newsite));
  89.       }
  90.       lbnd = bisector;
  91.       bisector = HEcreate (e, re);
  92.       ELinsert (lbnd, bisector);
  93.       if ((p = intersect (bisector, rbnd)) != (struct Site *) NULL) {
  94.         PQinsert (bisector, p, dist (p, newsite));
  95.       }
  96.       newsite = (struct Site *) (*nextsite) ();
  97.     }
  98.     else if (!PQempty ()) {     /* intersection is smallest */
  99.       lbnd = PQextractmin ();
  100.       llbnd = ELleft (lbnd);
  101.       rbnd = ELright (lbnd);
  102.       rrbnd = ELright (rbnd);
  103.       bot = leftreg (lbnd);
  104.       top = rightreg (rbnd);
  105.       out_triple (bot, top, rightreg (lbnd));
  106.       v = lbnd->vertex;
  107.       makevertex (v);
  108.       endpoint (lbnd->ELedge, lbnd->ELpm, v, imgIO, value);
  109.       endpoint (rbnd->ELedge, rbnd->ELpm, v, imgIO, value);
  110.       ELdelete (lbnd);
  111.       PQdelete (rbnd);
  112.       ELdelete (rbnd);
  113.       pm = le;
  114.       if (bot->coord.y > top->coord.y) {
  115.         temp = bot;
  116.         bot = top;
  117.         top = temp;
  118.         pm = re;
  119.       }
  120.       e = bisect (bot, top, imgIO, value);
  121.       bisector = HEcreate (e, pm);
  122.       ELinsert (llbnd, bisector);
  123.       endpoint (e, re - pm, v, imgIO, value);
  124.       deref (v);
  125.       if ((p = intersect (llbnd, bisector)) != (struct Site *) NULL) {
  126.         PQdelete (llbnd);
  127.         PQinsert (llbnd, p, dist (p, bot));
  128.       }
  129.       if ((p = intersect (bisector, rrbnd)) != (struct Site *) NULL) {
  130.         PQinsert (bisector, p, dist (p, bot));
  131.       }
  132.     }
  133.     else {
  134.       break;
  135.     }
  136.   }
  137.  
  138.   for (lbnd = ELright (ELleftend); lbnd != ELrightend; lbnd = ELright (lbnd)) {
  139.     e = lbnd->ELedge;
  140.     out_ep (e, imgIO, value);
  141.   }
  142. }
  143.