1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#include "mem.h"
15#include "geometry.h"
16#include "edges.h"
17#include "hedges.h"
18#include "heap.h"
19#include "voronoi.h"
20
21
22void voronoi(int triangulate, Site * (*nextsite) (void))
23{
24 Site *newsite, *bot, *top, *temp, *p;
25 Site *v;
26 Point newintstar = {0};
27 char pm;
28 Halfedge *lbnd, *rbnd, *llbnd, *rrbnd, *bisector;
29 Edge *e;
30
31 edgeinit();
32 siteinit();
33 PQinitialize();
34 bottomsite = (*nextsite) ();
35#ifdef STANDALONE
36 out_site(bottomsite);
37#endif
38 ELinitialize();
39
40 newsite = (*nextsite) ();
41 while (1) {
42 if (!PQempty())
43 newintstar = PQ_min();
44
45 if (newsite != (struct Site *) NULL && (PQempty()
46 || newsite->coord.y <
47 newintstar.y
48 || (newsite->coord.y ==
49 newintstar.y
50 && newsite->coord.x <
51 newintstar.x))) {
52 /* new site is smallest */
53#ifdef STANDALONE
54 out_site(newsite);
55#endif
56 lbnd = ELleftbnd(&(newsite->coord));
57 rbnd = ELright(lbnd);
58 bot = rightreg(lbnd);
59 e = gvbisect(bot, newsite);
60 bisector = HEcreate(e, le);
61 ELinsert(lbnd, bisector);
62 if ((p = hintersect(lbnd, bisector)) != (struct Site *) NULL) {
63 PQdelete(lbnd);
64 PQinsert(lbnd, p, dist(p, newsite));
65 }
66 lbnd = bisector;
67 bisector = HEcreate(e, re);
68 ELinsert(lbnd, bisector);
69 if ((p = hintersect(bisector, rbnd)) != (struct Site *) NULL)
70 PQinsert(bisector, p, dist(p, newsite));
71 newsite = (*nextsite) ();
72 } else if (!PQempty()) {
73 /* intersection is smallest */
74 lbnd = PQextractmin();
75 llbnd = ELleft(lbnd);
76 rbnd = ELright(lbnd);
77 rrbnd = ELright(rbnd);
78 bot = leftreg(lbnd);
79 top = rightreg(rbnd);
80#ifdef STANDALONE
81 out_triple(bot, top, rightreg(lbnd));
82#endif
83 v = lbnd->vertex;
84 makevertex(v);
85 endpoint(lbnd->ELedge, lbnd->ELpm, v);
86 endpoint(rbnd->ELedge, rbnd->ELpm, v);
87 ELdelete(lbnd);
88 PQdelete(rbnd);
89 ELdelete(rbnd);
90 pm = le;
91 if (bot->coord.y > top->coord.y) {
92 temp = bot;
93 bot = top;
94 top = temp;
95 pm = re;
96 }
97 e = gvbisect(bot, top);
98 bisector = HEcreate(e, pm);
99 ELinsert(llbnd, bisector);
100 endpoint(e, re - pm, v);
101 deref(v);
102 if ((p = hintersect(llbnd, bisector)) != (struct Site *) NULL) {
103 PQdelete(llbnd);
104 PQinsert(llbnd, p, dist(p, bot));
105 }
106 if ((p = hintersect(bisector, rrbnd)) != (struct Site *) NULL) {
107 PQinsert(bisector, p, dist(p, bot));
108 }
109 } else
110 break;
111 }
112
113 for (lbnd = ELright(ELleftend); lbnd != ELrightend;
114 lbnd = ELright(lbnd)) {
115 e = lbnd->ELedge;
116 clip_line(e);
117#ifdef STANDALONE
118 out_ep(e);
119#endif
120 }
121}
122