1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#ifndef NULL
#define NULL 0
#endif
#define DELETED -2
#include <stdlib.h>
#include <limits.h>
#include <stdbool.h>
extern int triangulate, sorted, plot, debug;
struct Freenode {
struct Freenode *nextfree;
};
struct Freelist {
struct Freenode *head;
int nodesize;
};
char *getfree();
char *myalloc();
extern double xmin, xmax, ymin, ymax, deltax, deltay;
struct Point {
double x, y;
};
/* structure used both for sites and for vertices */
struct Site {
struct Point coord;
int sitenbr;
int refcnt;
};
extern struct Site *sites;
extern int nsites;
extern int siteidx;
extern int sqrt_nsites;
extern int nvertices;
extern struct Freelist sfl;
extern struct Site *bottomsite;
void **alloclist;
int allocnum;
struct Edge {
double a, b, c;
struct Site *ep[2];
struct Site *reg[2];
int edgenbr;
};
#define le 0
#define re 1
extern int nedges;
extern struct Freelist efl;
int has_endpoint(), right_of();
struct Site *intersect();
double dist();
struct Point PQ_min();
struct Halfedge *PQextractmin();
struct Edge *bisect();
struct Halfedge {
struct Halfedge *ELleft, *ELright;
struct Edge *ELedge;
int ELrefcnt;
char ELpm;
struct Site *vertex;
double ystar;
struct Halfedge *PQnext;
};
extern struct Freelist hfl;
extern struct Halfedge *ELleftend, *ELrightend;
extern int ELhashsize;
extern struct Halfedge **ELhash;
struct Halfedge *HEcreate(), *ELleft(), *ELright(), *ELleftbnd();
struct Site *leftreg(), *rightreg();
extern int PQhashsize;
extern struct Halfedge *PQhash;
extern struct Halfedge *PQfind();
extern int PQcount;
extern int PQmin;
int PQempty();
extern double *site_list;
extern double *vert_list;
extern double *line_list;
extern unsigned int *edge_list;
extern unsigned int *dual_list;
extern int vert_count;
extern int edge_count;
extern int line_count;
extern int dual_count;
extern int site_count;
void makefree(struct Freenode *curr, struct Freelist *fl);
void voronoi(int triangulate, struct Site *(*nextsite)());
char *getfree(struct Freelist *fl);
char *myalloc(unsigned n);
void freeinit(struct Freelist *fl, int size);
void ELinitialize();
struct Halfedge *HEcreate(struct Edge *e, int pm);
void ELinsert(struct Halfedge *lb, struct Halfedge *new);
struct Halfedge *ELgethash(int b);
struct Halfedge *ELleftbnd(struct Point *p);
void ELdelete(struct Halfedge *he);
struct Halfedge *ELright(struct Halfedge *he);
struct Halfedge *ELleft(struct Halfedge *he);
struct Site *leftreg(struct Halfedge *he);
struct Site *rightreg(struct Halfedge *he);
void geominit();
struct Edge *bisect(struct Site *s1, struct Site *s2);
struct Site *intersect(struct Halfedge *el1, struct Halfedge *el2);
int right_of(struct Halfedge *el, struct Point *p);
void endpoint(struct Edge *e, int lr, struct Site *s);
double dist(struct Site *s, struct Site *t);
void makevertex(struct Site *v);
void deref(struct Site *v);
void ref(struct Site *v);
void PQinsert(struct Halfedge *he, struct Site *v, double offset);
void PQdelete(struct Halfedge *he);
int PQbucket(struct Halfedge *he);
int PQempty();
struct Point PQ_min();
struct Halfedge *PQextractmin();
void PQinitialize();
void out_bisector(struct Edge *e);
void out_ep(struct Edge *e);
void out_vertex(struct Site *v);
void out_site(struct Site *s);
void out_triple(struct Site *s1, struct Site *s2, struct Site *s3);
|
