ceph/src/boost/libs/polygon/doc/voronoi_advanced_tutorial.htm

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html><head>
   3
   4
   5
   6   <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Advanced Tutorial</title></head><body>
   7 <h1>Voronoi Advanced Tutorial<br>
   8 </h1>
   9
  10 This tutorial consists of two parts. The first one provides two
  11 examples of a real world problems that default configuration of Voronoi
  12 library is capable to solve. By default configuration we mean the one
  13 that accepts
  14 signed 32-bit integer and outputs floating-point (64-bit
  15 double) coordinates. We provide those examples to convince even the
  16 most skeptical users that they probably don't need to configure library
  17 for higher-precision input or output coordinate types. However if the
  18 posed problem really requires those, fully featured configuration of
  19 both input and output coordinate types is provided in the second part
  20 of this tutorial.<br>
  21
  22 <h2>Red Planet</h2>
  23
  24 <h3>Problem Statement</h3>
  25
  26 <img style="width: 665px; height: 369px;" alt="" src="images/rover.jpg"><br>
  27
  28 <br>Lets imagine that NASA is
  29 planning to send a new robot to Mars. Each day the center situated on Earth
  30 will send a destination point coordinates the robot needs to reach by
  31 the end of the day. Of course we'd like to save as much energy as
  32 possible thus choosing the shortest possible path. This would be a
  33 straight line in a perfect world (we don't consider curvature of
  34 surface), but situation becomes more complicated as there are some
  35 rocks and wells on Mars our robot can't go through. Behind of those our
  36 robot has some dimensions that might not allow it to pass narrow places.<br>
  37
  38 <h3>Application of Voronoi diagram</h3>
  39
  40 The problem above could be solved using Voronoi diagram. The first
  41 stage would be to discretize obstacles (rocks and wells) with
  42 polylines. Afterwards we will compute Voronoi diagram of the input set
  43 of segments. As each Voronoi edge is equidistant from the two closest
  44 sites we are able to filter edges the robot won't be able to pass due
  45 to it's dimensions. The last step would be to run a bit optimized A*
  46 algorithm to find
  47 the shortest or at least suboptimal path and we are done.<br>
  48
  49 <h3>Discretization of input geometries</h3>
  50
  51 To show how good is the default input coordinate type provided by the
  52 Voronoi library
  53 we will discretize the whole area of Mars. That will be approximately
  54 1.44 *&nbsp; 10^8&nbsp; square kilometres that is equal to 1.44 *&nbsp;
  55 10^18&nbsp; square centimetres, which could be snapped to the integer
  56 grid with a side of 1.2 * 10^9 centimetres.&nbsp; To make the Voronoi
  57 graph
  58 precise on the boundaries of that grid we will replicate input map 9
  59 times (3x3), thus Voronoi diagram within a central piece will
  60 provide us with a correct connectivity graph. This step will increase
  61 the size of our grid to 3.6 * 10^9 centimetres that is less than 2^32.
  62 So we are able to discretize the Red Planet's surface within a 1
  63 centimetre
  64 precision using the default input coordinate type (signed 32-bit
  65 integer). That would imply maximum absolute error to be
  66 equal up to 0.5 centimetres per coordinate. Considering the radius of
  67 our robot to be
  68 0.3 metres and for security reasons avoiding any large enough obstacles
  69 that are within 1 metre distance from it that error would be irrelevant.<br>
  70
  71 <span style="color: rgb(0, 0, 0); font-family: sans-serif; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 13px; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; background-color: rgb(249, 249, 249); display: inline ! important; float: none;"></span>
  72 <h3>Output analysis</h3>
  73
  74 Estimates of the resulting Voronoi diagram precision were already
  75 explained <a href="voronoi_main.htm">here</a>.
  76 So to avoid those computations again we will simply state that the
  77 maximum absolute error of the output geometries will be on the grid
  78 boundaries and will be equal to 2^-16 centimetres, which is
  79 approximately equal to 150 nanometres and is 100 times larger than
  80 a radius of a complex molecule. We would like to notice that the
  81 absolute error of the discretization step is much higher than the one
  82 produced by the Voronoi diagram construction algorithm.
  83 <h2>VLSI Design</h2>
  84
  85 <h3>Problem Statement</h3>
  86
  87 <img style="width: 400px; height: 283px;" alt="" src="images/vlsi.jpg"><br>
  88
  89 <br>
  90
  91 Very-large-scale integration (<a href="http://www.rulabinsky.com/cavd/index.html">VLSI</a>) is the
  92 process of creating
  93 integrated circuits by combining thousands of transistors into a single
  94 chip. Considering the fact that it may take weeks or months to get an
  95 integrated circuit manufactured, designers often spend large amounts of
  96 time analyzing their layouts to avoid costly mistakes. One of the
  97 common static analysis checks is minimum distance requirement between
  98 the components of an integrated circuit (distance should be greater
  99 than
 100 specified value).<br>
 101
 102 <h3>Application of Voronoi diagram</h3>
 103
 104 It appears that the minimum distance between components of the input
 105 set of points and segments corresponds to the one of the Voronoi
 106 diagram edges. This means that we can iterate through each edge of
 107 the Voronoi graph, extract the pair of input geometries that form it
 108 and find
 109 the distance between those. As the total amount of such edges is O(N)
 110 value
 111 (N - is the number of input geometries) the minimum distance could be
 112 efficiently find in a linear time once we construct the diagram.<br>
 113
 114 <h3>Discretization of input geometries</h3>
 115
 116 The average size of the modern CPUs is around 2.5 x 2.5 centimetres.
 117 Snapping this to the 32-bit integer grid will give discretization
 118 precision of 2.5 / 2^33 centimetres or 3 picometres that is 10 times
 119 smaller value than radius of an atom. That would be probably good
 120 enough precision even for a few next generations of processors.<br>
 121
 122 <h3>Output analysis</h3>
 123
 124 The maximum absolute error of the output geometries will be 2.5 / 2^47
 125 centimetres or 0.2 femtometres that is 10 times smaller value than
 126 the radius of an electron. However in this particular case we are not
 127 interested in the precision of the output, rather in its topology. As
 128 it was noticed on
 129 the <a href="voronoi_main.htm">Voronoi main page</a> very small edges
 130 are removed from the Voronoi diagram. However user should not worry
 131 because the edge that correspond to the minimal distance won't be among
 132 those. That means that we would be able to 100% correctly identify a
 133 pair of closest objects within the discretization precision.<br>
 134
 135 <h2>Conclusions</h2>
 136
 137 The above two examples show usage of the default Voronoi coordinate
 138 types
 139 in the macro and micro world. The main point of those was to give the user
 140 understanding of a scale that the default coordinate types provide. There
 141 are
 142 two main points we didn't mention before, but that would be relevant to
 143 the most real world problems:<br>
 144
 145 <ul>
 146
 147   <li>The absolute error of the coordinates of the output Voronoi
 148 diagram
 149 inside the 32-bit integer discretization grid is slightly smaller than
 150 the absolute error of discretization itself, thus could be neglected at
 151 all.</li>
 152   <li>In both problems above we didn't consider error of measurement.
 153 For example: is it possible to construct a map of the Mars within the
 154 0.5
 155 centimetres precision, or to get coordinates of the circuit parts
 156 withing the subatomic precision? I guess the answer for both questions
 157 would be "No". And that actually means that the error of the
 158 discretization
 159 step could be neglected comparing to the error produced by the
 160 measuring
 161 devices.<br>
 162   </li>
 163 </ul>
 164 The second statement means that there is actually no point to provide
 165 implementation that operates with floating-point input coordinates,
 166 because those always could be snapped to the integer grid. In case the
 167 user is not satisfied with the precision that the 32-bit integer grid
 168 provides or would like to retrieve coordinates of the output geometries
 169 within a smaller
 170 relative error, follow the next paragraph.<br>
 171
 172 <h2>Voronoi Coordinate Types Configuration</h2>
 173
 174 In the following chapter we are going to extend input coordinate type
 175 to the 48-bit signed
 176 integer and output coordinate type to the 80-bit IEEE floating-point
 177 type
 178 (long double). The code for this chapter is available in <a href="../example/voronoi_advanced_tutorial.cpp">voroni_advanced_tutorial.cpp</a>.
 179 While it won't be possible to compile it using the MSVC compiler (it
 180 doesn't
 181 support 80-bit long double type; ieee754.h header is required), it
 182 should give a clear understanding of how the library supports the user
 183 provided coordinate types.<br>
 184
 185 <br>
 186
 187 So the main step would be to declare the voronoi coordinate type traits
 188 that satisfy set of restrictions explained <a href="voronoi_builder.htm">here</a>:<br>
 189
 190 <br>
 191
 192 <span style="font-family: Courier New,Courier,monospace;">struct
 193 my_voronoi_ctype_traits {</span><br style="font-family: Courier New,Courier,monospace;">
 194
 195 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 196 typedef boost::int64_t int_type;</span><br style="font-family: Courier New,Courier,monospace;">
 197
 198 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 199 typedef detail::extended_int&lt;3&gt; int_x2_type;</span><br style="font-family: Courier New,Courier,monospace;">
 200
 201 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 202 typedef detail::extended_int&lt;3&gt; uint_x2_type;</span><br style="font-family: Courier New,Courier,monospace;">
 203
 204 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 205 typedef detail::extended_int&lt;128&gt; big_int_type;</span><br style="font-family: Courier New,Courier,monospace;">
 206
 207 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 208 typedef fpt80 fpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
 209
 210 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 211 typedef fpt80 efpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
 212
 213 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 214 typedef my_ulp_comparison ulp_cmp_type;</span><br style="font-family: Courier New,Courier,monospace;">
 215
 216 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 217 typedef my_fpt_converter to_fpt_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
 218
 219 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 220 typedef my_fpt_converter to_efpt_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
 221
 222 <span style="font-family: Courier New,Courier,monospace;">};<br>
 223 <br>
 224 </span>It is always better to use C++ built-in types wherever it's
 225 possible. That's why we use the 64-bit signed integer type to handle
 226 our
 227 input coordinates. <span style="font-family: Courier New,Courier,monospace;">int_x2_type</span>
 228 and <span style="font-family: Courier New,Courier,monospace;">uint_x2_type</span>
 229 is required to handle 96-bit signed/unsigned integers. As there is no
 230 such built-in type we use library provided efficient fixed integer
 231 type.
 232 The big integer type should be capable to handle 48 * 64 bit integers,
 233 that is
 234 less than 32 * 128, and so far we are good with <span style="font-family: Courier New,Courier,monospace;">extended_int&lt;128&gt;</span>
 235 type. We use the same floating point type for both <span style="font-family: Courier New,Courier,monospace;">fpt_type</span>
 236 and <span style="font-family: Courier New,Courier,monospace;">efpt_type</span>
 237 as it has enough exponent bits to represent both 48 * 32 bit and 48 *
 238 64 bit integers (that is also the reason we don't need two
 239 floating-point converter structures). The <span style="font-family: Courier New,Courier,monospace;">ulp_cmp_type</span>
 240 structure checks weather two IEEE floating-point values are within the
 241 given signed integer ulp range (we won't analyze corresponding code
 242 here as it requires deep understanding of the <a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">floating-point
 243 architecture</a> and its <a href="../../../boost/polygon/detail/voronoi_ctypes.hpp">usage to compare
 244 floating-point values</a>), but just to mention the declaration is
 245 following:<br>
 246
 247 <span style="font-family: Courier New,Courier,monospace;"></span><br style="font-family: Courier New,Courier,monospace;">
 248
 249 <span style="font-family: Courier New,Courier,monospace;">struct
 250 my_ulp_comparison {</span><br style="font-family: Courier New,Courier,monospace;">
 251
 252 <span style="font-family: Courier New,Courier,monospace;">&nbsp; enum
 253 Result {</span><span style="font-family: Courier New,Courier,monospace;"><br>
 254 &nbsp;&nbsp;&nbsp; LESS = -1,</span><br style="font-family: Courier New,Courier,monospace;">
 255
 256 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 257 EQUAL = 0,</span><br style="font-family: Courier New,Courier,monospace;">
 258
 259 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 260 MORE = 1</span><br style="font-family: Courier New,Courier,monospace;">
 261
 262 <span style="font-family: Courier New,Courier,monospace;">&nbsp; };</span><br style="font-family: Courier New,Courier,monospace;">
 263
 264 <span style="font-family: Courier New,Courier,monospace;">&nbsp; Result
 265 operator()(fpt80 a, fpt80 b, unsigned int maxUlps) const;</span><br style="font-family: Courier New,Courier,monospace;">
 266
 267 <span style="font-family: Courier New,Courier,monospace;">};<br>
 268 <br>
 269 </span>The last step would be to declare the <span style="font-family: Courier New,Courier,monospace;">my_fpt_converter</span>
 270 structure (converts the integer types to the floating-point type):<br>
 271
 272 <br>
 273
 274 <span style="font-family: Courier New,Courier,monospace;">struct
 275 my_fpt_converter {</span><br style="font-family: Courier New,Courier,monospace;">
 276
 277 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 278 template &lt;typename T&gt;</span><br style="font-family: Courier New,Courier,monospace;">
 279
 280 <span style="font-family: Courier New,Courier,monospace;">&nbsp; fpt80
 281 operator()(const T&amp; that) const {</span><br style="font-family: Courier New,Courier,monospace;">
 282
 283 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 284 return static_cast&lt;fpt80&gt;(that);</span><br style="font-family: Courier New,Courier,monospace;">
 285
 286 <span style="font-family: Courier New,Courier,monospace;">&nbsp; }</span><br style="font-family: Courier New,Courier,monospace;">
 287
 288 <br style="font-family: Courier New,Courier,monospace;">
 289
 290 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 291 template &lt;size_t N&gt;</span><br style="font-family: Courier New,Courier,monospace;">
 292
 293 <span style="font-family: Courier New,Courier,monospace;">&nbsp; fpt80
 294 operator()(const typename detail::extended_int&lt;N&gt;&amp; that)
 295 const {</span><br style="font-family: Courier New,Courier,monospace;">
 296
 297 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 298 fpt80 result = 0.0;</span><br style="font-family: Courier New,Courier,monospace;">
 299
 300 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 301 for (size_t i = 1; i &lt;= (std::min)((size_t)3, that.size()); ++i) {</span><br style="font-family: Courier New,Courier,monospace;">
 302
 303 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 304 if (i != 1)</span><br style="font-family: Courier New,Courier,monospace;">
 305
 306 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 307 result *= static_cast&lt;fpt80&gt;(0x100000000ULL);</span><br style="font-family: Courier New,Courier,monospace;">
 308
 309 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 310 result += that.chunks()[that.size() - i];</span><br style="font-family: Courier New,Courier,monospace;">
 311
 312 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 313 }</span><br style="font-family: Courier New,Courier,monospace;">
 314
 315 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 316 return (that.count() &lt; 0) ? -result : result;</span><br style="font-family: Courier New,Courier,monospace;">
 317
 318 <span style="font-family: Courier New,Courier,monospace;">&nbsp; }</span><br style="font-family: Courier New,Courier,monospace;">
 319
 320 <span style="font-family: Courier New,Courier,monospace;">};<br>
 321 <br>
 322 </span>At this point we are done with declaration of the Voronoi
 323 coordinate type traits. The next step is to declare the Voronoi diagram
 324 traits:<br>
 325
 326 <br>
 327
 328 <span style="font-family: Courier New,Courier,monospace;">struct
 329 my_voronoi_diagram_traits {</span><br style="font-family: Courier New,Courier,monospace;">
 330
 331 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 332 typedef fpt80 coordinate_type;</span><span style="font-family: Courier New,Courier,monospace;"></span><span style="font-family: Courier New,Courier,monospace;"></span><br style="font-family: Courier New,Courier,monospace;">
 333
 334 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 335 typedef voronoi_cell&lt;coordinate_type&gt; cell_type;</span><br style="font-family: Courier New,Courier,monospace;">
 336
 337 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 338 typedef voronoi_vertex&lt;coordinate_type&gt; vertex_type;</span><br style="font-family: Courier New,Courier,monospace;">
 339
 340 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 341 typedef voronoi_edge&lt;coordinate_type&gt; edge_type;</span><br style="font-family: Courier New,Courier,monospace;">
 342
 343 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 344 typedef struct {</span><br style="font-family: Courier New,Courier,monospace;">
 345
 346 <span style="font-family: Courier New,Courier,monospace;">&nbsp; public:</span><br style="font-family: Courier New,Courier,monospace;">
 347
 348 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 349 enum { ULPS = 128 };</span><br style="font-family: Courier New,Courier,monospace;">
 350
 351 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 352 bool operator()(const point_type &amp;v1, const point_type &amp;v2)
 353 const {</span><br style="font-family: Courier New,Courier,monospace;">
 354
 355 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 356 return (ulp_cmp(v1.x(), v2.x(), ULPS) == my_ulp_comparison::EQUAL
 357 &amp;&amp;</span><br style="font-family: Courier New,Courier,monospace;">
 358
 359 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 360 ulp_cmp(v1.y(), v2.y(), ULPS) == my_ulp_comparison::EQUAL);</span><br style="font-family: Courier New,Courier,monospace;">
 361
 362 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 363 }</span><br style="font-family: Courier New,Courier,monospace;">
 364
 365 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 366 private:</span><br style="font-family: Courier New,Courier,monospace;">
 367
 368 <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 369 my_ulp_comparison ulp_cmp;</span><br style="font-family: Courier New,Courier,monospace;">
 370
 371 <span style="font-family: Courier New,Courier,monospace;">&nbsp; }
 372 vertex_equality_predicate_type;</span><br style="font-family: Courier New,Courier,monospace;">
 373
 374 <span style="font-family: Courier New,Courier,monospace;">};</span><br>
 375
 376 <span style="font-family: Courier New,Courier,monospace;"></span><br>
 377
 378 Above we simply declared the Voronoi primitive types
 379 and vertex
 380 equality predicate using the new coordinate type and corresponding ulp
 381 comparison structure. As we are done with the declaration of the
 382 coordinate
 383 type specific structures we are ready to proceed to the construction
 384 step itself. The first step would be to initialize voronoi_builder
 385 structure with a set of random points:<br>
 386
 387 <br>
 388
 389 <span style="font-family: Courier New,Courier,monospace;">// Random
 390 generator and distribution. MAX is equal to 2^48.</span><br>
 391
 392 <span style="font-family: Courier New,Courier,monospace;">boost::mt19937_64
 393 gen(std::time(0));</span><br style="font-family: Courier New,Courier,monospace;">
 394
 395 <span style="font-family: Courier New,Courier,monospace;">boost::random::uniform_int_distribution&lt;boost::int64_t&gt;
 396 distr(-MAX, MAX-1);<br>
 397 <br>
 398 </span><span style="font-family: Courier New,Courier,monospace;">
 399 // Declaring and configuring Voronoi builder with the new coordinate
 400 type traits.<br>
 401 voronoi_builder&lt;boost::int64_t, my_voronoi_ctype_traits&gt; vb;</span><br>
 402 <span style="font-family: Courier New,Courier,monospace;"></span><br style="font-family: Courier New,Courier,monospace;">
 403
 404 <span style="font-family: Courier New,Courier,monospace;">// Voronoi
 405 builder initialization step.<br>
 406 for (size_t i = 0; i &lt; GENERATED_POINTS; ++i) {</span><br style="font-family: Courier New,Courier,monospace;">
 407
 408 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 409 boost::int64_t x = distr(gen);</span><br style="font-family: Courier New,Courier,monospace;">
 410
 411 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 412 boost::int64_t y = distr(gen);</span><br style="font-family: Courier New,Courier,monospace;">
 413
 414 <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 415 vb.insert_point(x, y);</span><br style="font-family: Courier New,Courier,monospace;">
 416
 417 <span style="font-family: Courier New,Courier,monospace;">}<br>
 418 <br>
 419 </span>The second step would be to generate the Voronoi diagram and
 420 this is done as before with the two lines of code:<br>
 421
 422 <br>
 423
 424 <span style="font-family: Courier New,Courier,monospace;">// Declaring
 425 and configuring Voronoi diagram structure with the new coordinate type
 426 traits.<br>
 427 voronoi_diagram&lt;fpt80, my_voronoi_diagram_traits&gt; vd;</span><br>
 428
 429 <span style="font-family: Courier New,Courier,monospace;">vb.construct(&amp;vd);<br>
 430 <br>
 431 </span>From this point the user can operate with the Voronoi diagram
 432 data structure
 433 and in our tutorial we output some simple stats of the resulting
 434 Voronoi graph. Probably the hardest part of this tutorial is
 435 the declaration of the ulp comparison structure. The library provides
 436 efficient well-commented cross-platform implementation for 64-bit
 437 floating-point type (double). So the best advice would be to follow
 438 that implementation, but before doing that really consider thoughtfully if the
 439 default
 440 coordinate types are not capable to deal with your problem.<br>
 441
 442 <br>
 443
 444 <table class="docinfo" id="table1" frame="void" rules="none">
 445
 446   <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup>
 447   <tbody valign="top">
 448     <tr>
 449       <th class="docinfo-name">Copyright:</th>
 450       <td>Copyright © Andrii Sydorchuk 2010-2012.</td>
 451     </tr>
 452     <tr class="field">
 453       <th class="docinfo-name">License:</th>
 454       <td class="field-body">Distributed under the Boost Software
 455 License, Version 1.0. (See accompanying file <tt class="literal"> <span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
 456 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 457     </tr>
 458   </tbody>
 459 </table>
 460
 461
 462 </body></html>