]>
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 |