Subversion Repositories wimsdev

Rev

Blame | Last modification | View Log | RSS feed

  1.  
  2. /*** EDGELIST.C ***/
  3.  
  4. #include "vdefs.h"
  5.  
  6. int ELhashsize ;
  7. Site * bottomsite ;
  8. Freelist hfl ;
  9. Halfedge * ELleftend, * ELrightend, **ELhash ;
  10.  
  11. int ntry, totalsearch ;
  12.  
  13. void
  14. ELinitialize(void)
  15.     {
  16.     int i ;
  17.  
  18.     freeinit(&hfl, sizeof(Halfedge)) ;
  19.     ELhashsize = 2 * sqrt_nsites ;
  20.     ELhash = (Halfedge **)myalloc( sizeof(*ELhash) * ELhashsize) ;
  21.     for (i = 0  ; i < ELhashsize  ; i++)
  22.         {
  23.         ELhash[i] = (Halfedge *)NULL ;
  24.         }
  25.     ELleftend = HEcreate((Edge *)NULL, 0) ;
  26.     ELrightend = HEcreate((Edge *)NULL, 0) ;
  27.     ELleftend->ELleft = (Halfedge *)NULL ;
  28.     ELleftend->ELright = ELrightend ;
  29.     ELrightend->ELleft = ELleftend ;
  30.     ELrightend->ELright = (Halfedge *)NULL ;
  31.     ELhash[0] = ELleftend ;
  32.     ELhash[ELhashsize-1] = ELrightend ;
  33.     }
  34.  
  35. Halfedge *
  36. HEcreate(Edge * e, int pm)
  37.     {
  38.     Halfedge * answer ;
  39.  
  40.     answer = (Halfedge *)getfree(&hfl) ;
  41.     answer->ELedge = e ;
  42.     answer->ELpm = pm ;
  43.     answer->PQnext = (Halfedge *)NULL ;
  44.     answer->vertex = (Site *)NULL ;
  45.     answer->ELrefcnt = 0 ;
  46.     return (answer) ;
  47.     }
  48.  
  49. void
  50. ELinsert(Halfedge * lb, Halfedge * new)
  51.     {
  52.     new->ELleft = lb ;
  53.     new->ELright = lb->ELright ;
  54.     (lb->ELright)->ELleft = new ;
  55.     lb->ELright = new ;
  56.     }
  57.  
  58. /* Get entry from hash table, pruning any deleted nodes */
  59.  
  60. Halfedge *
  61. ELgethash(int b)
  62.     {
  63.     Halfedge * he ;
  64.  
  65.     if ((b < 0) || (b >= ELhashsize))
  66.         {
  67.         return ((Halfedge *)NULL) ;
  68.         }
  69.     he = ELhash[b] ;
  70.     if ((he == (Halfedge *)NULL) || (he->ELedge != (Edge *)DELETED))
  71.         {
  72.         return (he) ;
  73.         }
  74.     /* Hash table points to deleted half edge.  Patch as necessary. */
  75.     ELhash[b] = (Halfedge *)NULL ;
  76.     if ((--(he->ELrefcnt)) == 0)
  77.         {
  78.         makefree((Freenode *)he, (Freelist *)&hfl) ;
  79.         }
  80.     return ((Halfedge *)NULL) ;
  81.     }
  82.  
  83. Halfedge *
  84. ELleftbnd(Point * p)
  85.     {
  86.     int i, bucket ;
  87.     Halfedge * he ;
  88.  
  89.     /* Use hash table to get close to desired halfedge */
  90.     bucket = (p->x - xmin) / deltax * ELhashsize ;
  91.     if (bucket < 0)
  92.         {
  93.         bucket = 0 ;
  94.         }
  95.     if (bucket >= ELhashsize)
  96.         {
  97.         bucket = ELhashsize - 1 ;
  98.         }
  99.     he = ELgethash(bucket) ;
  100.     if  (he == (Halfedge *)NULL)
  101.         {
  102.         for (i = 1 ; 1 ; i++)
  103.             {
  104.             if ((he = ELgethash(bucket-i)) != (Halfedge *)NULL)
  105.                 {
  106.                 break ;
  107.                 }
  108.             if ((he = ELgethash(bucket+i)) != (Halfedge *)NULL)
  109.                 {
  110.                 break ;
  111.                 }
  112.             }
  113.         totalsearch += i ;
  114.         }
  115.     ntry++ ;
  116.     /* Now search linear list of halfedges for the corect one */
  117.     if (he == ELleftend || (he != ELrightend && right_of(he,p)))
  118.         {
  119.         do  {
  120.             he = he->ELright ;
  121.             } while (he != ELrightend && right_of(he,p)) ;
  122.         he = he->ELleft ;
  123.         }
  124.     else
  125.         {
  126.         do  {
  127.             he = he->ELleft ;
  128.             } while (he != ELleftend && !right_of(he,p)) ;
  129.         }
  130.     /*** Update hash table and reference counts ***/
  131.     if ((bucket > 0) && (bucket < ELhashsize-1))
  132.         {
  133.         if (ELhash[bucket] != (Halfedge *)NULL)
  134.             {
  135.             (ELhash[bucket]->ELrefcnt)-- ;
  136.             }
  137.         ELhash[bucket] = he ;
  138.         (ELhash[bucket]->ELrefcnt)++ ;
  139.         }
  140.     return (he) ;
  141.     }
  142.  
  143. /*** This delete routine can't reclaim node, since pointers from hash
  144.  : table may be present.
  145.  ***/
  146.  
  147. void
  148. ELdelete(Halfedge * he)
  149.     {
  150.     (he->ELleft)->ELright = he->ELright ;
  151.     (he->ELright)->ELleft = he->ELleft ;
  152.     he->ELedge = (Edge *)DELETED ;
  153.     }
  154.  
  155. Halfedge *
  156. ELright(Halfedge * he)
  157.     {
  158.     return (he->ELright) ;
  159.     }
  160.  
  161. Halfedge *
  162. ELleft(Halfedge * he)
  163.     {
  164.     return (he->ELleft) ;
  165.     }
  166.  
  167. Site *
  168. leftreg(Halfedge * he)
  169.     {
  170.     if (he->ELedge == (Edge *)NULL)
  171.         {
  172.         return(bottomsite) ;
  173.         }
  174.     return (he->ELpm == le ? he->ELedge->reg[le] :
  175.         he->ELedge->reg[re]) ;
  176.     }
  177.  
  178. Site *
  179. rightreg(Halfedge * he)
  180.     {
  181.     if (he->ELedge == (Edge *)NULL)
  182.         {
  183.         return(bottomsite) ;
  184.         }
  185.     return (he->ELpm == le ? he->ELedge->reg[re] :
  186.         he->ELedge->reg[le]) ;
  187.     }
  188.  
  189.