home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 2 / LSD and 17bit Compendium Deluxe - Volume II.iso / a / prog / cprog / voronoi.lha / edgelist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-19  |  3.4 KB  |  144 lines
  1. #
  2. #include "defs.h"
  3.  
  4. int ntry, totalsearch;
  5.  
  6. ELinitialize()
  7. {
  8. int i;
  9.     freeinit(&hfl, sizeof **ELhash);
  10.     ELhashsize = 2 * sqrt_nsites;
  11.     ELhash = (struct Halfedge **) myalloc ( sizeof *ELhash * ELhashsize);
  12.     for(i=0; i<ELhashsize; i +=1) ELhash[i] = (struct Halfedge *)NULL;
  13.     ELleftend = HEcreate( (struct Edge *)NULL, 0);
  14.     ELrightend = HEcreate( (struct Edge *)NULL, 0);
  15.     ELleftend -> ELleft = (struct Halfedge *)NULL;
  16.     ELleftend -> ELright = ELrightend;
  17.     ELrightend -> ELleft = ELleftend;
  18.     ELrightend -> ELright = (struct Halfedge *)NULL;
  19.     ELhash[0] = ELleftend;
  20.     ELhash[ELhashsize-1] = ELrightend;
  21. }
  22.  
  23.  
  24. struct Halfedge *HEcreate(e, pm)
  25. struct Edge *e;
  26. int pm;
  27. {
  28. struct Halfedge *answer;
  29.     answer = (struct Halfedge *) getfree(&hfl);
  30.     answer -> ELedge = e;
  31.     answer -> ELpm = pm;
  32.     answer -> PQnext = (struct Halfedge *) NULL;
  33.     answer -> vertex = (struct Site *) NULL;
  34.     answer -> ELrefcnt = 0;
  35.     return(answer);
  36. }
  37.  
  38.  
  39. ELinsert(lb, new)
  40. struct    Halfedge *lb, *new;
  41. {
  42.     new -> ELleft = lb;
  43.     new -> ELright = lb -> ELright;
  44.     (lb -> ELright) -> ELleft = new;
  45.     lb -> ELright = new;
  46. }
  47.  
  48. /* Get entry from hash table, pruning any deleted nodes */
  49. struct Halfedge *ELgethash(b)
  50. int b;
  51. {
  52. struct Halfedge *he;
  53.  
  54.     if(b<0 || b>=ELhashsize) return((struct Halfedge *) NULL);
  55.     he = ELhash[b]; 
  56.     if (he == (struct Halfedge *) NULL || 
  57.         he -> ELedge != (struct Edge *) DELETED ) return (he);
  58.  
  59. /* Hash table points to deleted half edge.  Patch as necessary. */
  60.     ELhash[b] = (struct Halfedge *) NULL;
  61.     if ((he -> ELrefcnt -= 1) == 0) makefree(he, &hfl);
  62.     return ((struct Halfedge *) NULL);
  63. }    
  64.  
  65. struct Halfedge *ELleftbnd(p)
  66. struct Point *p;
  67. {
  68. int i, bucket;
  69. struct Halfedge *he;
  70.  
  71. /* Use hash table to get close to desired halfedge */
  72.     bucket = (p->x - xmin)/deltax * ELhashsize;
  73.     if(bucket<0) bucket =0;
  74.     if(bucket>=ELhashsize) bucket = ELhashsize - 1;
  75.     he = ELgethash(bucket);
  76.     if(he == (struct Halfedge *) NULL)
  77.     {   for(i=1; 1 ; i += 1)
  78.         {    if ((he=ELgethash(bucket-i)) != (struct Halfedge *) NULL) break;
  79.         if ((he=ELgethash(bucket+i)) != (struct Halfedge *) NULL) break;
  80.         };
  81.     totalsearch += i;
  82.     };
  83.     ntry += 1;
  84. /* Now search linear list of halfedges for the corect one */
  85.     if (he==ELleftend  || (he != ELrightend && right_of(he,p)))
  86.     {do {he = he -> ELright;} while (he!=ELrightend && right_of(he,p));
  87.      he = he -> ELleft;
  88.     }
  89.     else 
  90.     do {he = he -> ELleft;} while (he!=ELleftend && !right_of(he,p));
  91.  
  92. /* Update hash table and reference counts */
  93.     if(bucket > 0 && bucket <ELhashsize-1)
  94.     {    if(ELhash[bucket] != (struct Halfedge *) NULL) 
  95.             ELhash[bucket] -> ELrefcnt -= 1;
  96.         ELhash[bucket] = he;
  97.         ELhash[bucket] -> ELrefcnt += 1;
  98.     };
  99.     return (he);
  100. }
  101.  
  102.     
  103. /* This delete routine can't reclaim node, since pointers from hash
  104.    table may be present.   */
  105. ELdelete(he)
  106. struct Halfedge *he;
  107. {
  108.     (he -> ELleft) -> ELright = he -> ELright;
  109.     (he -> ELright) -> ELleft = he -> ELleft;
  110.     he -> ELedge = (struct Edge *)DELETED;
  111. }
  112.  
  113.  
  114. struct Halfedge *ELright(he)
  115. struct Halfedge *he;
  116. {
  117.     return (he -> ELright);
  118. }
  119.  
  120. struct Halfedge *ELleft(he)
  121. struct Halfedge *he;
  122. {
  123.     return (he -> ELleft);
  124. }
  125.  
  126.  
  127. struct Site *leftreg(he)
  128. struct Halfedge *he;
  129. {
  130.     if(he -> ELedge == (struct Edge *)NULL) return(bottomsite);
  131.     return( he -> ELpm == le ? 
  132.         he -> ELedge -> reg[le] : he -> ELedge -> reg[re]);
  133. }
  134.  
  135. struct Site *rightreg(he)
  136. struct Halfedge *he;
  137. {
  138.     if(he -> ELedge == (struct Edge *)NULL) return(bottomsite);
  139.     return( he -> ELpm == le ? 
  140.         he -> ELedge -> reg[re] : he -> ELedge -> reg[le]);
  141. }
  142.  
  143.  
  144.