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

   1 <html>
   2
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
   5 <title>Polygon Usage</title>
   6 </head>
   7
   8 <body>
   9
  10 <h1>Minkowski Sum Tutorial</h1>
  11 <p>In this tutorial we will implement an algorithm to compute the Minkowski sum
  12 of two polygon sets.&nbsp; The Minkowski sum of two polygon sets is the
  13 convolution of the two polygon sets and is defined as the set of points which is
  14 produced if you sum all pairs of points in the two polygon sets.&nbsp; The sum
  15 of two points is implemented in Boost.Polygon by the <font face="Courier New">
  16 convolve</font> function for <a href="gtl_point_concept.htm">point_concept</a>.&nbsp;
  17 Similarly there is a <font face="Courier New">
  18 convolve</font> function for <a href="gtl_rectangle_concept.htm">rectangle_concept</a>.&nbsp;
  19 The convolution of two polygon sets produces a polygon set as its output.&nbsp;
  20 An example of the convolution of two polygons is shown below.&nbsp; The center
  21 point of the green
  22 star can be imagined to slide around freely inside the blue picture frame shape
  23 painting the area the star touches to produce the red bloated picture frame.</p>
  24 <p>&nbsp;<img border="0" src="images/convolution1.PNG" width="438" height="404"></p>
  25 <p>The above image was produced using the code presented in this tutorial.&nbsp;
  26 We can see that the algorithm for Minkowski sum should support non-convex
  27 polygons that may potentially have holes.&nbsp; It should also support disjoint
  28 polygons in both input polygon sets.&nbsp; Shown below is what happens when
  29 multiple polygons are present in each input polygon set.</p>
  30 <p><img border="0" src="images/convolution2.PNG" width="547" height="432"></p>
  31 <p>In each of these examples the origin of the coordinate system is in the lower
  32 left corner of the image and the sum of the x and y locations of the input
  33 polygons places the result in the upper right hand corner of the images.&nbsp;
  34 In the example above the lower left red triangle is the convolution of the small
  35 blue triangle with the small green triangle.&nbsp; The upper right red triangle
  36 is the convolution of the large blue and large green triangle.&nbsp; The two
  37 medium sized red polygons are the result of the convolution of the small with
  38 large and large with small blue and green triangles.&nbsp; The test case was
  39 carefully contrived to prevent the result from merging together, though that
  40 could certainly happen.</p>
  41 <p>The algorithm implemented for Minkowski sum in this tutorial is very simple.&nbsp;
  42 It is based on the convolution of polygon edges.&nbsp; The convolution of two
  43 edges is very easy to compute and is in general a parallelogram.&nbsp; An
  44 example of two edges being convolved to produce a parallelogram is shown below.</p>
  45 <p><img border="0" src="images/convolve_edges.PNG" width="491" height="461"></p>
  46 <p>Now that we know what we need from a function to convolve two edges, let's
  47 implement one now.&nbsp; Below we show the code for convolving two edges along
  48 with some type definitions we will be using throughout the tutorial.&nbsp; The
  49 code for this tutorial is available in <a href="tutorial/minkowski.cpp">
  50 minkowski.cpp</a>.</p>
  51 <p><font face="Courier New" size="2">typedef boost::polygon::point_data&lt;int&gt;
  52 point;<br>
  53 typedef boost::polygon::polygon_set_data&lt;int&gt; polygon_set;<br>
  54 typedef boost::polygon::polygon_with_holes_data&lt;int&gt; polygon;<br>
  55 typedef std::pair&lt;point, point&gt; edge;<br>
  56 using namespace boost::polygon::operators;<br>
  57 <br>
  58 void convolve_two_segments(std::vector&lt;point&gt;&amp; figure, const edge&amp; a, const
  59 edge&amp; b) {<br>
  60 &nbsp; using namespace boost::polygon;<br>
  61 &nbsp; figure.clear();<br>
  62 &nbsp; figure.push_back(point(a.first));<br>
  63 &nbsp; figure.push_back(point(a.first));<br>
  64 &nbsp; figure.push_back(point(a.second));<br>
  65 &nbsp; figure.push_back(point(a.second));<br>
  66 &nbsp; convolve(figure[0], b.second);<br>
  67 &nbsp; convolve(figure[1], b.first);<br>
  68 &nbsp; convolve(figure[2], b.first);<br>
  69 &nbsp; convolve(figure[3], b.second);<br>
  70 }</font></p>
  71 <p>This function for convolving two line segments just convolves the end points
  72 of the two line segments in all combinations to produce the four points of a
  73 parallelogram and populates a vector of points with them in the correct order.&nbsp;
  74 We are using the Boost.Polygon library function for convolving two points and
  75 the library point data structure.</p>
  76 <p>To compute the convolution of two polygon sets we start by taking the union
  77 of the convolution of all pairs of edges between the two polygon sets.&nbsp;
  78 Given an operation for convolving two edges it is pretty easy to convolve all
  79 pairs of edges of two polygon sets.&nbsp; The result is the convolution the
  80 perimeters of the polygon sets, but doesn't handle the convolution of their
  81 interiors.&nbsp; To illustrate this we show what happens when one of the above
  82 examples is computed using just the all pairs of edges convolution.</p>
  83 <p>&nbsp; <img border="0" src="images/perimeter_convolve.PNG" width="546" height="432"></p>
  84 <p>As we can see, the result is as if the small triangles were slid around the
  85 perimeter of the large triangles leaving a hole in the center that should be
  86 filled in if the small triangle were allowed to slide freely within the large
  87 triangle.&nbsp; Also available in Boost.Polygon is the <font face="Courier New">
  88 convolve</font> function for <a href="gtl_polygon_concept.htm">polygon_concept</a>
  89 that convolves a polygon over a point.&nbsp; All this does is translate the
  90 polygon by the x and y value of the point.&nbsp; To fill in the interior regions
  91 of the result of the convolution of two polygon sets we perform an all pairs of
  92 polygon convolution to the first vertex of the other polygon and merge that into
  93 the union of edge convolutions.</p>
  94 <p>Let's implement the rest of Minkowski sum of two polygon sets as the union of
  95 all pairs edges convolutions and the all pairs of polygons to point
  96 convolutions.&nbsp; First we implement a function that convolves all pairs of
  97 edges represented by iterator pairs over points.&nbsp; We assume that the first
  98 point is equal to the last point in each sequence because we know the polygons
  99 that gave rise to the iterators were produce by the Boost.Polygon algorithm for
 100 general polygon formation.</p>
 101 <p><font face="Courier New" size="2">template &lt;typename itrT1, typename itrT2&gt;<br>
 102 void convolve_two_point_sequences(polygon_set&amp; result, itrT1 ab, itrT1 ae, itrT2
 103 bb, itrT2 be) {<br>
 104 &nbsp; using namespace boost::polygon;<br>
 105 &nbsp; if(ab == ae || bb == be)<br>
 106 &nbsp;&nbsp;&nbsp; return;<br>
 107 &nbsp; point prev_a = *ab;<br>
 108 &nbsp; std::vector&lt;point&gt; vec;<br>
 109 &nbsp; polygon poly;<br>
 110 &nbsp; ++ab;<br>
 111 &nbsp; for( ; ab != ae; ++ab) {<br>
 112 &nbsp;&nbsp;&nbsp; point prev_b = *bb;<br>
 113 &nbsp;&nbsp;&nbsp; itrT2 tmpb = bb;<br>
 114 &nbsp;&nbsp;&nbsp; ++tmpb;<br>
 115 &nbsp;&nbsp;&nbsp; for( ; tmpb != be; ++tmpb) {<br>
 116 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; convolve_two_segments(vec, std::make_pair(prev_b,
 117 *tmpb), std::make_pair(prev_a, *ab));<br>
 118 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; set_points(poly, vec.begin(), vec.end());<br>
 119 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; result.insert(poly);<br>
 120 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; prev_b = *tmpb;<br>
 121 &nbsp;&nbsp;&nbsp; }<br>
 122 &nbsp;&nbsp;&nbsp; prev_a = *ab;<br>
 123 &nbsp; }<br>
 124 }</font></p>
 125 <p>Using the function defined above we can implement a function for computing
 126 the convolution of all pairs of edges represented by an iterator pair over
 127 points and edges in a collection of polygons.&nbsp; We just call the
 128 convolve_two_point_sequences for the input point sequence and all outer shell
 129 and hole point sequences from the container of polygons.</p>
 130 <p><font face="Courier New" size="2">template &lt;typename itrT&gt;<br>
 131 void convolve_point_sequence_with_polygons(polygon_set&amp; result, itrT b, itrT e,
 132 const std::vector&lt;polygon&gt;&amp; polygons) {<br>
 133 &nbsp; using namespace boost::polygon;<br>
 134 &nbsp; for(std::size_t i = 0; i &lt; polygons.size(); ++i) {<br>
 135 &nbsp;&nbsp;&nbsp; convolve_two_point_sequences(result, b, e,
 136 begin_points(polygons[i]), end_points(polygons[i]));<br>
 137 &nbsp;&nbsp;&nbsp; for(polygon_with_holes_traits&lt;polygon&gt;::iterator_holes_type
 138 itrh = begin_holes(polygons[i]);<br>
 139 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; itrh != end_holes(polygons[i]); ++itrh)
 140 {<br>
 141 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; convolve_two_point_sequences(result, b, e,
 142 begin_points(*itrh), end_points(*itrh));<br>
 143 &nbsp;&nbsp;&nbsp; }<br>
 144 &nbsp; }<br>
 145 }</font></p>
 146 <p>Using the function defined above we can implement a function for computing
 147 the convolution of all pairs of edges from polygons contained within two polygon
 148 sets.&nbsp; We also convolve each polygon with the first vertex of every polygon
 149 from the other set to fill in the interiors of the result.</p>
 150 <p><font face="Courier New" size="2">void convolve_two_polygon_sets(polygon_set&amp;
 151 result, const polygon_set&amp; a, const polygon_set&amp; b) {<br>
 152 &nbsp; using namespace boost::polygon;<br>
 153 &nbsp; result.clear();<br>
 154 &nbsp; std::vector&lt;polygon&gt; a_polygons;<br>
 155 &nbsp; std::vector&lt;polygon&gt; b_polygons;<br>
 156 &nbsp; a.get(a_polygons);<br>
 157 &nbsp; b.get(b_polygons);<br>
 158 &nbsp; for(std::size_t ai = 0; ai &lt; a_polygons.size(); ++ai) {<br>
 159 &nbsp;&nbsp;&nbsp; convolve_point_sequence_with_polygons(result,
 160 begin_points(a_polygons[ai]), <br>
 161 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 162 end_points(a_polygons[ai]), b_polygons);<br>
 163 &nbsp;&nbsp;&nbsp; for(polygon_with_holes_traits&lt;polygon&gt;::iterator_holes_type
 164 itrh = begin_holes(a_polygons[ai]);<br>
 165 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; itrh != end_holes(a_polygons[ai]); ++itrh)
 166 {<br>
 167 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; convolve_point_sequence_with_polygons(result,
 168 begin_points(*itrh), <br>
 169 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 170 end_points(*itrh), b_polygons);<br>
 171 &nbsp;&nbsp;&nbsp; }<br>
 172 &nbsp;&nbsp;&nbsp; for(std::size_t bi = 0; bi &lt; b_polygons.size(); ++bi) {<br>
 173 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; polygon tmp_poly = a_polygons[ai];<br>
 174 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; result.insert(convolve(tmp_poly, *(begin_points(b_polygons[bi]))));<br>
 175 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tmp_poly = b_polygons[bi];<br>
 176 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp; result.insert(convolve(tmp_poly, *(begin_points(a_polygons[ai]))));<br>
 177 &nbsp;&nbsp;&nbsp; }<br>
 178 &nbsp; }<br>
 179 }</font></p>
 180 <p>We test the convolution of two polygon set with the code shown below that
 181 produces the first example shown in this tutorial.<font face="Courier New" size="2">
 182 </font></p>
 183 <p><font face="Courier New" size="2">polygon_set a, b, c;<br>
 184 a += boost::polygon::rectangle_data&lt;int&gt;(0+300, 0, 200+300, 200);<br>
 185 a -= boost::polygon::rectangle_data&lt;int&gt;(50+300, 50, 150+300, 150);<br>
 186 std::vector&lt;polygon&gt; polys;<br>
 187 std::vector&lt;point&gt; pts;<br>
 188 pts.push_back(point(-40, 0+300));<br>
 189 pts.push_back(point(-10, 10+300));<br>
 190 pts.push_back(point(0, 40+300));<br>
 191 pts.push_back(point(10, 10+300));<br>
 192 pts.push_back(point(40, 0+300));<br>
 193 pts.push_back(point(10, -10+300));<br>
 194 pts.push_back(point(0, -40+300));<br>
 195 pts.push_back(point(-10, -10+300));<br>
 196 pts.push_back(point(-40, 0+300));<br>
 197 polygon poly;<br>
 198 boost::polygon::set_points(poly, pts.begin(), pts.end());<br>
 199 b+=poly;<br>
 200 polys.clear();<br>
 201 convolve_two_polygon_sets(c, a, b);</font></p>
 202 <p>Output (a is blue, b is green and c is red):</p>
 203 <p><img border="0" src="images/convolution1.PNG" width="438" height="404"></p>
 204 <p>This concludes our tutorial on how to implement Minkowski sum of polygons as
 205 the convolution of polygon sets based on the Boolean OR operation of geometry
 206 produced by simpler convolution features provided by the Boost.Polygon library.</p>
 207
 208
 209 <table class="docinfo" rules="none" frame="void" id="table1">
 210         <colgroup>
 211                 <col class="docinfo-name"><col class="docinfo-content">
 212         </colgroup>
 213         <tbody vAlign="top">
 214                 <tr>
 215                         <th class="docinfo-name">Copyright:</th>
 216                         <td>Copyright © Intel Corporation 2008-2010.</td>
 217                 </tr>
 218                 <tr class="field">
 219                         <th class="docinfo-name">License:</th>
 220                         <td class="field-body">Distributed under the Boost Software License,
 221                         Version 1.0. (See accompanying file <tt class="literal">
 222                         <span class="pre">LICENSE_1_0.txt</span></tt> or copy at
 223                         <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
 224                         http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 225                 </tr>
 226 </table>
 227
 228 </body>
 229
 230 </html>