-
Notifications
You must be signed in to change notification settings - Fork 59
/
Copy pathcircle_test.html
342 lines (306 loc) · 10.5 KB
/
circle_test.html
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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
<html>
<head>
<title>
CIRCLE_TEST - Circle Packing Measure.
</title>
</head>
<body bgcolor="#EEEEEE" link="#CC0000" alink="#FF3300" vlink="#000055">
<h1 align = "center">
CIRCLE_TEST <br> Circle Packing Measure.
</h1>
<hr>
<p>
<b>CIRCLE_TEST</b>
is a FORTRAN90 program which
analyzes point sets in the unit square (or M-dimensional unit hypercube).
</p>
<p>
The point sets are to be measured in terms of a circle-packing
test. The point of the test can best be described in analogy.
Suppose that, at each point in the set, we place a (two dimensional)
balloon of initial radius 0. At a given instant, all the balloons
begin to expand. If any two balloons touch, they instantly stop
expanding. Once all the balloons have stopped expanding, we
record the radius of each balloon.
</p>
<p>
The point sets we are interested in have been generated by a
variety of algorithms, and are stored as datasets, of
spatial dimension 2, 7 and 16, and sample sizes 10, 100,
1,000 and 10,000. The point set types include:
<ul>
<li>
<a href = "../../datasets/cvt/cvt.html">
Centroidal Voronoi Tessellation values,</a>
</li>
<li>
<a href = "../../datasets/faure/faure.html">
Faure quasirandom values,</a>
</li>
<li>
<a href = "../../datasets/halton/halton.html">
Halton quasirandom values,</a>
</li>
<li>
<a href = "../../datasets/hammersley/hammersley.html">
Hammersley quasirandom values,</a>
</li>
<li>
<a href = "../../datasets/ihs/ihs.html">
Improved Distributed Hypercube Sampling (IHS) values,</a>
</li>
<li>
<a href = "../../datasets/latin_center/latin_center.html">
Latin Center Square values,</a>
</li>
<li>
<a href = "../../datasets/latin_edge/latin_edge.html">
Latin Edge Square values,</a>
</li>
<li>
<a href = "../../datasets/latin_random/latin_random.html">
Latin Random Square values,</a>
</li>
<li>
<a href = "../../datasets/niederreiter2/niederreiter2.html">
Niederreiter quasirandom values (base 2),</a>
</li>
<li>
<a href = "../../datasets/sobol/sobol.html">
Sobol quasirandom values,</a>
</li>
<li>
<a href = "../../datasets/uniform/uniform.html">
uniform random values.</a>
</li>
</ul>
</p>
<p>
The amount of area covered by the circles is compared to the
area of the unit square. This measurement has a certain amount
of boundary effect, and is more effective when the number of
points is large, so that the boundary effects can be ignored.
In order to make a meaningful number to report, we prefer, then,
to restrict the balloons so that they cannot extend outside
the unit square. In this way we can compare the coverage for
a given set of points to that produced by a maximal sphere packing
set, for which the balloons are all of the same size.
</p>
<p>
Note that, for each datapoint, the radius of the associated circle
is the minimum distance to the nearest boundary of the Voronoi
cell containing the point.
</p>
<p>
Based on this measure of coverage, a "good" dataset would be one
for which the value was maximal. We might also be interested in
the variation in the sizes of the radiuses.
</p>
<p>
In the limit, the maximum relative packing density of a 2D
region with equal sized spheres is 0.9069. In 3D, a density
of at least 0.74 can be achieved, and it is known that no
greater than 0.7796 is possible.
</p>
<p>
<b>(in)Efficiency Note</b>: As currently programmed, the routine
is inefficient, taking execution time that is O(N^3). This is
because there are about N steps of the iteration, each of which
"retires" one point by finding its maximal radius; in each of the
N steps, the program recomputes the distances between every
unretired point and all the N points. A more clever program
would construct the Voronoi diagram, and then each point would
only have to worry about its nearest neighbors.
</p>
<p>
For instance, for the 2D Halton datasets, here is the table
of the number of points versus unrestricted (spheres can extend
out of the unit hypercube) and restricted (they can't)
scores:
<table "border=1">
<tr><th>Points</th><th>Unrestricted</th><th>Restricted</th></tr>
<tr><td> 10</td><td>0.8203</td><td>0.3884</td></tr>
<tr><td> 100</td><td>0.5416</td><td>0.4067</td></tr>
<tr><td> 1000</td><td>0.4299</td><td>0.3959</td></tr>
<tr><td>10000</td><td>0.4214</td><td>(unavailable)</td></tr>
</table>
It is a comfort to see that the restricted scores are more
tightly clustered than the unrestricted ones. This is a reflection
of the fact that they measure a geometrically meaningful
quantity that can be compared directly to 1, the volume of
the unit hypercube, and to the maximal packing density.
</p>
<p>
A collection of sample datasets, and plots of the points and the
circles involved in the circle test, is available at
<a href = "../../datasets/sample_2d/sample_2d.html">sample_2d</a>.
</p>
<h3 align = "center">
Usage:
</h3>
<p>
<blockquote>
<b>circle_test</b> <i>input_file</i>
</blockquote>
where
<ul>
<li>
<i>input_file</i> is the input file.
</li>
</ul>
</p>
<h3 align = "center">
Licensing:
</h3>
<p>
The computer code and data files described and made available on this web page
are distributed under
<a href = "../../txt/gnu_lgpl.txt">the GNU LGPL license.</a>
</p>
<h3 align = "center">
Related Programs:
</h3>
<p>
<a href = "../../c_src/diaphony/diaphony.html">
DIAPHONY</a>,
a C program which
reads a file of N points in M dimensions and computes its diaphony, a measure
of point dispersion.
</p>
<p>
<a href = "../../c_src/star_discrepancy/star_discrepancy.html">
STAR_DISCREPANCY</a>,
a C program which
reads a file of N points in M dimensions, (presumed to lie in the
unit hypercube) and computes bounds on the star discrepancy,
a measure of dispersion, by Eric Thiemard.
</p>
<p>
<a href = "../../f_src/table_quality/table_quality.html">
TABLE_QUALITY</a>,
a FORTRAN90 program which
computes the quality measures of a dataset read from a file.
which can analyze a dataset that is stored in a file.
</p>
<p>
<a href = "../../f_src/tet_mesh_quality/tet_mesh_quality.html">
TET_MESH_QUALITY</a>,
a FORTRAN90 program which
computes quality measures of a tetrahedral mesh.
</p>
<p>
<a href = "../../f_src/triangulation_quality/triangulation_quality.html">
TRIANGULATION_QUALITY</a>,
a FORTRAN90 program which
computes quality measures of a triangulation.
</p>
<h3 align = "center">
Source Code:
</h3>
<p>
<ul>
<li>
<a href = "circle_test.f90">circle_test.f90</a>, the source code.
</li>
<li>
<a href = "circle_test.sh">circle_test.sh</a>,
commands to compile the source code and run it on the
test files.
</li>
</ul>
</p>
<h3 align = "center">
Examples and Tests:
</h3>
<p>
<ul>
<li>
<a href = "halton_02_00010_output.txt">halton_02_00010_output.txt</a>,
the circle test applied to 10 2D Halton points.
</li>
<li>
<a href = "halton_02_00100_output.txt">halton_02_00100_output.txt</a>,
the circle test applied to 100 2D Halton points.
</li>
<li>
<a href = "halton_02_01000_output.txt">halton_02_01000_output.txt</a>,
the circle test applied to 1000 2D Halton points.
</li>
<li>
<a href = "halton_02_10000_output.txt">halton_02_10000_output.txt</a>,
the circle test applied to 10000 2D Halton points.
</li>
</ul>
</p>
<h3 align = "center">
List of Routines:
</h3>
<p>
<ul>
<li>
<b>CIRCLE_TEST_MAIN</b> reads a dataset, and applies the circle test.
</li>
<li>
<b>CIRCLE_TEST</b> performs the circle test on a set of points.
</li>
<li>
<b>CH_IS_DIGIT</b> returns .TRUE. if a character is a decimal digit.
</li>
<li>
<b>CH_TO_DIGIT</b> returns the integer value of a base 10 digit.
</li>
<li>
<b>DIGIT_INC</b> increments a decimal digit.
</li>
<li>
<b>DIGIT_TO_CH</b> returns the character representation of a decimal digit.
</li>
<li>
<b>FILE_COLUMN_COUNT</b> counts the number of columns in the first line of a file.
</li>
<li>
<b>FILE_LINE_COUNT</b> counts the number of lines in a file.
</li>
<li>
<b>FILE_NAME_INC</b> generates the next filename in a series.
</li>
<li>
<b>GET_FILE_NAME</b> gets the input file name.
</li>
<li>
<b>GET_UNIT</b> returns a free FORTRAN unit number.
</li>
<li>
<b>R8_PI</b> returns the value of pi.
</li>
<li>
<b>RADIUS_MAXIMUS</b> finds the biggest possible nonintersecting sphere.
</li>
<li>
<b>READ_INPUT_FILE</b> reads the data from the input file.
</li>
<li>
<b>SPHERE_UNIT_VOLUME_ND</b> computes the volume of a unit sphere in ND.
</li>
<li>
<b>SPHERE_VOLUME_ND</b> computes the volume of a sphere in ND.
</li>
<li>
<b>TIMESTAMP</b> prints the current YMDHMS date as a time stamp.
</li>
<li>
<b>WORD_COUNT</b> counts the number of "words" in a string.
</li>
</ul>
</p>
<p>
You can go up one level to <a href = "../f_src.html">
the FORTRAN90 source codes</a>.
</p>
<hr>
<i>
Last revised on 04 October 2008.
</i>
<!-- John Burkardt -->
</body>
</html>