| <html> |
| |
| <head> |
| <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"> |
| <title>Polygon Usage</title> |
| </head> |
| |
| <body> |
| |
| <h1>Minkowski Sum Tutorial</h1> |
| <p>In this tutorial we will implement an algorithm to compute the Minkowski sum |
| of two polygon sets. The Minkowski sum of two polygon sets is the |
| convolution of the two polygon sets and is defined as the set of points which is |
| produced if you sum all pairs of points in the two polygon sets. The sum |
| of two points is implemented in Boost.Polygon by the <font face="Courier New"> |
| convolve</font> function for <a href="gtl_point_concept.htm">point_concept</a>. |
| Similarly there is a <font face="Courier New"> |
| convolve</font> function for <a href="gtl_rectangle_concept.htm">rectangle_concept</a>. |
| The convolution of two polygon sets produces a polygon set as its output. |
| An example of the convolution of two polygons is shown below. The center |
| point of the green |
| star can be imagined to slide around freely inside the blue picture frame shape |
| painting the area the star touches to produce the red bloated picture frame.</p> |
| <p> <img border="0" src="images/convolution1.PNG" width="438" height="404"></p> |
| <p>The above image was produced using the code presented in this tutorial. |
| We can see that the algorithm for Minkowski sum should support non-convex |
| polygons that may potentially have holes. It should also support disjoint |
| polygons in both input polygon sets. Shown below is what happens when |
| multiple polygons are present in each input polygon set.</p> |
| <p><img border="0" src="images/convolution2.PNG" width="547" height="432"></p> |
| <p>In each of these examples the origin of the coordinate system is in the lower |
| left corner of the image and the sum of the x and y locations of the input |
| polygons places the result in the upper right hand corner of the images. |
| In the example above the lower left red triangle is the convolution of the small |
| blue triangle with the small green triangle. The upper right red triangle |
| is the convolution of the large blue and large green triangle. The two |
| medium sized red polygons are the result of the convolution of the small with |
| large and large with small blue and green triangles. The test case was |
| carefully contrived to prevent the result from merging together, though that |
| could certainly happen.</p> |
| <p>The algorithm implemented for Minkowski sum in this tutorial is very simple. |
| It is based on the convolution of polygon edges. The convolution of two |
| edges is very easy to compute and is in general a parallelogram. An |
| example of two edges being convolved to produce a parallelogram is shown below.</p> |
| <p><img border="0" src="images/convolve_edges.PNG" width="491" height="461"></p> |
| <p>Now that we know what we need from a function to convolve two edges, let's |
| implement one now. Below we show the code for convolving two edges along |
| with some type definitions we will be using throughout the tutorial. The |
| code for this tutorial is available in <a href="tutorial/minkowski.cpp"> |
| minkowski.cpp</a>.</p> |
| <p><font face="Courier New" size="2">typedef boost::polygon::point_data<int> |
| point;<br> |
| typedef boost::polygon::polygon_set_data<int> polygon_set;<br> |
| typedef boost::polygon::polygon_with_holes_data<int> polygon;<br> |
| typedef std::pair<point, point> edge;<br> |
| using namespace boost::polygon::operators;<br> |
| <br> |
| void convolve_two_segments(std::vector<point>& figure, const edge& a, const |
| edge& b) {<br> |
| using namespace boost::polygon;<br> |
| figure.clear();<br> |
| figure.push_back(point(a.first));<br> |
| figure.push_back(point(a.first));<br> |
| figure.push_back(point(a.second));<br> |
| figure.push_back(point(a.second));<br> |
| convolve(figure[0], b.second);<br> |
| convolve(figure[1], b.first);<br> |
| convolve(figure[2], b.first);<br> |
| convolve(figure[3], b.second);<br> |
| }</font></p> |
| <p>This function for convolving two line segments just convolves the end points |
| of the two line segments in all combinations to produce the four points of a |
| parallelogram and populates a vector of points with them in the correct order. |
| We are using the Boost.Polygon library function for convolving two points and |
| the library point data structure.</p> |
| <p>To compute the convolution of two polygon sets we start by taking the union |
| of the convolution of all pairs of edges between the two polygon sets. |
| Given an operation for convolving two edges it is pretty easy to convolve all |
| pairs of edges of two polygon sets. The result is the convolution the |
| perimeters of the polygon sets, but doesn't handle the convolution of their |
| interiors. To illustrate this we show what happens when one of the above |
| examples is computed using just the all pairs of edges convolution.</p> |
| <p> <img border="0" src="images/perimeter_convolve.PNG" width="546" height="432"></p> |
| <p>As we can see, the result is as if the small triangles were slid around the |
| perimeter of the large triangles leaving a hole in the center that should be |
| filled in if the small triangle were allowed to slide freely within the large |
| triangle. Also available in Boost.Polygon is the <font face="Courier New"> |
| convolve</font> function for <a href="gtl_polygon_concept.htm">polygon_concept</a> |
| that convolves a polygon over a point. All this does is translate the |
| polygon by the x and y value of the point. To fill in the interior regions |
| of the result of the convolution of two polygon sets we perform an all pairs of |
| polygon convolution to the first vertex of the other polygon and merge that into |
| the union of edge convolutions.</p> |
| <p>Let's implement the rest of Minkowski sum of two polygon sets as the union of |
| all pairs edges convolutions and the all pairs of polygons to point |
| convolutions. First we implement a function that convolves all pairs of |
| edges represented by iterator pairs over points. We assume that the first |
| point is equal to the last point in each sequence because we know the polygons |
| that gave rise to the iterators were produced by the Boost.Polygon algorithm for |
| general polygon formation.</p> |
| <p><font face="Courier New" size="2">template <typename itrT1, typename itrT2><br> |
| void convolve_two_point_sequences(polygon_set& result, itrT1 ab, itrT1 ae, itrT2 |
| bb, itrT2 be) {<br> |
| using namespace boost::polygon;<br> |
| if(ab == ae || bb == be)<br> |
| return;<br> |
| point prev_a = *ab;<br> |
| std::vector<point> vec;<br> |
| polygon poly;<br> |
| ++ab;<br> |
| for( ; ab != ae; ++ab) {<br> |
| point prev_b = *bb;<br> |
| itrT2 tmpb = bb;<br> |
| ++tmpb;<br> |
| for( ; tmpb != be; ++tmpb) {<br> |
| convolve_two_segments(vec, std::make_pair(prev_b, |
| *tmpb), std::make_pair(prev_a, *ab));<br> |
| set_points(poly, vec.begin(), vec.end());<br> |
| result.insert(poly);<br> |
| prev_b = *tmpb;<br> |
| }<br> |
| prev_a = *ab;<br> |
| }<br> |
| }</font></p> |
| <p>Using the function defined above we can implement a function for computing |
| the convolution of all pairs of edges represented by an iterator pair over |
| points and edges in a collection of polygons. We just call the |
| convolve_two_point_sequences for the input point sequence and all outer shell |
| and hole point sequences from the container of polygons.</p> |
| <p><font face="Courier New" size="2">template <typename itrT><br> |
| void convolve_point_sequence_with_polygons(polygon_set& result, itrT b, itrT e, |
| const std::vector<polygon>& polygons) {<br> |
| using namespace boost::polygon;<br> |
| for(std::size_t i = 0; i < polygons.size(); ++i) {<br> |
| convolve_two_point_sequences(result, b, e, |
| begin_points(polygons[i]), end_points(polygons[i]));<br> |
| for(polygon_with_holes_traits<polygon>::iterator_holes_type |
| itrh = begin_holes(polygons[i]);<br> |
| itrh != end_holes(polygons[i]); ++itrh) |
| {<br> |
| convolve_two_point_sequences(result, b, e, |
| begin_points(*itrh), end_points(*itrh));<br> |
| }<br> |
| }<br> |
| }</font></p> |
| <p>Using the function defined above we can implement a function for computing |
| the convolution of all pairs of edges from polygons contained within two polygon |
| sets. We also convolve each polygon with the first vertex of every polygon |
| from the other set to fill in the interiors of the result.</p> |
| <p><font face="Courier New" size="2">void convolve_two_polygon_sets(polygon_set& |
| result, const polygon_set& a, const polygon_set& b) {<br> |
| using namespace boost::polygon;<br> |
| result.clear();<br> |
| std::vector<polygon> a_polygons;<br> |
| std::vector<polygon> b_polygons;<br> |
| a.get(a_polygons);<br> |
| b.get(b_polygons);<br> |
| for(std::size_t ai = 0; ai < a_polygons.size(); ++ai) {<br> |
| convolve_point_sequence_with_polygons(result, |
| begin_points(a_polygons[ai]), <br> |
| |
| end_points(a_polygons[ai]), b_polygons);<br> |
| for(polygon_with_holes_traits<polygon>::iterator_holes_type |
| itrh = begin_holes(a_polygons[ai]);<br> |
| itrh != end_holes(a_polygons[ai]); ++itrh) |
| {<br> |
| convolve_point_sequence_with_polygons(result, |
| begin_points(*itrh), <br> |
| |
| end_points(*itrh), b_polygons);<br> |
| }<br> |
| for(std::size_t bi = 0; bi < b_polygons.size(); ++bi) {<br> |
| polygon tmp_poly = a_polygons[ai];<br> |
| result.insert(convolve(tmp_poly, *(begin_points(b_polygons[bi]))));<br> |
| tmp_poly = b_polygons[bi];<br> |
| result.insert(convolve(tmp_poly, *(begin_points(a_polygons[ai]))));<br> |
| }<br> |
| }<br> |
| }</font></p> |
| <p>We test the convolution of two polygon sets with the code shown below that |
| produces the first example shown in this tutorial.<font face="Courier New" size="2"> |
| </font></p> |
| <p><font face="Courier New" size="2">polygon_set a, b, c;<br> |
| a += boost::polygon::rectangle_data<int>(0+300, 0, 200+300, 200);<br> |
| a -= boost::polygon::rectangle_data<int>(50+300, 50, 150+300, 150);<br> |
| std::vector<polygon> polys;<br> |
| std::vector<point> pts;<br> |
| pts.push_back(point(-40, 0+300));<br> |
| pts.push_back(point(-10, 10+300));<br> |
| pts.push_back(point(0, 40+300));<br> |
| pts.push_back(point(10, 10+300));<br> |
| pts.push_back(point(40, 0+300));<br> |
| pts.push_back(point(10, -10+300));<br> |
| pts.push_back(point(0, -40+300));<br> |
| pts.push_back(point(-10, -10+300));<br> |
| pts.push_back(point(-40, 0+300));<br> |
| polygon poly;<br> |
| boost::polygon::set_points(poly, pts.begin(), pts.end());<br> |
| b+=poly;<br> |
| convolve_two_polygon_sets(c, a, b);</font></p> |
| <p>Output (a is blue, b is green and c is red):</p> |
| <p><img border="0" src="images/convolution1.PNG" width="438" height="404"></p> |
| <p>This concludes our tutorial on how to implement Minkowski sum of polygons as |
| the convolution of polygon sets based on the Boolean OR operation of geometry |
| produced by simpler convolution features provided by the Boost.Polygon library.</p> |
| |
| |
| <table class="docinfo" rules="none" frame="void" id="table1"> |
| <colgroup> |
| <col class="docinfo-name"><col class="docinfo-content"> |
| </colgroup> |
| <tbody vAlign="top"> |
| <tr> |
| <th class="docinfo-name">Copyright:</th> |
| <td>Copyright © Intel Corporation 2008-2010.</td> |
| </tr> |
| <tr class="field"> |
| <th class="docinfo-name">License:</th> |
| <td class="field-body">Distributed under the Boost Software 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"> |
| http://www.boost.org/LICENSE_1_0.txt</a>)</td> |
| </tr> |
| </table> |
| |
| </body> |
| |
| </html> |
