|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r62253 - in sandbox/gtl/doc: . images tutorial
From: lucanus.j.simonson_at_[hidden]
Date: 2010-05-26 18:08:42
Author: ljsimons
Date: 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
New Revision: 62253
URL: http://svn.boost.org/trac/boost/changeset/62253
Log:
added minkowski sum tutorial
Added:
sandbox/gtl/doc/gtl_minkowski_tutorial.htm (contents, props changed)
sandbox/gtl/doc/images/convolution1.PNG (contents, props changed)
sandbox/gtl/doc/images/convolution2.PNG (contents, props changed)
sandbox/gtl/doc/images/convolve_edges.PNG (contents, props changed)
sandbox/gtl/doc/images/perimeter_convolve.PNG (contents, props changed)
sandbox/gtl/doc/tutorial/minkowski.cpp (contents, props changed)
Text files modified:
sandbox/gtl/doc/analysis.htm | 1 +
sandbox/gtl/doc/gtl_connectivity_extraction.htm | 1 +
sandbox/gtl/doc/gtl_connectivity_extraction_45.htm | 1 +
sandbox/gtl/doc/gtl_connectivity_extraction_90.htm | 1 +
sandbox/gtl/doc/gtl_coordinate_concept.htm | 1 +
sandbox/gtl/doc/gtl_design_overview.htm | 1 +
sandbox/gtl/doc/gtl_interval_concept.htm | 1 +
sandbox/gtl/doc/gtl_isotropy.htm | 1 +
sandbox/gtl/doc/gtl_point_3d_concept.htm | 1 +
sandbox/gtl/doc/gtl_point_concept.htm | 1 +
sandbox/gtl/doc/gtl_polygon_45_concept.htm | 1 +
sandbox/gtl/doc/gtl_polygon_45_set_concept.htm | 1 +
sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm | 1 +
sandbox/gtl/doc/gtl_polygon_90_concept.htm | 1 +
sandbox/gtl/doc/gtl_polygon_90_set_concept.htm | 1 +
sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm | 1 +
sandbox/gtl/doc/gtl_polygon_concept.htm | 1 +
sandbox/gtl/doc/gtl_polygon_set_concept.htm | 1 +
sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm | 1 +
sandbox/gtl/doc/gtl_property_merge.htm | 1 +
sandbox/gtl/doc/gtl_property_merge_45.htm | 1 +
sandbox/gtl/doc/gtl_property_merge_90.htm | 1 +
sandbox/gtl/doc/gtl_rectangle_concept.htm | 1 +
sandbox/gtl/doc/index.htm | 5 ++++-
24 files changed, 27 insertions(+), 1 deletions(-)
Modified: sandbox/gtl/doc/analysis.htm
==============================================================================
--- sandbox/gtl/doc/analysis.htm (original)
+++ sandbox/gtl/doc/analysis.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -47,6 +47,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
Modified: sandbox/gtl/doc/gtl_connectivity_extraction.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
Modified: sandbox/gtl/doc/gtl_connectivity_extraction_45.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction_45.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction_45.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
Modified: sandbox/gtl/doc/gtl_connectivity_extraction_90.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction_90.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction_90.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
Modified: sandbox/gtl/doc/gtl_coordinate_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_coordinate_concept.htm (original)
+++ sandbox/gtl/doc/gtl_coordinate_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
Modified: sandbox/gtl/doc/gtl_design_overview.htm
==============================================================================
--- sandbox/gtl/doc/gtl_design_overview.htm (original)
+++ sandbox/gtl/doc/gtl_design_overview.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -46,6 +46,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
Modified: sandbox/gtl/doc/gtl_interval_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_interval_concept.htm (original)
+++ sandbox/gtl/doc/gtl_interval_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
Modified: sandbox/gtl/doc/gtl_isotropy.htm
==============================================================================
--- sandbox/gtl/doc/gtl_isotropy.htm (original)
+++ sandbox/gtl/doc/gtl_isotropy.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
Added: sandbox/gtl/doc/gtl_minkowski_tutorial.htm
Modified: sandbox/gtl/doc/gtl_point_3d_concept.htm
Modified: sandbox/gtl/doc/gtl_point_concept.htm
Modified: sandbox/gtl/doc/gtl_polygon_45_concept.htm
Modified: sandbox/gtl/doc/gtl_polygon_45_set_concept.htm
Modified: sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm
Modified: sandbox/gtl/doc/gtl_polygon_90_concept.htm
Modified: sandbox/gtl/doc/gtl_polygon_90_set_concept.htm
Modified: sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm
Modified: sandbox/gtl/doc/gtl_polygon_concept.htm
Modified: sandbox/gtl/doc/gtl_polygon_set_concept.htm
Modified: sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm
Modified: sandbox/gtl/doc/gtl_property_merge.htm
Modified: sandbox/gtl/doc/gtl_property_merge_45.htm
Modified: sandbox/gtl/doc/gtl_property_merge_90.htm
Modified: sandbox/gtl/doc/gtl_rectangle_concept.htm
Added: sandbox/gtl/doc/images/convolution1.PNG
Added: sandbox/gtl/doc/images/convolution2.PNG
Added: sandbox/gtl/doc/images/convolve_edges.PNG
Added: sandbox/gtl/doc/images/perimeter_convolve.PNG
Modified: sandbox/gtl/doc/index.htm
Added: sandbox/gtl/doc/tutorial/minkowski.cpp
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/gtl_minkowski_tutorial.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -0,0 +1,230 @@
+<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 point_concept.
+Similarly there is a <font face="Courier New">
+convolve</font> function for rectangle_concept.
+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 polygon_concept
+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 produce 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 set 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>
+polys.clear();<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>)</td>
+ </tr>
+</table>
+
+</body>
+
+</html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/gtl_point_3d_concept.htm (original)
+++ sandbox/gtl/doc/gtl_point_3d_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_point_concept.htm (original)
+++ sandbox/gtl/doc/gtl_point_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_set_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_set_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_set_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge_45.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge_45.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge_90.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge_90.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
--- sandbox/gtl/doc/gtl_rectangle_concept.htm (original)
+++ sandbox/gtl/doc/gtl_rectangle_concept.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -45,6 +45,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
==============================================================================
Binary file. No diff available.
==============================================================================
Binary file. No diff available.
==============================================================================
Binary file. No diff available.
==============================================================================
Binary file. No diff available.
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -46,6 +46,7 @@
Presentation</a></li>
<li>Performance Analysis</li>
<li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
@@ -184,11 +185,13 @@
Using the n-layer map-overlay algorithm on polygon data</li>
</ul>
-<li>Tutorial:
+<li>Tutorials:
<ul>
<li>Layout Versus Schematic Learn how to
apply Boost.Polygon capabilities to implement a simplified circuit
extraction application</li>
+ <li>Minkowski Sum Learn how to
+ apply Boost.Polygon capabilities to implement Minkowski sum of polygon sets</li>
</ul>
</ul>
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/tutorial/minkowski.cpp 2010-05-26 18:08:39 EDT (Wed, 26 May 2010)
@@ -0,0 +1,154 @@
+/*
+Copyright 2010 Intel Corporation
+
+Use, modification and distribution are subject to the Boost Software License,
+Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
+http://www.boost.org/LICENSE_1_0.txt).
+*/
+#include <iostream>
+#include <boost/polygon/polygon.hpp>
+
+typedef boost::polygon::point_data<int> point;
+typedef boost::polygon::polygon_set_data<int> polygon_set;
+typedef boost::polygon::polygon_with_holes_data<int> polygon;
+typedef std::pair<point, point> edge;
+using namespace boost::polygon::operators;
+
+void convolve_two_segments(std::vector<point>& figure, const edge& a, const edge& b) {
+ using namespace boost::polygon;
+ figure.clear();
+ figure.push_back(point(a.first));
+ figure.push_back(point(a.first));
+ figure.push_back(point(a.second));
+ figure.push_back(point(a.second));
+ convolve(figure[0], b.second);
+ convolve(figure[1], b.first);
+ convolve(figure[2], b.first);
+ convolve(figure[3], b.second);
+}
+
+template <typename itrT1, typename itrT2>
+void convolve_two_point_sequences(polygon_set& result, itrT1 ab, itrT1 ae, itrT2 bb, itrT2 be) {
+ using namespace boost::polygon;
+ if(ab == ae || bb == be)
+ return;
+ point first_a = *ab;
+ point prev_a = *ab;
+ std::vector<point> vec;
+ polygon poly;
+ ++ab;
+ for( ; ab != ae; ++ab) {
+ point first_b = *bb;
+ point prev_b = *bb;
+ itrT2 tmpb = bb;
+ ++tmpb;
+ for( ; tmpb != be; ++tmpb) {
+ convolve_two_segments(vec, std::make_pair(prev_b, *tmpb), std::make_pair(prev_a, *ab));
+ set_points(poly, vec.begin(), vec.end());
+ result.insert(poly);
+ prev_b = *tmpb;
+ }
+ prev_a = *ab;
+ }
+}
+
+template <typename itrT>
+void convolve_point_sequence_with_polygons(polygon_set& result, itrT b, itrT e, const std::vector<polygon>& polygons) {
+ using namespace boost::polygon;
+ for(std::size_t i = 0; i < polygons.size(); ++i) {
+ convolve_two_point_sequences(result, b, e, begin_points(polygons[i]), end_points(polygons[i]));
+ for(polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(polygons[i]);
+ itrh != end_holes(polygons[i]); ++itrh) {
+ convolve_two_point_sequences(result, b, e, begin_points(*itrh), end_points(*itrh));
+ }
+ }
+}
+
+void convolve_two_polygon_sets(polygon_set& result, const polygon_set& a, const polygon_set& b) {
+ using namespace boost::polygon;
+ result.clear();
+ std::vector<polygon> a_polygons;
+ std::vector<polygon> b_polygons;
+ a.get(a_polygons);
+ b.get(b_polygons);
+ for(std::size_t ai = 0; ai < a_polygons.size(); ++ai) {
+ convolve_point_sequence_with_polygons(result, begin_points(a_polygons[ai]),
+ end_points(a_polygons[ai]), b_polygons);
+ for(polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(a_polygons[ai]);
+ itrh != end_holes(a_polygons[ai]); ++itrh) {
+ convolve_point_sequence_with_polygons(result, begin_points(*itrh),
+ end_points(*itrh), b_polygons);
+ }
+ for(std::size_t bi = 0; bi < b_polygons.size(); ++bi) {
+ polygon tmp_poly = a_polygons[ai];
+ result.insert(convolve(tmp_poly, *(begin_points(b_polygons[bi]))));
+ tmp_poly = b_polygons[bi];
+ result.insert(convolve(tmp_poly, *(begin_points(a_polygons[ai]))));
+ }
+ }
+}
+
+namespace boost { namespace polygon{
+
+ template <typename T>
+ std::ostream& operator<<(std::ostream& o, const polygon_data<T>& poly) {
+ o << "Polygon { ";
+ for(typename polygon_data<T>::iterator_type itr = poly.begin();
+ itr != poly.end(); ++itr) {
+ if(itr != poly.begin()) o << ", ";
+ o << (*itr).get(HORIZONTAL) << " " << (*itr).get(VERTICAL);
+ }
+ o << " } ";
+ return o;
+ }
+
+ template <typename T>
+ std::ostream& operator<<(std::ostream& o, const polygon_with_holes_data<T>& poly) {
+ o << "Polygon With Holes { ";
+ for(typename polygon_with_holes_data<T>::iterator_type itr = poly.begin();
+ itr != poly.end(); ++itr) {
+ if(itr != poly.begin()) o << ", ";
+ o << (*itr).get(HORIZONTAL) << " " << (*itr).get(VERTICAL);
+ } o << " { ";
+ for(typename polygon_with_holes_data<T>::iterator_holes_type itr = poly.begin_holes();
+ itr != poly.end_holes(); ++itr) {
+ o << (*itr);
+ }
+ o << " } } ";
+ return o;
+ }
+}}
+
+int main(int argc, char **argv) {
+ polygon_set a, b, c;
+ a += boost::polygon::rectangle_data<int>(0, 0, 1000, 1000);
+ a -= boost::polygon::rectangle_data<int>(100, 100, 900, 900);
+ a += boost::polygon::rectangle_data<int>(1000, -1000, 1010, -990);
+ std::vector<polygon> polys;
+ std::vector<point> pts;
+ pts.push_back(point(-40, 0));
+ pts.push_back(point(-10, 10));
+ pts.push_back(point(0, 40));
+ pts.push_back(point(10, 10));
+ pts.push_back(point(40, 0));
+ pts.push_back(point(10, -10));
+ pts.push_back(point(0, -40));
+ pts.push_back(point(-10, -10));
+ pts.push_back(point(-40, 0));
+ polygon poly;
+ boost::polygon::set_points(poly, pts.begin(), pts.end());
+ b+=poly;
+ pts.clear();
+ pts.push_back(point(1040, 1040));
+ pts.push_back(point(1050, 1045));
+ pts.push_back(point(1045, 1050));
+ boost::polygon::set_points(poly, pts.begin(), pts.end());
+ b+=poly;
+ polys.clear();
+ convolve_two_polygon_sets(c, a, b);
+ c.get(polys);
+ for(int i = 0; i < polys.size(); ++i ){
+ std::cout << polys[i] << std::endl;
+ }
+ return 0;
+}