projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
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. 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. 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>. | |
| 17 | Similarly there is a <font face="Courier New"> | |
| 18 | convolve</font> function for <a href="gtl_rectangle_concept.htm">rectangle_concept</a>. | |
| 19 | The convolution of two polygon sets produces a polygon set as its output. | |
| 20 | An example of the convolution of two polygons is shown below. 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> <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. | |
| 26 | We can see that the algorithm for Minkowski sum should support non-convex | |
| 27 | polygons that may potentially have holes. It should also support disjoint | |
| 28 | polygons in both input polygon sets. 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. | |
| 34 | In the example above the lower left red triangle is the convolution of the small | |
| 35 | blue triangle with the small green triangle. The upper right red triangle | |
| 36 | is the convolution of the large blue and large green triangle. 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. 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. | |
| 42 | It is based on the convolution of polygon edges. The convolution of two | |
| 43 | edges is very easy to compute and is in general a parallelogram. 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. Below we show the code for convolving two edges along | |
| 48 | with some type definitions we will be using throughout the tutorial. 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<int> | |
| 52 | point;<br> | |
| 53 | typedef boost::polygon::polygon_set_data<int> polygon_set;<br> | |
| 54 | typedef boost::polygon::polygon_with_holes_data<int> polygon;<br> | |
| 55 | typedef std::pair<point, point> edge;<br> | |
| 56 | using namespace boost::polygon::operators;<br> | |
| 57 | <br> | |
| 58 | void convolve_two_segments(std::vector<point>& figure, const edge& a, const | |
| 59 | edge& b) {<br> | |
| 60 | using namespace boost::polygon;<br> | |
| 61 | figure.clear();<br> | |
| 62 | figure.push_back(point(a.first));<br> | |
| 63 | figure.push_back(point(a.first));<br> | |
| 64 | figure.push_back(point(a.second));<br> | |
| 65 | figure.push_back(point(a.second));<br> | |
| 66 | convolve(figure[0], b.second);<br> | |
| 67 | convolve(figure[1], b.first);<br> | |
| 68 | convolve(figure[2], b.first);<br> | |
| 69 | 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. | |
| 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. | |
| 78 | Given an operation for convolving two edges it is pretty easy to convolve all | |
| 79 | pairs of edges of two polygon sets. The result is the convolution the | |
| 80 | perimeters of the polygon sets, but doesn't handle the convolution of their | |
| 81 | interiors. 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> <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. 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. All this does is translate the | |
| 90 | polygon by the x and y value of the point. 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. First we implement a function that convolves all pairs of | |
| 97 | edges represented by iterator pairs over points. 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 <typename itrT1, typename itrT2><br> | |
| 102 | void convolve_two_point_sequences(polygon_set& result, itrT1 ab, itrT1 ae, itrT2 | |
| 103 | bb, itrT2 be) {<br> | |
| 104 | using namespace boost::polygon;<br> | |
| 105 | if(ab == ae || bb == be)<br> | |
| 106 | return;<br> | |
| 107 | point prev_a = *ab;<br> | |
| 108 | std::vector<point> vec;<br> | |
| 109 | polygon poly;<br> | |
| 110 | ++ab;<br> | |
| 111 | for( ; ab != ae; ++ab) {<br> | |
| 112 | point prev_b = *bb;<br> | |
| 113 | itrT2 tmpb = bb;<br> | |
| 114 | ++tmpb;<br> | |
| 115 | for( ; tmpb != be; ++tmpb) {<br> | |
| 116 | convolve_two_segments(vec, std::make_pair(prev_b, | |
| 117 | *tmpb), std::make_pair(prev_a, *ab));<br> | |
| 118 | set_points(poly, vec.begin(), vec.end());<br> | |
| 119 | result.insert(poly);<br> | |
| 120 | prev_b = *tmpb;<br> | |
| 121 | }<br> | |
| 122 | prev_a = *ab;<br> | |
| 123 | }<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. 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 <typename itrT><br> | |
| 131 | void convolve_point_sequence_with_polygons(polygon_set& result, itrT b, itrT e, | |
| 132 | const std::vector<polygon>& polygons) {<br> | |
| 133 | using namespace boost::polygon;<br> | |
| 134 | for(std::size_t i = 0; i < polygons.size(); ++i) {<br> | |
| 135 | convolve_two_point_sequences(result, b, e, | |
| 136 | begin_points(polygons[i]), end_points(polygons[i]));<br> | |
| 137 | for(polygon_with_holes_traits<polygon>::iterator_holes_type | |
| 138 | itrh = begin_holes(polygons[i]);<br> | |
| 139 | itrh != end_holes(polygons[i]); ++itrh) | |
| 140 | {<br> | |
| 141 | convolve_two_point_sequences(result, b, e, | |
| 142 | begin_points(*itrh), end_points(*itrh));<br> | |
| 143 | }<br> | |
| 144 | }<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. 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& | |
| 151 | result, const polygon_set& a, const polygon_set& b) {<br> | |
| 152 | using namespace boost::polygon;<br> | |
| 153 | result.clear();<br> | |
| 154 | std::vector<polygon> a_polygons;<br> | |
| 155 | std::vector<polygon> b_polygons;<br> | |
| 156 | a.get(a_polygons);<br> | |
| 157 | b.get(b_polygons);<br> | |
| 158 | for(std::size_t ai = 0; ai < a_polygons.size(); ++ai) {<br> | |
| 159 | convolve_point_sequence_with_polygons(result, | |
| 160 | begin_points(a_polygons[ai]), <br> | |
| 161 | | |
| 162 | end_points(a_polygons[ai]), b_polygons);<br> | |
| 163 | for(polygon_with_holes_traits<polygon>::iterator_holes_type | |
| 164 | itrh = begin_holes(a_polygons[ai]);<br> | |
| 165 | itrh != end_holes(a_polygons[ai]); ++itrh) | |
| 166 | {<br> | |
| 167 | convolve_point_sequence_with_polygons(result, | |
| 168 | begin_points(*itrh), <br> | |
| 169 | | |
| 170 | end_points(*itrh), b_polygons);<br> | |
| 171 | }<br> | |
| 172 | for(std::size_t bi = 0; bi < b_polygons.size(); ++bi) {<br> | |
| 173 | polygon tmp_poly = a_polygons[ai];<br> | |
| 174 | result.insert(convolve(tmp_poly, *(begin_points(b_polygons[bi]))));<br> | |
| 175 | tmp_poly = b_polygons[bi];<br> | |
| 176 | result.insert(convolve(tmp_poly, *(begin_points(a_polygons[ai]))));<br> | |
| 177 | }<br> | |
| 178 | }<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<int>(0+300, 0, 200+300, 200);<br> | |
| 185 | a -= boost::polygon::rectangle_data<int>(50+300, 50, 150+300, 150);<br> | |
| 186 | std::vector<polygon> polys;<br> | |
| 187 | std::vector<point> 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 |