source: trunk/src2/voronoi/edgelist.c @ 666

Last change on this file since 666 was 666, checked in by mmc, 17 years ago

Added voronoi code, which is currently used by the nanovis server
to generate triangular meshes for point clouds.

File size: 4.1 KB
Line 
1
2/*** EDGELIST.C ***/
3
4#include "vdefs.h"
5
6int ELhashsize ;
7Site * bottomsite ;
8Freelist hfl ;
9Halfedge * ELleftend, * ELrightend, **ELhash ;
10
11int ntry, totalsearch ;
12
13void
14ELinitialize(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
35Halfedge *
36HEcreate(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
49void
50ELinsert(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
60Halfedge *
61ELgethash(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
83Halfedge *
84ELleftbnd(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
147void
148ELdelete(Halfedge * he)
149    {
150    (he->ELleft)->ELright = he->ELright ;
151    (he->ELright)->ELleft = he->ELleft ;
152    he->ELedge = (Edge *)DELETED ;
153    }
154
155Halfedge *
156ELright(Halfedge * he)
157    {
158    return (he->ELright) ;
159    }
160
161Halfedge *
162ELleft(Halfedge * he)
163    {
164    return (he->ELleft) ;
165    }
166
167Site *
168leftreg(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
178Site *
179rightreg(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
Note: See TracBrowser for help on using the repository browser.