source: trunk/src2/voronoi/voronoi.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: 3.3 KB
Line 
1
2/*** VORONOI.C ***/
3
4#include "vdefs.h"
5
6extern Site * bottomsite ;
7extern Halfedge * ELleftend, * ELrightend ;
8
9/*** implicit parameters: nsites, sqrt_nsites, xmin, xmax, ymin, ymax,
10 : deltax, deltay (can all be estimates).
11 : Performance suffers if they are wrong; better to make nsites,
12 : deltax, and deltay too big than too small.  (?)
13 ***/
14
15void
16voronoi(Site *(*nextsite)(void))
17    {
18    Site * newsite, * bot, * top, * temp, * p, * v ;
19    Point newintstar ;
20    int pm ;
21    Halfedge * lbnd, * rbnd, * llbnd, * rrbnd, * bisector ;
22    Edge * e ;
23
24    PQinitialize() ;
25    bottomsite = (*nextsite)() ;
26    out_site(bottomsite) ;
27    ELinitialize() ;
28    newsite = (*nextsite)() ;
29    while (1)
30        {
31        if(!PQempty())
32            {
33            newintstar = PQ_min() ;
34            }
35        if (newsite != (Site *)NULL && (PQempty()
36            || newsite -> coord.y < newintstar.y
37            || (newsite->coord.y == newintstar.y
38            && newsite->coord.x < newintstar.x))) {/* new site is
39smallest */
40            {
41            out_site(newsite) ;
42            }
43        lbnd = ELleftbnd(&(newsite->coord)) ;
44        rbnd = ELright(lbnd) ;
45        bot = rightreg(lbnd) ;
46        e = bisect(bot, newsite) ;
47        bisector = HEcreate(e, le) ;
48        ELinsert(lbnd, bisector) ;
49        p = intersect(lbnd, bisector) ;
50        if (p != (Site *)NULL)
51            {
52            PQdelete(lbnd) ;
53            PQinsert(lbnd, p, dist(p,newsite)) ;
54            }
55        lbnd = bisector ;
56        bisector = HEcreate(e, re) ;
57        ELinsert(lbnd, bisector) ;
58        p = intersect(bisector, rbnd) ;
59        if (p != (Site *)NULL)
60            {
61            PQinsert(bisector, p, dist(p,newsite)) ;
62            }
63        newsite = (*nextsite)() ;
64        }
65    else if (!PQempty())   /* intersection is smallest */
66            {
67            lbnd = PQextractmin() ;
68            llbnd = ELleft(lbnd) ;
69            rbnd = ELright(lbnd) ;
70            rrbnd = ELright(rbnd) ;
71            bot = leftreg(lbnd) ;
72            top = rightreg(rbnd) ;
73            out_triple(bot, top, rightreg(lbnd)) ;
74            v = lbnd->vertex ;
75            makevertex(v) ;
76            endpoint(lbnd->ELedge, lbnd->ELpm, v);
77            endpoint(rbnd->ELedge, rbnd->ELpm, v) ;
78            ELdelete(lbnd) ;
79            PQdelete(rbnd) ;
80            ELdelete(rbnd) ;
81            pm = le ;
82            if (bot->coord.y > top->coord.y)
83                {
84                temp = bot ;
85                bot = top ;
86                top = temp ;
87                pm = re ;
88                }
89            e = bisect(bot, top) ;
90            bisector = HEcreate(e, pm) ;
91            ELinsert(llbnd, bisector) ;
92            endpoint(e, re-pm, v) ;
93            deref(v) ;
94            p = intersect(llbnd, bisector) ;
95            if (p  != (Site *) NULL)
96                {
97                PQdelete(llbnd) ;
98                PQinsert(llbnd, p, dist(p,bot)) ;
99                }
100            p = intersect(bisector, rrbnd) ;
101            if (p != (Site *) NULL)
102                {
103                PQinsert(bisector, p, dist(p,bot)) ;
104                }
105            }
106        else
107            {
108            break ;
109            }
110        }
111
112    for( lbnd = ELright(ELleftend) ;
113         lbnd != ELrightend ;
114         lbnd = ELright(lbnd))
115        {
116        e = lbnd->ELedge ;
117        out_ep(e) ;
118        }
119    }
120
Note: See TracBrowser for help on using the repository browser.