[ceph.git] / ceph / src / boost / libs / polygon / doc / index.htm

<!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.&nbsp; 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.&nbsp; An
example of the disjoint-union (XOR) of figure a and figure b is shown
below in figure c.&nbsp; 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.&nbsp; 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.&nbsp; </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.&nbsp;
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.&nbsp; 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.&nbsp; 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.&nbsp; 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&lt;CPolygon&gt;&amp;
result, const list&lt;CPolygon&gt;&amp; a, </span></nobr><br />
      <span style="font-family: Courier New;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
      </span><nobr> <span style="font-family: Courier New;"> const
list&lt;CPolygon&gt;&amp; b, int deflateValue) { </span></nobr></div>
      <div style="text-align: justify;"> <nobr><span
 style="font-family: Courier New;">&nbsp;&nbsp;&nbsp;&nbsp;
CBoundingBox domainExtent; </span></nobr></div>
      <div style="text-align: justify;"> <nobr> <span
 style="font-family: Courier New;"> <span style="">&nbsp; </span>&nbsp;&nbsp;
using namespace boost::polygon::operators; </span></nobr></div>
      <div style="text-align: justify;"> <nobr> <span
 style="font-family: Courier New;"> <span style="">&nbsp; </span>&nbsp;&nbsp;
boost::polygon::extents(domainExtent, a); </span></nobr></div>
      <div style="text-align: justify;"> <nobr> <span
 style="font-family: Courier New;"> <span style="">&nbsp;&nbsp;&nbsp;&nbsp;
      </span>result += (b &amp; 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.&nbsp; The end
result is accumulated into a list of polygons with a union
operation.&nbsp; 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.&nbsp; 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.&nbsp;
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.&nbsp; Following the principle of least astonishment, the
inferred behavior should generally match the actual behavior.&nbsp;
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.&nbsp; 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.&nbsp; 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"> &nbsp;</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>
Commit	Line	Data
7c673cae FG	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.  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.  An
95	example of the disjoint-union (XOR) of figure a and figure b is shown
96	below in figure c.  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.  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.  </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.
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.  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.  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.  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<CPolygon>&
162	result, const list<CPolygon>& a, </span></nobr><br />
163	<span style="font-family: Courier New;">
164	</span><nobr> <span style="font-family: Courier New;"> const
165	list<CPolygon>& b, int deflateValue) { </span></nobr></div>
166	<div style="text-align: justify;"> <nobr><span
167	style="font-family: Courier New;">
168	CBoundingBox domainExtent; </span></nobr></div>
169	<div style="text-align: justify;"> <nobr> <span
170	style="font-family: Courier New;"> <span style="">  </span>
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="">  </span>
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="">
177	</span>result += (b & 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.  The end
186	result is accumulated into a list of polygons with a union
187	operation.  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.  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.
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.  Following the principle of least astonishment, the
198	inferred behavior should generally match the actual behavior.
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.  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.  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">  </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