Subversion Repositories wimsdev

Rev

Rev 10 | 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.     newintstar.x = 0; /* gcc -Wall */
  30.     newintstar.y = 0; /* gcc -Wall */
  31.     while (1)
  32.         {
  33.         if(!PQempty())
  34.             {
  35.             newintstar = PQ_min() ;
  36.             }
  37.         if (newsite != (Site *)NULL && (PQempty()
  38.             || newsite -> coord.y < newintstar.y
  39.             || (newsite->coord.y == newintstar.y
  40.             && newsite->coord.x < newintstar.x)))
  41.             {/* new site is smallest */
  42.             out_site(newsite) ;
  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.