/[zanavi_public1]/navit/navit/maptool/poly2tri-c/001/seidel-1.0/misc.c
ZANavi

Contents of /navit/navit/maptool/poly2tri-c/001/seidel-1.0/misc.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Mon Feb 4 17:41:59 2013 UTC (11 years, 1 month ago) by zoff99
File MIME type: text/plain
File size: 2652 byte(s)
new map version, lots of fixes and experimental new features
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 }

   
Visit the ZANavi Wiki