| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head><!-- |
| Copyright 2009-2010 Intel Corporation |
| license banner |
| --> |
| <title>Boost Polygon Library: Main Page</title> |
| <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1"> |
| <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0"><tbody><tr> |
| <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> |
| <div style="padding: 5px;" align="center"> |
| <img border="0" src="images/boost.png" width="277" height="86"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;"> |
| </a> |
| </div> |
| <div style="margin: 5px;"> |
| <h3 class="navbar">Contents</h3> |
| <ul> |
| <li>Boost.Polygon Main Page</li> |
| <li><a href="gtl_design_overview.htm">Design Overview</a></li> |
| <li><a href="gtl_isotropy.htm">Isotropy</a></li> |
| <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li> |
| <li><a href="gtl_interval_concept.htm">Interval Concept</a></li> |
| <li> |
| <a href="gtl_point_concept.htm">Point Concept</a></li> |
| <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li> |
| <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li> |
| <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 With Holes Concept</a></li> |
| <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li> |
| <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 With Holes Concept</a></li> |
| <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li> |
| <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With Holes Concept</a></li> |
| <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set Concept</a></li> |
| <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set Concept</a></li> |
| <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li> |
| <li><a href="gtl_connectivity_extraction_90.htm">Connectivity Extraction 90</a></li> |
| <li><a href="gtl_connectivity_extraction_45.htm">Connectivity Extraction 45</a></li> |
| <li><a href="gtl_connectivity_extraction.htm">Connectivity Extraction</a></li> |
| <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li> |
| <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li> |
| <li><a href="gtl_property_merge.htm">Property Merge</a></li> |
| </ul> |
| <h3 class="navbar">Other Resources</h3> |
| <ul> |
| <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> |
| <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 |
| Presentation</a></li> |
| <li><a href="analysis.htm">Performance Analysis</a></li> |
| <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li> |
| <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li> |
| </ul> |
| </div> |
| <h3 class="navbar">Polygon Sponsor</h3> |
| <div style="padding: 5px;" align="center"> |
| <img border="0" src="images/intlogo.gif" width="127" height="51"> |
| </div> |
| </td> |
| <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"> |
| |
| <!-- End Header --> |
| |
| <br> |
| <p> |
| </p><h1>THE BOOST.POLYGON LIBRARY</h1> |
| <p>The Boost.Polygon library provides algorithms focused on manipulating planar |
| polygon geometry data. Specific algorithms provided are the polygon set |
| operations (intersection, union, difference, disjoint-union) and related |
| algorithms such as polygon connectivity graph extraction, offsetting and map-overlay. |
| An example of the disjoint-union (XOR) of figure a and figure b is shown below |
| in figure c. |
| These so-called Boolean algorithms are of significant interest in GIS (Geospatial Information |
| Systems), VLSI CAD as well al other fields of CAD, and many more application |
| areas, and providing them is the primary focus of this library. The |
| Boost.Polygon library is not intended to cover all of computational |
| geometry in its scope, and provides a set of capabilities for working with |
| coordinates, points, intervals and rectangles that are needed to support |
| implementing and interacting with polygon data structures and algorithms. </p><img border="0" src="images/hand.png" width="837" height="277"><p> |
| The coordinate data type is a template parameter of all data types and |
| algorithms provided by the library, and is expected to be integral. |
| Floating point coordinate data types are not supported by the algorithms |
| implemented in the library due to the fact that the achieving floating point |
| robustness implies a different set of algorithms and generally platform specific |
| assumptions about floating point representations. |
| For additional detailed discussion of the library and its implementation |
| including benchmark comparisons with other open source alternatives please see |
| the <a href="GTL_boostcon2009.pdf">paper</a> and |
| <a href="GTL_boostcon_draft03.pdf">presentation</a> from |
| <a href="http://www.boostcon.com/home">boostcon</a> 2009 as well as a detailed |
| <a href="analysis.htm">analysis</a> of the runtime complexity of |
| the library's core algorithms. </p> |
| <p>The design philosophy behind the polygon library was to create an API for |
| invoking the library algorithms it provides on user geometry data types that is maximally |
| intuitive, minimally error-prone and easy to integrate into pre-existing |
| applications. C++-concepts based template meta-programming combined with |
| generic operator overloading meets these design goals without sacrificing the |
| runtime or memory efficiency of the underlying algorithms. The API is |
| intended to demonstrate what could be achieved with ease by a C++-concepts based |
| library interface, but is implemented based on current language features. This API makes |
| the following code snippet that operates on non-library geometry types possible:</p> |
| <p:colorscheme |
| colors="#ffffff,#000000,#808080,#000000,#bbe0e3,#333399,#009999,#99cc00"/> |
| |
| <div v:shape="_x0000_s1026" class="O"> |
| <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1"> |
| <nobr> |
| <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New"> |
| void foo(list<CPolygon>& result, const list<CPolygon>& a, </span></nobr><br> |
| <span style="font-family: Courier New"> |
| </span><nobr> |
| <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New"> |
| const list<CPolygon>& |
| b, int deflateValue) { </span></nobr></div> |
| <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1"> |
| <nobr> |
| <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New"> |
| CBoundingBox domainExtent; </span></nobr></div> |
| <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1"> |
| <nobr> |
| <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New"> |
| <span style="mso-spacerun:yes"> </span> using namespace boost::polygon::operators; </span></nobr></div> |
| <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1"> |
| <nobr> |
| <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New"> |
| <span style="mso-spacerun:yes"> </span> |
| boost::polygon::extents(domainExtent, a); </span></nobr></div> |
| <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1"> |
| <nobr> |
| <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New"> |
| <span style="mso-spacerun:yes"> </span>result += (b & |
| domainExtent) ^ (a - deflateValue); </span></nobr></div> |
| <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1"> |
| <nobr> |
| <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New"> |
| }</span></nobr></div> |
| </div> |
| <p>In the code snippet above the hypothetical polygon type CPolygon has been |
| mapped to the library polygon concept and is used with library APIs to clip |
| polygon list <i>b</i> against the bounding box of polygon list <i>a</i> and apply the |
| disjoint-union of that with polygon list <i>a</i> deflated by some integer amount. |
| The end result is accumulated into a list of polygons with a union operation. |
| It is considerably more typing to describe this usage of the API than to code |
| it, and the description is not much clearer than the code itself. |
| A picture is worth a thousand words.</p> |
| <p><img border="0" src="images/foo.PNG" width="432" height="371"></p> |
| <p>In Boost.Polygon operations such as those shown above are free functions named for what they do, or are overloads of C++ operators that make it |
| easy to infer from reading the code what to expect. Operators are |
| contained in the namespace <font face="Courier New">boost::polygon::operators</font> |
| so that they can be used outside the <font face="Courier New">boost::polygon</font> |
| namespace without bringing in the entire <font face="Courier New">boost::polygon</font> |
| namespace. Following the |
| principle of least astonishment, the inferred behavior should generally match |
| the actual behavior. Conventions such as argument ordering (output |
| arguments come first) and consistently applying the same semantics across |
| different functions (accumulate) reduces the learning curve for new users while reducing the |
| need to memorize semantics and argument ordering of many different functions for |
| advanced users.</p> |
| <p>While the internal library code that implements this API is usually complex and |
| cryptic due to heavy use of template meta-programming, the application of the library |
| API in user code is usually simple and clear because it is free of any |
| extraneous syntax. The one exception to this is the mapping of user types |
| to library concepts, which necessitates that the user perform some simple |
| template programming and understand some of the internals of how the library |
| concept type system works. The examples below should aid the user in |
| performing these programming tasks.</p> |
| <ul> |
| |
| <li>Example files: |
| <ul> |
| <li><a href="gtl_point_usage.htm">point_usage.cpp</a> Using the |
| library provided point data type and functions</li> |
| <li><a href="gtl_custom_point.htm">custom_point.cpp</a> Mapping a |
| user defined point class to the library point_concept</li> |
| <li><a href="gtl_polygon_usage.htm">polygon_usage.cpp</a> Using |
| the library provided polygon data types and functions</li> |
| <li><a href="gtl_custom_polygon.htm">custom_polygon.cpp</a> Mapping a |
| user defined polygon class to the library polygon_concept</li> |
| <li><a href="gtl_polygon_set_usage.htm">polygon_set_usage.cpp</a> Using |
| the library provided polygon set data types and functions</li> |
| <li><a href="gtl_custom_polygon_set.htm">custom_polygon_set.cpp</a> |
| Mapping a user defined class to the library polygon_set_concept</li> |
| <li><a href="gtl_connectivity_extraction_usage.htm">connectivity_extraction_usage.cpp</a> |
| Using the connectivity extraction algorithm to build a connectivity |
| graph on polygons</li> |
| <li><a href="gtl_property_merge_usage.htm">property_merge_usage.cpp</a> |
| Using the n-layer map-overlay algorithm on polygon data</li> |
| </ul> |
| |
| <li>Tutorials: |
| <ul> |
| <li><a href="gtl_tutorial.htm">Layout Versus Schematic</a> Learn how to |
| apply Boost.Polygon capabilities to implement a simplified circuit |
| extraction application</li> |
| <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum</a> Learn how to |
| apply Boost.Polygon capabilities to implement Minkowski sum of polygon sets</li> |
| </ul> |
| |
| </ul> |
| |
| |
| <p>We would like to thank: Thomas Klimpel, Frank Mori Hess, Barend Gehrels, |
| Andreas Fabri, Jeffrey Hellrung, Tim Keitt, Markus Werle, Paul A. Bristow, |
| Robert Stewart, Mathias Gaunard, Michael Fawcett, Steven Watanabe, Joachim |
| Faulhaber, John Bytheway, Sebastian Redl, Mika Heiskanen, John Phillips, Kai |
| Benndorf, Hartmut Kaiser, Arash Partow, Maurizio Vitale, Brandon Kohn, David |
| Abrahams, Gordon Woodhull, Daniel James, John Maddock, Tom Brinkman, Bo Persson, |
| Mateusz Loskot, Christian Henning, Jean-Sebastien Stoezel, for providing |
| feedback and or formal review of the library as part of the boost submission |
| process and Fernando Cacciola for graciously serving as review manager.</p> |
| |
| |
| <tr> |
| <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> |
| </td> |
| <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"> |
| |
| |
| <table class="docinfo" rules="none" frame="void" id="table2"> |
| <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> |
| |
| </html> |