123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295 |
- <!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" />
- <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
- </head>
- <body>
- <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
- src="images/boost.png" border="0" height="86" width="277" /><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_segment_concept.htm">Segment 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>
- <li><a href="voronoi_main.htm">Voronoi Main Page<br />
- </a></li>
- <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
- </li>
- <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
- <li><a href="voronoi_diagram.htm">Voronoi Diagram</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>
- <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
- <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
- Tutorial</a></li>
- </ul>
- </div>
- <h3 class="navbar">Polygon Sponsor</h3>
- <div style="padding: 5px;" align="center"> <img
- src="images/intlogo.gif" border="0" height="51" width="127" /><a
- title="www.adobe.com home page" href="http://www.adobe.com/"
- tabindex="2" style="border: medium none ;"> </a> </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 all 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 src="images/hand.png" border="0" height="277" width="837" />
- <p>One of the important features of the library is the
- implementation of
- the generic sweepline algorithm to construct Voronoi diagrams of points
- and linear segments in 2D (developed
- as part of the GSoC 2010 program). Voronoi diagram data structure has
- applications in image segmentation, optical character recognition,
- nearest neighbor queries execution. It is closely related with the
- other
- computational geometry concepts: Delaunay triangulation, medial axis,
- straight skeleton, the largest empty circle. The Boost.Polygon library
- provides interface to construct Voronoi diagram of points figure a and
- line segments figure b (the last could be used to discretize any
- two-dimensional curve). Figure c contains the example of the medial
- axis of the
- non-convex polygon. The implementation <a href="voronoi_benchmark.htm">outperforms</a>
- most of the known
- commercial and non-commercial libraries in both efficiency and
- numerical robustness aspects. You may find more details on the topic at
- the <a href="voronoi_main.htm">Voronoi main page</a>.<br />
- </p>
- <p><img src="images/voronoi.png" border="0" height="300"
- width="900" /></p>
- <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">
- </p:colorscheme>
- <div v:shape="_x0000_s1026" class="O">
- <div style="text-align: justify;"> <nobr> <span
- style="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;"> const
- list<CPolygon>& b, int deflateValue) { </span></nobr></div>
- <div style="text-align: justify;"> <nobr><span
- style="font-family: Courier New;">
- CBoundingBox domainExtent; </span></nobr></div>
- <div style="text-align: justify;"> <nobr> <span
- style="font-family: Courier New;"> <span style=""> </span>
- using namespace boost::polygon::operators; </span></nobr></div>
- <div style="text-align: justify;"> <nobr> <span
- style="font-family: Courier New;"> <span style=""> </span>
- boost::polygon::extents(domainExtent, a); </span></nobr></div>
- <div style="text-align: justify;"> <nobr> <span
- style="font-family: Courier New;"> <span style="">
- </span>result += (b & domainExtent) ^ (a - deflateValue); </span></nobr></div>
- <div style="text-align: justify;"> <nobr> <span
- style="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 src="images/foo.PNG" border="0" height="371" width="432" /></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>
- <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>
- <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic
- Tutorial</a> Learn how to construct, traverse, visualize, associate
- data with Voronoi diagrams without digging into the library details.</li>
- <li><a href="voronoi_advanced_tutorial.htm">Voronoi
- Advanced Tutorial</a> Learn how to configure the Voronoi builder and
- Voronoi diagram data structure with the user provided coordinate types.
- </li>
- </ul>
- </li>
- </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>
- </td>
- </tr>
- <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" id="table2" frame="void" rules="none">
- <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>
- </tbody>
- </table>
- </td>
- </tr>
- </tbody>
- </table>
- </body>
- </html>
|