Graphviz  2.41.20170921.2350
voronoi.c
Go to the documentation of this file.
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 
22 void 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 }
Site * bottomsite
Definition: site.c:20
Edge * ELedge
Definition: hedges.h:28
int PQempty(void)
Definition: heap.c:80
Site * rightreg(Halfedge *he)
Definition: hedges.c:258
void ELinsert(Halfedge *lb, Halfedge *new)
Definition: hedges.c:160
void voronoi(int triangulate, Site *(*nextsite)(void))
Definition: voronoi.c:22
double y
Definition: geometry.h:27
void PQdelete(Halfedge *he)
Definition: heap.c:64
char ELpm
Definition: hedges.h:30
void siteinit()
Definition: site.c:25
Definition: site.h:26
Halfedge * HEcreate(Edge *e, char pm)
Definition: hedges.c:147
Site * hintersect(Halfedge *el1, Halfedge *el2)
Definition: hedges.c:56
Halfedge * ELrightend
Definition: hedges.c:21
Definition: edges.h:25
Halfedge * ELleftend
Definition: hedges.c:21
Halfedge * ELright(Halfedge *he)
Definition: hedges.c:240
void PQinitialize(void)
Definition: heap.c:114
double x
Definition: geometry.h:27
void PQinsert(Halfedge *he, Site *v, double offset)
Definition: heap.c:45
#define le
Definition: edges.h:32
void ELdelete(Halfedge *he)
Definition: hedges.c:232
Halfedge * ELleftbnd(Point *p)
Definition: hedges.c:186
Point PQ_min(void)
Definition: heap.c:86
#define re
Definition: edges.h:33
Halfedge * PQextractmin(void)
Definition: heap.c:98
Site * leftreg(Halfedge *he)
Definition: hedges.c:251
Halfedge * ELleft(Halfedge *he)
Definition: hedges.c:245
#define NULL
Definition: logic.h:39
Edge * gvbisect(Site *s1, Site *s2)
Definition: edges.c:32
Site * vertex
Definition: hedges.h:31
void deref(Site *v)
Definition: site.c:63
#define top(sp)
Definition: stack.h:35
void clip_line(Edge *e)
Definition: edges.c:79
Definition: geometry.h:26
void ELinitialize()
Definition: hedges.c:35
void endpoint(Edge *e, int lr, Site *s)
Definition: edges.c:199
double dist(Site *s, Site *t)
Definition: site.c:41
void edgeinit()
Definition: edges.c:26
Point coord
Definition: site.h:27
void makevertex(Site *v)
Definition: site.c:53