Graphviz 14.0.2~dev.20251008.0253
Loading...
Searching...
No Matches
voronoi.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include <neatogen/geometry.h>
12#include <neatogen/edges.h>
13#include <neatogen/hedges.h>
14#include <neatogen/heap.h>
15#include <neatogen/voronoi.h>
16#include <util/gv_math.h>
17#include <util/list.h>
18
19void voronoi(Site *(*nextsite)(void *context), void *context) {
20 Site *newsite, *bot, *top, *p;
21 Site *v;
22 Point newintstar = {0};
23 char pm;
24 Halfedge *lbnd, *rbnd, *llbnd, *rrbnd, *bisector;
25 Edge *e;
26
27 pq_t *pq = PQinitialize();
28 bottomsite = nextsite(context);
29 el_state_t st = {0};
30 ELinitialize(&st);
31
32 newsite = nextsite(context);
33 while (1) {
34 if (!PQempty(pq))
35 newintstar = PQ_min(pq);
36
37 if (newsite != NULL &&
38 (PQempty(pq) || newsite->coord.y < newintstar.y ||
39 (newsite->coord.y ==newintstar.y && newsite->coord.x < newintstar.x))) {
40 /* new site is smallest */
41 lbnd = ELleftbnd(&st, &newsite->coord);
42 rbnd = ELright(lbnd);
43 bot = rightreg(lbnd);
44 e = gvbisect(bot, newsite, &st.allocated);
45 bisector = HEcreate(&st, e, le);
46 ELinsert(lbnd, bisector);
47 if ((p = hintersect(lbnd, bisector, &st.allocated)) != NULL) {
48 PQdelete(pq, lbnd);
49 PQinsert(pq, lbnd, p, ngdist(p, newsite));
50 }
51 lbnd = bisector;
52 bisector = HEcreate(&st, e, re);
53 ELinsert(lbnd, bisector);
54 if ((p = hintersect(bisector, rbnd, &st.allocated)) != NULL)
55 PQinsert(pq, bisector, p, ngdist(p, newsite));
56 newsite = nextsite(context);
57 } else if (!PQempty(pq)) {
58 /* intersection is smallest */
59 lbnd = PQextractmin(pq);
60 llbnd = ELleft(lbnd);
61 rbnd = ELright(lbnd);
62 rrbnd = ELright(rbnd);
63 bot = leftreg(lbnd);
64 top = rightreg(rbnd);
65 v = lbnd->vertex;
66 endpoint(lbnd->ELedge, lbnd->ELpm, v, &st.allocated);
67 endpoint(rbnd->ELedge, rbnd->ELpm, v, &st.allocated);
68 ELdelete(lbnd);
69 PQdelete(pq, rbnd);
70 ELdelete(rbnd);
71 pm = le;
72 if (bot->coord.y > top->coord.y) {
73 SWAP(&bot, &top);
74 pm = re;
75 }
76 e = gvbisect(bot, top, &st.allocated);
77 bisector = HEcreate(&st, e, pm);
78 ELinsert(llbnd, bisector);
79 endpoint(e, re - pm, v, &st.allocated);
80 if ((p = hintersect(llbnd, bisector, &st.allocated)) != NULL) {
81 PQdelete(pq, llbnd);
82 PQinsert(pq, llbnd, p, ngdist(p, bot));
83 }
84 if ((p = hintersect(bisector, rrbnd, &st.allocated)) != NULL) {
85 PQinsert(pq, bisector, p, ngdist(p, bot));
86 }
87 } else
88 break;
89 }
90
91 for (lbnd = ELright(st.leftend); lbnd != st.rightend;
92 lbnd = ELright(lbnd)) {
93 e = lbnd->ELedge;
94 clip_line(e);
95 }
96
97 ELcleanup(&st);
98
99 // `PQcleanup` relies on the number of sites, so should be discarded and
100 // at least every time we use `vAdjust`. See note in adjust.c:cleanup().
101 PQcleanup(pq);
102}
void clip_line(Edge *e)
Definition edges.c:59
void endpoint(Edge *e, int lr, Site *s, arena_t *allocator)
Definition edges.c:175
Edge * gvbisect(Site *s1, Site *s2, arena_t *allocator)
Definition edges.c:21
#define le
Definition edges.h:29
#define re
Definition edges.h:30
node NULL
Definition grammar.y:181
Arithmetic helper functions.
#define SWAP(a, b)
Definition gv_math.h:134
Point PQ_min(pq_t *pq)
Definition heap.c:94
void PQcleanup(pq_t *pq)
Definition heap.c:112
bool PQempty(const pq_t *pq)
Definition heap.c:90
void PQdelete(pq_t *pq, Halfedge *he)
Definition heap.c:77
pq_t * PQinitialize(void)
Definition heap.c:119
Halfedge * PQextractmin(pq_t *pq)
Definition heap.c:105
void PQinsert(pq_t *pq, Halfedge *he, Site *v, double offset)
Definition heap.c:62
Site * hintersect(Halfedge *el1, Halfedge *el2, arena_t *allocator)
Definition hedges.c:43
Halfedge * ELright(Halfedge *he)
Definition hedges.c:226
void ELcleanup(el_state_t *st)
Definition hedges.c:21
void ELinitialize(el_state_t *st)
Definition hedges.c:26
void ELinsert(Halfedge *lb, Halfedge *new)
Definition hedges.c:139
Site * rightreg(Halfedge *he)
Definition hedges.c:244
Halfedge * ELleft(Halfedge *he)
Definition hedges.c:231
Halfedge * ELleftbnd(el_state_t *st, Point *p)
Definition hedges.c:180
void ELdelete(Halfedge *he)
Definition hedges.c:218
Halfedge * HEcreate(el_state_t *st, Edge *e, char pm)
Definition hedges.c:129
Site * leftreg(Halfedge *he)
Definition hedges.c:237
static Agedge_t * top(edge_stack_t *sp)
Definition tred.c:73
type-generic dynamically expanding list
double ngdist(Site *s, Site *t)
Definition site.c:16
Site * bottomsite
Definition site.c:14
Definition edges.h:23
Edge * ELedge
Definition hedges.h:25
char ELpm
Definition hedges.h:26
Site * vertex
Definition hedges.h:27
double x
Definition geometry.h:24
double y
Definition geometry.h:24
Definition site.h:23
Point coord
Definition site.h:24
Halfedge * leftend
Definition hedges.h:36
arena_t allocated
outstanding dynamic allocations
Definition hedges.h:33
Halfedge * rightend
Definition hedges.h:37
Definition heap.c:18
void voronoi(Site *(*nextsite)(void *context), void *context)
Definition voronoi.c:19