# Boost-Commit :

Subject: [Boost-commit] svn:boost r77700 - in sandbox/gtl: doc libs/polygon/voronoi_example
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-01 16:28:25

Author: asydorchuk
Date: 2012-04-01 16:28:24 EDT (Sun, 01 Apr 2012)
New Revision: 77700
URL: http://svn.boost.org/trac/boost/changeset/77700

Log:

Text files modified:
sandbox/gtl/doc/voronoi_builder.htm | 5 +
sandbox/gtl/libs/polygon/voronoi_example/voronoi_basic_tutorial.cpp | 2
4 files changed, 162 insertions(+), 11 deletions(-)

==============================================================================
+++ sandbox/gtl/doc/voronoi_advanced_tutorial.htm 2012-04-01 16:28:24 EDT (Sun, 01 Apr 2012)
@@ -11,6 +11,7 @@

+

@@ -26,11 +27,14 @@
of this tutorial.<br>
<h2>Red Planet</h2>

-<div style="margin-left: 40px;">
+
<h3>Problem Statement</h3>

+
<img style="width: 665px; height: 369px;" alt="" src="images/rover.jpg"><br>
+
<br>
+
Yes, we are going to talk about Mars. So lets imagine that NASA is
planning to send a new robot to Mars. Each day center situated on Earth
will send a destination point coordinates the robot needs to reach by
@@ -40,8 +44,10 @@
surface), but situation becomes more complicated as there are some
rocks and wells on Mars our robot can't go through. Behind of those our
robot has some dimensions that might not allow it to pass narrow places.<br>
+
<h3>Application of Voronoi diagram</h3>

+
The problem above could be solved using Voronoi diagram. The first
stage would be to discretize obstacles (rocks and wells) with
polylines. Afterwards we will compute Voronoi diagram of the input set
@@ -49,8 +55,10 @@
sites we are able to filter edges the robot won't be able to pass due
to it's dimensions. The last step would be to run a bit optimized A* algorithm to find
the shortest or at least suboptimal path and we are done.<br>
+
<h3>Discretization of input geometries</h3>

+
To show how good is default input coordinate type provided by Voronoi
we would discretize the whole area of Mars. That would be approximately
1.44 *&nbsp; 10^8&nbsp; square kilometres that is equal to 1.44 *&nbsp;
@@ -68,9 +76,11 @@

+
<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>
<h3>Output analysis</h3>

+
Estimates of the resulting Voronoi diagram precision were already discussed here.
So to avoid those computations again we will simply state that the
maximum absolute error of the output geometries will be on the grid
@@ -79,13 +89,16 @@

We would like to notice that the absolute error of a discretization step is much higher than the one
-produced by the Voronoi diagram construction algorithm. </div><h2>VLSI Design</h2>
+produced by the Voronoi diagram construction algorithm. <h2>VLSI Design</h2>
+

-<div style="margin-left: 40px;">
<h3>Problem Statement</h3>

+
<img style="width: 400px; height: 283px;" alt="" src="images/vlsi.jpg"><br>
-<br>Very-large-scale integration (VLSI) is the process of creating
+
+<br>
+Very-large-scale integration (VLSI) is the process of creating
integrated circuits by combining thousands of transistors into a single
chip. Considering the fact that it may take weeks or months to get an
integrated circuit manufactured, designers often spend large amounts of
@@ -93,7 +106,9 @@
common static analysis checks is minimum distance requirement between
the components of integrated circuit (distance should be not less than
specified value).<br>
+
<h3>Application of Voronoi diagram</h3>
+
It appears that the minimal distance between components of the input
set of points and segments corresponds to one of the Voronoi
diagram edges. This means that we can iterate through each edge of
@@ -102,13 +117,17 @@
(N - is the number of input geometries) minimal distance could be
efficiently find in linear time once we construct the diagram.<br>

+
<h3>Discretization of input geometries</h3>
+
The average size of the modern CPUs is around 2.5 x 2.5 centimetres.
Snapping this to the 32 bit integer grid will give discretization
precision of 2.5 / 2^33 centimetres or 3 picometres that is 10 times
smaller value than radius of an atom. That would be probably good
enough precision even for a few next generations of processors.<br>
+
<h3>Output analysis</h3>
+
The maximum absolute error of the output geometries will be 2.5 / 2^47
centimetres or 0.2 femtometres that is 10 times smaller value than
radius of an electron. However in this particular case we are not
@@ -121,7 +140,8 @@

-</div>
+
+

<h2>Conclusions</h2>
@@ -153,8 +173,136 @@

-<h2>Voronoi Coordinate Types Configuration</h2><br>
+<h2>Voronoi Coordinate Types Configuration</h2>In the following
+tutorial we are going to extend input coordinate type to 48 bit signed
+integer and output coordinate type to 80 bit IEEE floating-point type
+(long double). The code for this chapter is available in voroni_advanced_tutorial.cpp.
+While it won't be possible to compile it using MSVC (MSVC doesn't
+support 80 bit long double type; ieee754.h header is required), it
+should give clear understanding of how the library supports user
+provided coordinate types.<br>
+<br>
+So the main step would be to declare voronoi coordinate type traits that satisfy set of restrictions expalined here:<br>
+<br>
+<span style="font-family: Courier New,Courier,monospace;">struct my_voronoi_ctype_traits {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef boost::int64_t int_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef detail::extended_int&lt;3&gt; int_x2_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef detail::extended_int&lt;3&gt; uint_x2_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef detail::extended_int&lt;128&gt; big_int_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef fpt80 fpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef fpt80 efpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef my_ulp_comparison ulp_cmp_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef my_fpt_converter to_fpt_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef my_fpt_converter to_efpt_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">};<br>
+<br>
+</span>It is always better to use C++ builtin types wherever it's
+possible. That's why we use 64 bit signed integer type to handle our
+input coordinates. <span style="font-family: Courier New,Courier,monospace;">int_x2_type</span> and <span style="font-family: Courier New,Courier,monospace;">uint_x2_type</span>
+is required to handle 96 bit signed/unsigned integers. As there is no
+such builtin type we use library provided efficient fixed integer type.
+Big int type should be capable to handle 48 * 64 bit integers, that is
+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> type. We use the same floating point type for both <span style="font-family: Courier New,Courier,monospace;">fpt_type</span> and <span style="font-family: Courier New,Courier,monospace;">efpt_type</span>
+as it has enough exponent bits to represent both 48 * 32 bit and 48 *
+64 bit integers (that is also the reason we don't need two
+floating-point converter structures). The <span style="font-family: Courier New,Courier,monospace;">ulp_cmp_type</span>
+structure checks weather two IEEE floating-point values are within
+given signed integer ulp range (we won't analyze corresponding code
+here as it requires deep understanding of floating-point architecture and its usage to compare floating-point values), but to notice declaration is following:<br>
+<span style="font-family: Courier New,Courier,monospace;"></span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">struct my_ulp_comparison {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; enum Result {</span><span style="font-family: Courier New,Courier,monospace;"><br>
+&nbsp;&nbsp;&nbsp; LESS = -1,</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; EQUAL = 0,</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; MORE = 1</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; };</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; Result operator()(fpt80 a, fpt80 b, unsigned int maxUlps) const;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">};<br>
+<br>
+</span>The last step would be to declare <span style="font-family: Courier New,Courier,monospace;">my_fpt_converter</span> structure (converts integer types to floating-point type):<br>
+<br>
+<span style="font-family: Courier New,Courier,monospace;">struct my_fpt_converter {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; template &lt;typename T&gt;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; fpt80 operator()(const T&amp; that) const {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; return static_cast&lt;fpt80&gt;(that);</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; }</span><br style="font-family: Courier New,Courier,monospace;">
+<br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; template &lt;size_t N&gt;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; fpt80 operator()(const typename detail::extended_int&lt;N&gt; &amp;that) const {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; fpt80 result = 0.0;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; for (size_t i = 1; i &lt;= (std::min)((size_t)3, that.size()); ++i) {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if (i != 1)</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; result *= static_cast&lt;fpt80&gt;(0x100000000ULL);</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; result += that.chunks()[that.size() - i];</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; }</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; return (that.count() &lt; 0) ? -result : result;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; }</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">};<br>
+<br>
+</span>At this point we are done with declaration of the Voronoi
+coordinate type traits. The next step is to declare Voronoi diagram
+traits:<br>
+<br>
+<span style="font-family: Courier New,Courier,monospace;">struct my_voronoi_diagram_traits {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef fpt80 coordinate_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef struct {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; template &lt;typename CT&gt;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; fpt80 operator()(const CT&amp; that) const {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return static_cast&lt;fpt80&gt;(that);</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; }</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; } ctype_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef detail::point_2d&lt;coordinate_type&gt; point_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef voronoi_cell&lt;coordinate_type&gt; cell_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef voronoi_vertex&lt;coordinate_type&gt; vertex_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef voronoi_edge&lt;coordinate_type&gt; edge_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; typedef struct {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; public:</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; enum { ULPS = 128 };</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; bool operator()(const point_type &amp;v1, const point_type &amp;v2) const {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return (ulp_cmp(v1.x(), v2.x(), ULPS) == my_ulp_comparison::EQUAL &amp;&amp;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
+ulp_cmp(v1.y(), v2.y(), ULPS) == my_ulp_comparison::EQUAL);</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; }</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; private:</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp; my_ulp_comparison ulp_cmp;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; } vertex_equality_predicate_type;</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">};</span><br>
+
<span style="font-family: Courier New,Courier,monospace;"></span><br>
+We simply declared Voronoi primitive types, type converter and vertex
+equality predicate using new coordinate type and corresponding ulp
+comparison structure. As we are done with declaration of coordinate
+type specific structures we are ready to proceed to the construction
+step itself. The first step would be to initialize voronoi_builder
+structure with a set of random points:<br>
+<br>
+<span style="font-family: Courier New,Courier,monospace;">// Random generator and distribution. MAX is equal to 2^48.</span><br>
+<span style="font-family: Courier New,Courier,monospace;">boost::mt19937_64 gen(std::time(0));</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">boost::random::uniform_int_distribution&lt;boost::int64_t&gt; distr(-MAX, MAX-1);</span><span style="font-family: Courier New,Courier,monospace;"><br>
+// Declaring and configuring Voronoi builder with the new coordinate type traits.<br>
+voronoi_builder&lt;boost::int64_t, my_voronoi_ctype_traits&gt; vb;</span><span style="font-family: Courier New,Courier,monospace;"></span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">// Voronoi builder initialization step.<br>
+for (size_t i = 0; i &lt; GENERATED_POINTS; ++i) {</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; boost::int64_t x = distr(gen);</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; boost::int64_t y = distr(gen);</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">&nbsp; vb.insert_point(x, y);</span><br style="font-family: Courier New,Courier,monospace;">
+<span style="font-family: Courier New,Courier,monospace;">}<br>
+<br>
+</span>The second step would be to generate Voronoi diagram and this is done with two lines of code:<br>
+<br>
+<span style="font-family: Courier New,Courier,monospace;">// Declaring and configuring Voronoi diagram structure with the new coordinate type traits.<br>
+voronoi_diagram&lt;fpt80, my_voronoi_diagram_traits&gt; vd;</span><br>
+<span style="font-family: Courier New,Courier,monospace;">vb.construct(&amp;vd);<br>
+<br>
+</span>From this point user can operate with Voronoi diagram structure
+and in our tutorial we output some simple stats of the resulting
+Voronoi graph. Probably the hardest part of this tutorial is
+declaration of the ulp comparison structure. The library provides
+efficient well-commented cross-platform implementation for 64 bit
+floating-point type (double). So the best advice would be to follow
+that implementation, but before doing that really consider if default
+coordinate types are not capable to solve your problem.<br>
+<br>
<table class="docinfo" id="table1" frame="void" rules="none">
<colgroup>
<col class="docinfo-name"><col class="docinfo-content">

Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-04-01 16:28:24 EDT (Sun, 01 Apr 2012)
@@ -11,6 +11,7 @@

+
<meta http-equiv="Content-Language" content="en-us">

@@ -139,7 +140,9 @@
better to come up with a proper <font face="Courier New">
<span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
structure.<br>
- <h1>Member Functions</h1>
+
+ <h2>Member Functions</h2>
+
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody><tr>
<td style="font-family: 'Courier New',Courier,monospace;">

==============================================================================
+++ sandbox/gtl/libs/polygon/voronoi_example/voronoi_advanced_tutorial.cpp 2012-04-01 16:28:24 EDT (Sun, 01 Apr 2012)
@@ -105,7 +105,7 @@
} vertex_equality_predicate_type;
};

-// Voronoi ctype traits for 43-bit signed integer input coordinates.
+// Voronoi ctype traits for 48-bit signed integer input coordinates.
struct my_voronoi_ctype_traits {
typedef boost::int64_t int_type;
typedef detail::extended_int<3> int_x2_type;
@@ -126,7 +126,6 @@
boost::mt19937_64 gen(std::time(0));
boost::random::uniform_int_distribution<boost::int64_t> distr(-MAX, MAX-1);
voronoi_builder<boost::int64_t, my_voronoi_ctype_traits> vb;
- voronoi_diagram<fpt80, my_voronoi_diagram_traits> vd;
for (size_t i = 0; i < GENERATED_POINTS; ++i) {
boost::int64_t x = distr(gen);
boost::int64_t y = distr(gen);
@@ -135,12 +134,13 @@

printf("Constructing Voronoi diagram of %d points...\n", GENERATED_POINTS);
boost::timer::cpu_timer t;
+ voronoi_diagram<fpt80, my_voronoi_diagram_traits> vd;
t.start();
vb.construct(&vd);
boost::timer::cpu_times times = t.elapsed();
std::string ftime = boost::timer::format(times, 5, "%w");

- printf("Consturction done in: %s seconds.\n", ftime.c_str());
+ printf("Construction done in: %s seconds.\n", ftime.c_str());
printf("Resulting Voronoi graph has following stats:\n");
printf("Number of Voronoi cells: %d.\n", vd.num_cells());
printf("Number of Voronoi vertices: %d.\n", vd.num_vertices());

Modified: sandbox/gtl/libs/polygon/voronoi_example/voronoi_basic_tutorial.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/voronoi_example/voronoi_basic_tutorial.cpp (original)
+++ sandbox/gtl/libs/polygon/voronoi_example/voronoi_basic_tutorial.cpp 2012-04-01 16:28:24 EDT (Sun, 01 Apr 2012)
@@ -183,7 +183,7 @@
}
// Add 10% offset to the bounding rectangle.
bbox = voronoi_utils<double>::scale(bbox, 1.1);
- // Redner Voronoi diagram.
+ // Render Voronoi diagram.
render_diagram(vd, bbox);
}