Back to index

wims  3.65+svn20090927
voronoi.c
Go to the documentation of this file.
00001 
00002 /*** VORONOI.C ***/
00003 
00004 #include "vdefs.h"
00005 
00006 extern Site * bottomsite ;
00007 extern Halfedge * ELleftend, * ELrightend ;
00008 
00009 /*** implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax,
00010  : deltax, deltay (can all be estimates).
00011  : Performance suffers if they are wrong; better to make nsites,
00012  : deltax, and deltay too big than too small.  (?)
00013  ***/
00014 
00015 void
00016 voronoi(Site *(*nextsite)(void))
00017     {
00018     Site * newsite, * bot, * top, * temp, * p, * v ;
00019     Point newintstar ;
00020     int pm ;
00021     Halfedge * lbnd, * rbnd, * llbnd, * rrbnd, * bisector ;
00022     Edge * e ;
00023 
00024     PQinitialize() ;
00025     bottomsite = (*nextsite)() ;
00026     out_site(bottomsite) ;
00027     ELinitialize() ;
00028     newsite = (*nextsite)() ;
00029     while (1)
00030         {
00031         if(!PQempty())
00032             {
00033             newintstar = PQ_min() ;
00034             }
00035         if (newsite != (Site *)NULL && (PQempty()
00036             || newsite -> coord.y < newintstar.y
00037             || (newsite->coord.y == newintstar.y
00038             && newsite->coord.x < newintstar.x))) {/* new site is
00039 smallest */
00040             {
00041             out_site(newsite) ;
00042             }
00043         lbnd = ELleftbnd(&(newsite->coord)) ;
00044         rbnd = ELright(lbnd) ;
00045         bot = rightreg(lbnd) ;
00046         e = bisect(bot, newsite) ;
00047         bisector = HEcreate(e, le) ;
00048         ELinsert(lbnd, bisector) ;
00049         p = intersect(lbnd, bisector) ;
00050         if (p != (Site *)NULL)
00051             {
00052             PQdelete(lbnd) ;
00053             PQinsert(lbnd, p, dist(p,newsite)) ;
00054             }
00055         lbnd = bisector ;
00056         bisector = HEcreate(e, re) ;
00057         ELinsert(lbnd, bisector) ;
00058         p = intersect(bisector, rbnd) ;
00059         if (p != (Site *)NULL)
00060             {
00061             PQinsert(bisector, p, dist(p,newsite)) ;
00062             }
00063         newsite = (*nextsite)() ;
00064         }
00065     else if (!PQempty())   /* intersection is smallest */
00066             {
00067             lbnd = PQextractmin() ;
00068             llbnd = ELleft(lbnd) ;
00069             rbnd = ELright(lbnd) ;
00070             rrbnd = ELright(rbnd) ;
00071             bot = leftreg(lbnd) ;
00072             top = rightreg(rbnd) ;
00073             out_triple(bot, top, rightreg(lbnd)) ;
00074             v = lbnd->vertex ;
00075             makevertex(v) ;
00076             endpoint(lbnd->ELedge, lbnd->ELpm, v);
00077             endpoint(rbnd->ELedge, rbnd->ELpm, v) ;
00078             ELdelete(lbnd) ;
00079             PQdelete(rbnd) ;
00080             ELdelete(rbnd) ;
00081             pm = le ;
00082             if (bot->coord.y > top->coord.y)
00083                 {
00084                 temp = bot ;
00085                 bot = top ;
00086                 top = temp ;
00087                 pm = re ;
00088                 }
00089             e = bisect(bot, top) ;
00090             bisector = HEcreate(e, pm) ;
00091             ELinsert(llbnd, bisector) ;
00092             endpoint(e, re-pm, v) ;
00093             deref(v) ;
00094             p = intersect(llbnd, bisector) ;
00095             if (p  != (Site *) NULL)
00096                 {
00097                 PQdelete(llbnd) ;
00098                 PQinsert(llbnd, p, dist(p,bot)) ;
00099                 }
00100             p = intersect(bisector, rrbnd) ;
00101             if (p != (Site *) NULL)
00102                 {
00103                 PQinsert(bisector, p, dist(p,bot)) ;
00104                 }
00105             }
00106         else
00107             {
00108             break ;
00109             }
00110         }
00111 
00112     for( lbnd = ELright(ELleftend) ;
00113          lbnd != ELrightend ;
00114          lbnd = ELright(lbnd))
00115         {
00116         e = lbnd->ELedge ;
00117         out_ep(e) ;
00118         }
00119     }
00120