Subversion Repositories wimsdev

Rev

Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  1.  
  2. /*** VORONOI.C ***/
  3.  
  4. #include "vdefs.h"
  5.  
  6. extern Site * bottomsite ;
  7. extern Halfedge * ELleftend, * ELrightend ;
  8.  
  9. /*** implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax,
  10.  : deltax, deltay (can all be estimates).
  11.  : Performance suffers if they are wrong; better to make nsites,
  12.  : deltax, and deltay too big than too small.  (?)
  13.  ***/
  14.  
  15. void
  16. voronoi(Site *(*nextsite)(void))
  17.     {
  18.     Site * newsite, * bot, * top, * temp, * p, * v ;
  19.     Point newintstar ;
  20.     int pm ;
  21.     Halfedge * lbnd, * rbnd, * llbnd, * rrbnd, * bisector ;
  22.     Edge * e ;
  23.  
  24.     PQinitialize() ;
  25.     bottomsite = (*nextsite)() ;
  26.     out_site(bottomsite) ;
  27.     ELinitialize() ;
  28.     newsite = (*nextsite)() ;
  29.     while (1)
  30.         {
  31.         if(!PQempty())
  32.             {
  33.             newintstar = PQ_min() ;
  34.             }
  35.         if (newsite != (Site *)NULL && (PQempty()
  36.             || newsite -> coord.y < newintstar.y
  37.             || (newsite->coord.y == newintstar.y
  38.             && newsite->coord.x < newintstar.x))) {/* new site is
  39. smallest */
  40.             {
  41.             out_site(newsite) ;
  42.             }
  43.         lbnd = ELleftbnd(&(newsite->coord)) ;
  44.         rbnd = ELright(lbnd) ;
  45.         bot = rightreg(lbnd) ;
  46.         e = bisect(bot, newsite) ;
  47.         bisector = HEcreate(e, le) ;
  48.         ELinsert(lbnd, bisector) ;
  49.         p = intersect(lbnd, bisector) ;
  50.         if (p != (Site *)NULL)
  51.             {
  52.             PQdelete(lbnd) ;
  53.             PQinsert(lbnd, p, dist(p,newsite)) ;
  54.             }
  55.         lbnd = bisector ;
  56.         bisector = HEcreate(e, re) ;
  57.         ELinsert(lbnd, bisector) ;
  58.         p = intersect(bisector, rbnd) ;
  59.         if (p != (Site *)NULL)
  60.             {
  61.             PQinsert(bisector, p, dist(p,newsite)) ;
  62.             }
  63.         newsite = (*nextsite)() ;
  64.         }
  65.     else if (!PQempty())   /* intersection is smallest */
  66.             {
  67.             lbnd = PQextractmin() ;
  68.             llbnd = ELleft(lbnd) ;
  69.             rbnd = ELright(lbnd) ;
  70.             rrbnd = ELright(rbnd) ;
  71.             bot = leftreg(lbnd) ;
  72.             top = rightreg(rbnd) ;
  73.             out_triple(bot, top, rightreg(lbnd)) ;
  74.             v = lbnd->vertex ;
  75.             makevertex(v) ;
  76.             endpoint(lbnd->ELedge, lbnd->ELpm, v);
  77.             endpoint(rbnd->ELedge, rbnd->ELpm, v) ;
  78.             ELdelete(lbnd) ;
  79.             PQdelete(rbnd) ;
  80.             ELdelete(rbnd) ;
  81.             pm = le ;
  82.             if (bot->coord.y > top->coord.y)
  83.                 {
  84.                 temp = bot ;
  85.                 bot = top ;
  86.                 top = temp ;
  87.                 pm = re ;
  88.                 }
  89.             e = bisect(bot, top) ;
  90.             bisector = HEcreate(e, pm) ;
  91.             ELinsert(llbnd, bisector) ;
  92.             endpoint(e, re-pm, v) ;
  93.             deref(v) ;
  94.             p = intersect(llbnd, bisector) ;
  95.             if (p  != (Site *) NULL)
  96.                 {
  97.                 PQdelete(llbnd) ;
  98.                 PQinsert(llbnd, p, dist(p,bot)) ;
  99.                 }
  100.             p = intersect(bisector, rrbnd) ;
  101.             if (p != (Site *) NULL)
  102.                 {
  103.                 PQinsert(bisector, p, dist(p,bot)) ;
  104.                 }
  105.             }
  106.         else
  107.             {
  108.             break ;
  109.             }
  110.         }
  111.  
  112.     for( lbnd = ELright(ELleftend) ;
  113.          lbnd != ELrightend ;
  114.          lbnd = ELright(lbnd))
  115.         {
  116.         e = lbnd->ELedge ;
  117.         out_ep(e) ;
  118.         }
  119.     }
  120.  
  121.