1 |
#include <triangulate.h>
|
2 |
#include <sys/time.h>
|
3 |
#include <math.h>
|
4 |
|
5 |
#ifdef __STDC__
|
6 |
extern double log2(double);
|
7 |
#else
|
8 |
extern double log2();
|
9 |
#endif
|
10 |
|
11 |
static int choose_idx;
|
12 |
static int permute[SEGSIZE];
|
13 |
|
14 |
|
15 |
/* Generate a random permutation of the segments 1..n */
|
16 |
int generate_random_ordering(n)
|
17 |
int n;
|
18 |
{
|
19 |
struct timeval tval;
|
20 |
struct timezone tzone;
|
21 |
register int i;
|
22 |
int m, st[SEGSIZE], *p;
|
23 |
|
24 |
choose_idx = 1;
|
25 |
gettimeofday(&tval, &tzone);
|
26 |
srand48(tval.tv_sec);
|
27 |
|
28 |
for (i = 0; i <= n; i++)
|
29 |
st[i] = i;
|
30 |
|
31 |
p = st;
|
32 |
for (i = 1; i <= n; i++, p++)
|
33 |
{
|
34 |
m = lrand48() % (n + 1 - i) + 1;
|
35 |
permute[i] = p[m];
|
36 |
if (m != 1)
|
37 |
p[m] = p[1];
|
38 |
}
|
39 |
return 0;
|
40 |
}
|
41 |
|
42 |
|
43 |
/* Return the next segment in the generated random ordering of all the */
|
44 |
/* segments in S */
|
45 |
int choose_segment()
|
46 |
{
|
47 |
int i;
|
48 |
|
49 |
#ifdef DEBUG
|
50 |
fprintf(stderr, "choose_segment: %d\n", permute[choose_idx]);
|
51 |
#endif
|
52 |
return permute[choose_idx++];
|
53 |
}
|
54 |
|
55 |
|
56 |
#ifdef STANDALONE
|
57 |
|
58 |
/* Read in the list of vertices from infile */
|
59 |
int read_segments(filename, genus)
|
60 |
char *filename;
|
61 |
int *genus;
|
62 |
{
|
63 |
FILE *infile;
|
64 |
int ccount;
|
65 |
register int i;
|
66 |
int ncontours, npoints, first, last;
|
67 |
|
68 |
if ((infile = fopen(filename, "r")) == NULL)
|
69 |
{
|
70 |
perror(filename);
|
71 |
return -1;
|
72 |
}
|
73 |
|
74 |
fscanf(infile, "%d", &ncontours);
|
75 |
if (ncontours <= 0)
|
76 |
return -1;
|
77 |
|
78 |
/* For every contour, read in all the points for the contour. The */
|
79 |
/* outer-most contour is read in first (points specified in */
|
80 |
/* anti-clockwise order). Next, the inner contours are input in */
|
81 |
/* clockwise order */
|
82 |
|
83 |
ccount = 0;
|
84 |
i = 1;
|
85 |
|
86 |
while (ccount < ncontours)
|
87 |
{
|
88 |
int j;
|
89 |
|
90 |
fscanf(infile, "%d", &npoints);
|
91 |
first = i;
|
92 |
last = first + npoints - 1;
|
93 |
for (j = 0; j < npoints; j++, i++)
|
94 |
{
|
95 |
fscanf(infile, "%lf%lf", &seg[i].v0.x, &seg[i].v0.y);
|
96 |
if (i == last)
|
97 |
{
|
98 |
seg[i].next = first;
|
99 |
seg[i].prev = i-1;
|
100 |
seg[i-1].v1 = seg[i].v0;
|
101 |
}
|
102 |
else if (i == first)
|
103 |
{
|
104 |
seg[i].next = i+1;
|
105 |
seg[i].prev = last;
|
106 |
seg[last].v1 = seg[i].v0;
|
107 |
}
|
108 |
else
|
109 |
{
|
110 |
seg[i].prev = i-1;
|
111 |
seg[i].next = i+1;
|
112 |
seg[i-1].v1 = seg[i].v0;
|
113 |
}
|
114 |
|
115 |
seg[i].is_inserted = FALSE;
|
116 |
}
|
117 |
|
118 |
ccount++;
|
119 |
}
|
120 |
|
121 |
*genus = ncontours - 1;
|
122 |
return i-1;
|
123 |
}
|
124 |
|
125 |
#endif
|
126 |
|
127 |
|
128 |
/* Get log*n for given n */
|
129 |
int math_logstar_n(n)
|
130 |
int n;
|
131 |
{
|
132 |
register int i;
|
133 |
double v;
|
134 |
|
135 |
for (i = 0, v = (double) n; v >= 1; i++)
|
136 |
v = log2(v);
|
137 |
|
138 |
return (i - 1);
|
139 |
}
|
140 |
|
141 |
|
142 |
int math_N(n, h)
|
143 |
int n;
|
144 |
int h;
|
145 |
{
|
146 |
register int i;
|
147 |
double v;
|
148 |
|
149 |
for (i = 0, v = (int) n; i < h; i++)
|
150 |
v = log2(v);
|
151 |
|
152 |
return (int) ceil((double) 1.0*n/v);
|
153 |
}
|