home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 2 / LSD and 17bit Compendium Deluxe - Volume II.iso / a / prog / cprog / voronoi.lha / voronoi.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-19  |  2.3 KB  |  97 lines
  1. #
  2. #include "defs.h"
  3.  
  4.  
  5. /* implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax,
  6.    deltax, deltay (can all be estimates).
  7.    Performance suffers if they are wrong; better to make nsites,
  8.    deltax, and deltay too big than too small.  (?) */
  9.  
  10. voronoi(triangulate, nextsite)
  11. int triangulate;
  12. struct Site *(*nextsite)();
  13. {
  14. struct Site *newsite, *bot, *top, *temp, *p;
  15. struct Site *v;
  16. struct Point newintstar;
  17. int pm;
  18. struct Halfedge *lbnd, *rbnd, *llbnd, *rrbnd, *bisector;
  19. struct Edge *e;
  20.  
  21.  
  22. PQinitialize();
  23. bottomsite = (*nextsite)();
  24. out_site(bottomsite);
  25. ELinitialize();
  26.  
  27. newsite = (*nextsite)();
  28. while(1)
  29. {
  30.     if(!PQempty()) newintstar = PQ_min();
  31.  
  32.     if (newsite != (struct Site *)NULL 
  33.        && (PQempty() 
  34.          || newsite -> coord.y < newintstar.y
  35.           || (newsite->coord.y == newintstar.y 
  36.              && newsite->coord.x < newintstar.x)))
  37.     {/* new site is smallest */
  38.         out_site(newsite);
  39.         lbnd = ELleftbnd(&(newsite->coord));
  40.         rbnd = ELright(lbnd);
  41.         bot = rightreg(lbnd);
  42.         e = bisect(bot, newsite);
  43.         bisector = HEcreate(e, le);
  44.         ELinsert(lbnd, bisector);
  45.         if ((p = intersect(lbnd, bisector)) != (struct Site *) NULL) 
  46.         {    PQdelete(lbnd);
  47.             PQinsert(lbnd, p, dist(p,newsite));
  48.         };
  49.         lbnd = bisector;
  50.         bisector = HEcreate(e, re);
  51.         ELinsert(lbnd, bisector);
  52.         if ((p = intersect(bisector, rbnd)) != (struct Site *) NULL)
  53.         {    PQinsert(bisector, p, dist(p,newsite));    
  54.         };
  55.         newsite = (*nextsite)();    
  56.     }
  57.     else if (!PQempty()) 
  58.     /* intersection is smallest */
  59.     {    lbnd = PQextractmin();
  60.         llbnd = ELleft(lbnd);
  61.         rbnd = ELright(lbnd);
  62.         rrbnd = ELright(rbnd);
  63.         bot = leftreg(lbnd);
  64.         top = rightreg(rbnd);
  65.         out_triple(bot, top, rightreg(lbnd));
  66.         v = lbnd->vertex;
  67.         makevertex(v);
  68.         endpoint(lbnd->ELedge,lbnd->ELpm,v);
  69.         endpoint(rbnd->ELedge,rbnd->ELpm,v);
  70.         ELdelete(lbnd); 
  71.         PQdelete(rbnd);
  72.         ELdelete(rbnd); 
  73.         pm = le;
  74.         if (bot->coord.y > top->coord.y)
  75.         {    temp = bot; bot = top; top = temp; pm = re;}
  76.         e = bisect(bot, top);
  77.         bisector = HEcreate(e, pm);
  78.         ELinsert(llbnd, bisector);
  79.         endpoint(e, re-pm, v);
  80.         deref(v);
  81.         if((p = intersect(llbnd, bisector)) != (struct Site *) NULL)
  82.         {    PQdelete(llbnd);
  83.             PQinsert(llbnd, p, dist(p,bot));
  84.         };
  85.         if ((p = intersect(bisector, rrbnd)) != (struct Site *) NULL)
  86.         {    PQinsert(bisector, p, dist(p,bot));
  87.         };
  88.     }
  89.     else break;
  90. };
  91.  
  92. for(lbnd=ELright(ELleftend); lbnd != ELrightend; lbnd=ELright(lbnd))
  93.     {    e = lbnd -> ELedge;
  94.         out_ep(e);
  95.     };
  96. }
  97.