ceph/src/boost/libs/polygon/doc/index.htm

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   2 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   3 <head>
   4 <!--
   5     Copyright 2009-2010 Intel Corporation
   6     license banner
   7 -->
   8   <title>Boost Polygon Library: Main Page</title>
   9   <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" />
  10 <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
  11 </head>
  12 <body>
  13 <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
  14  cellpadding="0" cellspacing="0">
  15   <tbody>
  16     <tr>
  17       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
  18  valign="top">
  19       <div style="padding: 5px;" align="center"> <img
  20  src="images/boost.png" border="0" height="86" width="277" /><a
  21  title="www.boost.org home page" href="http://www.boost.org/"
  22  tabindex="2" style="border: medium none ;"> </a> </div>
  23       <div style="margin: 5px;">
  24       <h3 class="navbar">Contents</h3>
  25       <ul>
  26         <li>Boost.Polygon Main Page</li>
  27         <li><a href="gtl_design_overview.htm">Design Overview</a></li>
  28         <li><a href="gtl_isotropy.htm">Isotropy</a></li>
  29         <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
  30         <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
  31         <li><a href="gtl_point_concept.htm">Point Concept</a></li>
  32         <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
  33         <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
  34         <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
  35         <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
  36 With Holes Concept</a></li>
  37         <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
  38         <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
  39 With Holes Concept</a></li>
  40         <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
  41         <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
  42 Holes Concept</a></li>
  43         <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
  44 Concept</a></li>
  45         <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
  46 Concept</a></li>
  47         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
  48         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  49 Extraction 90</a></li>
  50         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  51 Extraction 45</a></li>
  52         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  53 Extraction</a></li>
  54         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  55         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  56         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  57         <li><a href="voronoi_main.htm">Voronoi Main Page<br />
  58           </a></li>
  59         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
  60         </li>
  61         <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
  62         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
  63       </ul>
  64       <h3 class="navbar">Other Resources</h3>
  65       <ul>
  66         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  67         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  68 Presentation</a></li>
  69         <li><a href="analysis.htm">Performance Analysis</a></li>
  70         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  71         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  72         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  73         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  74 Tutorial</a></li>
  75       </ul>
  76       </div>
  77       <h3 class="navbar">Polygon Sponsor</h3>
  78       <div style="padding: 5px;" align="center"> <img
  79  src="images/intlogo.gif" border="0" height="51" width="127" /><a
  80  title="www.adobe.com home page" href="http://www.adobe.com/"
  81  tabindex="2" style="border: medium none ;"> </a> </div>
  82       </td>
  83       <td
  84  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
  85  valign="top" width="100%">
  86 <!-- End Header --><br />
  87       <p>
  88       </p>
  89       <h1>THE BOOST.POLYGON LIBRARY</h1>
  90       <p>The Boost.Polygon library provides algorithms focused on
  91 manipulating planar polygon geometry data.&nbsp; Specific algorithms
  92 provided are the polygon set operations (intersection, union,
  93 difference, disjoint-union) and related algorithms such as polygon
  94 connectivity graph extraction, offsetting and map-overlay.&nbsp; An
  95 example of the disjoint-union (XOR) of figure a and figure b is shown
  96 below in figure c.&nbsp; These so-called Boolean algorithms are of
  97 significant interest in GIS (Geospatial Information Systems), VLSI CAD
  98 as well all other fields of CAD, and many more application areas, and
  99 providing them is the primary focus of this library.&nbsp; The
 100 Boost.Polygon library is not intended to cover all of computational
 101 geometry in its scope, and provides a set of capabilities for working
 102 with coordinates, points, intervals and rectangles that are needed to
 103 support implementing and interacting with polygon data structures and
 104 algorithms.&nbsp; </p>
 105       <img src="images/hand.png" border="0" height="277" width="837" />
 106       <p>One of the important features of the library is the
 107 implementation of
 108 the generic sweepline algorithm to construct Voronoi diagrams of points
 109 and linear segments in 2D (developed
 110 as part of the GSoC 2010 program). Voronoi diagram data structure has
 111 applications in image segmentation, optical character recognition,
 112 nearest neighbor queries execution. It is closely related with the
 113 other
 114 computational geometry concepts: Delaunay triangulation, medial axis,
 115 straight skeleton, the largest empty circle. The Boost.Polygon library
 116 provides interface to construct Voronoi diagram of points figure a and
 117 line segments figure b (the last could be used to discretize any
 118 two-dimensional curve). Figure c contains the example of the medial
 119 axis of the
 120 non-convex polygon. The implementation <a href="voronoi_benchmark.htm">outperforms</a>
 121 most of the known
 122 commercial and non-commercial libraries in both efficiency and
 123 numerical robustness aspects. You may find more details on the topic at
 124 the <a href="voronoi_main.htm">Voronoi main page</a>.<br />
 125       </p>
 126       <p><img src="images/voronoi.png" border="0" height="300"
 127  width="900" /></p>
 128       <p>The coordinate data type is a template parameter of all data
 129 types
 130 and algorithms provided by the library, and is expected to be integral.
 131 Floating point coordinate data types are not supported by the
 132 algorithms implemented in the library due to the fact that the
 133 achieving floating point robustness implies a different set of
 134 algorithms and generally platform specific assumptions about floating
 135 point representations.&nbsp;
 136 For additional detailed discussion of the library and its
 137 implementation including benchmark comparisons with other open source
 138 alternatives please see the <a href="GTL_boostcon2009.pdf">paper</a>
 139 and
 140       <a href="GTL_boostcon_draft03.pdf">presentation</a> from
 141       <a href="http://www.boostcon.com/home">boostcon</a> 2009 as well
 142 as a detailed
 143       <a href="analysis.htm">analysis</a> of the runtime complexity of
 144 the library's core algorithms. </p>
 145       <p>The design philosophy behind the polygon library was to create
 146 an API for invoking the library algorithms it provides on user geometry
 147 data types that is maximally intuitive, minimally error-prone and easy
 148 to integrate into pre-existing applications.&nbsp; C++-concepts based
 149 template meta-programming combined with generic operator overloading
 150 meets these design goals without sacrificing the runtime or memory
 151 efficiency of the underlying algorithms.&nbsp; The API is intended to
 152 demonstrate what could be achieved with ease by a C++-concepts based
 153 library interface, but is implemented based on current language
 154 features.&nbsp; This API makes the following code snippet that operates
 155 on non-library geometry types possible:</p>
 156       <p:colorscheme
 157  colors="#ffffff,#000000,#808080,#000000,#bbe0e3,#333399,#009999,#99cc00">
 158       </p:colorscheme>
 159       <div v:shape="_x0000_s1026" class="O">
 160       <div style="text-align: justify;"> <nobr> <span
 161  style="font-family: Courier New;"> void foo(list&lt;CPolygon&gt;&amp;
 162 result, const list&lt;CPolygon&gt;&amp; a, </span></nobr><br />
 163       <span style="font-family: Courier New;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 164       </span><nobr> <span style="font-family: Courier New;"> const
 165 list&lt;CPolygon&gt;&amp; b, int deflateValue) { </span></nobr></div>
 166       <div style="text-align: justify;"> <nobr><span
 167  style="font-family: Courier New;">&nbsp;&nbsp;&nbsp;&nbsp;
 168 CBoundingBox domainExtent; </span></nobr></div>
 169       <div style="text-align: justify;"> <nobr> <span
 170  style="font-family: Courier New;"> <span style="">&nbsp; </span>&nbsp;&nbsp;
 171 using namespace boost::polygon::operators; </span></nobr></div>
 172       <div style="text-align: justify;"> <nobr> <span
 173  style="font-family: Courier New;"> <span style="">&nbsp; </span>&nbsp;&nbsp;
 174 boost::polygon::extents(domainExtent, a); </span></nobr></div>
 175       <div style="text-align: justify;"> <nobr> <span
 176  style="font-family: Courier New;"> <span style="">&nbsp;&nbsp;&nbsp;&nbsp;
 177       </span>result += (b &amp; domainExtent) ^ (a - deflateValue); </span></nobr></div>
 178       <div style="text-align: justify;"> <nobr> <span
 179  style="font-family: Courier New;"> }</span></nobr></div>
 180       </div>
 181       <p>In the code snippet above the hypothetical polygon type
 182 CPolygon has been mapped to the library polygon concept and is used
 183 with library APIs to clip polygon list <i>b</i> against the bounding
 184 box of polygon list <i>a</i> and apply the disjoint-union of that with
 185 polygon list <i>a</i> deflated by some integer amount.&nbsp; The end
 186 result is accumulated into a list of polygons with a union
 187 operation.&nbsp; It is considerably more typing to describe this usage
 188 of the API than to code it, and the description is not much clearer
 189 than the code itself.&nbsp; A picture is worth a thousand words.</p>
 190       <p><img src="images/foo.PNG" border="0" height="371" width="432" /></p>
 191       <p>In Boost.Polygon operations such as those shown above are free
 192 functions named for what they do, or are overloads of C++ operators
 193 that make it easy to infer from reading the code what to expect.&nbsp;
 194 Operators are contained in the namespace <font face="Courier New">boost::polygon::operators</font>
 195 so that they can be used outside the <font face="Courier New">boost::polygon</font>
 196 namespace without bringing in the entire <font face="Courier New">boost::polygon</font>
 197 namespace.&nbsp; Following the principle of least astonishment, the
 198 inferred behavior should generally match the actual behavior.&nbsp;
 199 Conventions such as argument ordering (output arguments come first) and
 200 consistently applying the same semantics across different functions
 201 (accumulate) reduces the learning curve for new users while reducing
 202 the need to memorize semantics and argument ordering of many different
 203 functions for advanced users.</p>
 204       <p>While the internal library code that implements this API is
 205 usually complex and cryptic due to heavy use of template
 206 meta-programming, the application of the library API in user code is
 207 usually simple and clear because it is free of any extraneous
 208 syntax.&nbsp; The one exception to this is the mapping of user types to
 209 library concepts, which necessitates that the user perform some simple
 210 template programming and understand some of the internals of how the
 211 library concept type system works.&nbsp; The examples below should aid
 212 the user in performing these programming tasks.</p>
 213       <ul>
 214         <li>Example files:
 215           <ul>
 216             <li><a href="gtl_point_usage.htm">point_usage.cpp</a> Using
 217 the library provided point data type and functions</li>
 218             <li><a href="gtl_custom_point.htm">custom_point.cpp</a>
 219 Mapping a user defined point class to the library point_concept</li>
 220             <li><a href="gtl_polygon_usage.htm">polygon_usage.cpp</a>
 221 Using the library provided polygon data types and functions</li>
 222             <li><a href="gtl_custom_polygon.htm">custom_polygon.cpp</a>
 223 Mapping a user defined polygon class to the library polygon_concept</li>
 224             <li><a href="gtl_polygon_set_usage.htm">polygon_set_usage.cpp</a>
 225 Using the library provided polygon set data types and functions</li>
 226             <li><a href="gtl_custom_polygon_set.htm">custom_polygon_set.cpp</a>
 227 Mapping a user defined class to the library polygon_set_concept</li>
 228             <li><a href="gtl_connectivity_extraction_usage.htm">connectivity_extraction_usage.cpp</a>
 229 Using the connectivity extraction algorithm to build a connectivity
 230 graph on polygons</li>
 231             <li><a href="gtl_property_merge_usage.htm">property_merge_usage.cpp</a>
 232 Using the n-layer map-overlay algorithm on polygon data</li>
 233           </ul>
 234         </li>
 235         <li>Tutorials:
 236           <ul>
 237             <li><a href="gtl_tutorial.htm">Layout Versus Schematic</a>
 238 Learn how to apply Boost.Polygon capabilities to implement a simplified
 239 circuit extraction application</li>
 240             <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum</a>
 241 Learn how to apply Boost.Polygon capabilities to implement Minkowski
 242 sum of polygon sets</li>
 243             <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic
 244 Tutorial</a> Learn how to construct, traverse, visualize, associate
 245 data with Voronoi diagrams without digging into the library details.</li>
 246             <li><a href="voronoi_advanced_tutorial.htm">Voronoi
 247 Advanced Tutorial</a> Learn how to configure the Voronoi builder and
 248 Voronoi diagram data structure with the user provided coordinate types.
 249             </li>
 250           </ul>
 251         </li>
 252       </ul>
 253       <p>We would like to thank: Thomas Klimpel, Frank Mori Hess,
 254 Barend Gehrels, Andreas Fabri, Jeffrey Hellrung, Tim Keitt, Markus
 255 Werle, Paul A. Bristow, Robert Stewart, Mathias Gaunard, Michael
 256 Fawcett, Steven Watanabe, Joachim Faulhaber, John Bytheway, Sebastian
 257 Redl, Mika Heiskanen, John Phillips, Kai Benndorf, Hartmut Kaiser,
 258 Arash Partow, Maurizio Vitale, Brandon Kohn, David Abrahams, Gordon
 259 Woodhull, Daniel James, John Maddock, Tom Brinkman, Bo Persson, Mateusz
 260 Loskot, Christian Henning, Jean-Sebastien Stoezel, for providing
 261 feedback and or formal review of the library as part of the boost
 262 submission process and Fernando Cacciola for graciously serving as
 263 review manager.</p>
 264       </td>
 265     </tr>
 266     <tr>
 267       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
 268  valign="top"> &nbsp;</td>
 269       <td
 270  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 271  valign="top" width="100%">
 272       <table class="docinfo" id="table2" frame="void" rules="none">
 273         <colgroup> <col class="docinfo-name" /><col
 274  class="docinfo-content" /> </colgroup> <tbody valign="top">
 275           <tr>
 276             <th class="docinfo-name">Copyright:</th>
 277             <td>Copyright © Intel Corporation 2008-2010.</td>
 278           </tr>
 279           <tr class="field">
 280             <th class="docinfo-name">License:</th>
 281             <td class="field-body">Distributed under the Boost Software
 282 License, Version 1.0. (See accompanying file <tt class="literal"> <span
 283  class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
 284  class="reference" target="_top"
 285  href="http://www.boost.org/LICENSE_1_0.txt">
 286 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 287           </tr>
 288         </tbody>
 289       </table>
 290       </td>
 291     </tr>
 292   </tbody>
 293 </table>
 294 </body>
 295 </html>