boost_1_45_0/libs/polygon/doc/gtl_design_overview.htm - nest-learning-thermostat/5.0/boost - Git at Google

 <!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" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:(null)1="http://www.w3.org/TR/REC-html40"><head><!--
     Copyright 2009-2010 Intel Corporation
     license banner
 -->
 <title>Boost Polygon Library: Overview</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><a href="index.htm">Boost.Polygon Main Page</a></li>
 			<li>Design Overview</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>Polygon Library Design Overview</h1>

 <p>
 <p>The Polygon library uses C++-Concepts inspired template programming to
 provide generic library functions overloaded on concept type.&nbsp; There are
 currently thirteen concepts in the Polygon library type system.&nbsp; A concept
 object in the Polygon library is just an empty struct similar to a tag that
 would be used for tag dispatching.&nbsp;&nbsp; These concepts are shown in the
 refinement diagram below.</p>


 </body><img border="0" src="images/refinements.png" width="466" height="369"><p>
 The arrows between diagram bubbles show concept refinement relationships.&nbsp; This is
 similar, but not identical to, inheritance relationships between normal classes.&nbsp;
 A refinement of a concept narrows down the definition of a more general concept.&nbsp;
 For example, the rectangle concept is a refinement of a polygon concept because
 it restricts the polygon to a four sided, axis-parallel, rectilinear figure.&nbsp; A refinement
 of a concept is always acceptable to an API that expects read only access to a
 given concept, but never acceptable to an API that expects to write to that
 concept.&nbsp; There are three types of geometry in the polygon library, the
 general case, the case restricted to angles that are multiples of 45 degrees,
 and the Manhattan/rectilinear case where angles are restricted to multiples of
 90 degrees.&nbsp;&nbsp; The refinement diagram shows that 90 degree concepts are
 refinements of 45 degree concepts, which are themselves refinements of the
 general case.&nbsp; This allows the compiler to choose between the three
 implementations of algorithms to select the best algorithm for the conceptual
 data types passed to an overload of a function including heterogeneous
 combinations of 90, 45 and general case geometry.&nbsp; To provide the
 <font face="Courier New">operator&amp;</font> that performs the intersection on any
 pair of objects from the ten conceptual types related to each other through
 refinement in the diagraph above fully one hundred distinct combinations of
 conceptual types are supported by the library, but only three overloads are
 required to implement the operator (one for 90, one for 45 and one for arbitrary
 angle version of the intersection operation) because refinement generalizes the
 implementation of the interface.&nbsp; In this way a fully symmetric, complete
 and internally consistent API is implemented to provide meaningful and correct
 behaviors for all combinations of argument types in all APIs where those types
 make sense.&nbsp; For example, it doesn't make sense to copy data from a polygon
 into a rectangle, so attempting to do so yields a syntax error, while copying a
 rectangle into a polygon does make sense.&nbsp; The <font face="Courier New">
 assign()</font> function that is used to copy geometry data between concepts
 instantiates for the 49 combinations of concepts that make sense, but not for
 the 51 combinations that are illegal.&nbsp; The syntax error you will see when
 attempting an illegal assign operation is simple and clear because use of SFINAE
 by the library to overload generic functions means no matching function is found
 by the compiler in cases where no overload is provided.</p>
 <p>
 <font face="Courier New">error: no matching function for call to 'assign(rectangle_data&lt;int&gt;&amp;,
 polygon_data&lt;int&gt;&amp;)'</font></p>
 <p>Associated with each concept is a traits struct that generally must be
 specialized for a given data type to provide the concept mapping between the
 interfaces of the data type and the expected behaviors of an object of that type
 required by the library.&nbsp; The library also provides its own data types for
 each concept that conform to the default traits definition.&nbsp; These library
 provided data types are no more than dumb containers that provide access to
 their data and rely on the generic library functions to enforce invariants and
 provide useful behaviors specific to their type of geometry that would normally
 be member functions of the data type in an OO design.&nbsp; The library data
 types conform to the default traits associated with their related geometry
 concept and are registered as models of that concept.&nbsp; When a data
 type has been mapped to a concept through traits it needs to be registered
 as that conceptual type with the library by
 specializing the geometry_concept meta-function.&nbsp; Once mapped and
 registered, a user data type can be used interchangeably with library data types
 in the generic free functions that are overloaded on concept.<p>Traits for
 mapping a data type to a concept are broken down into mutable and read only
 traits.&nbsp; Read only traits are specialized internally to work with any types
 that are refinements of a concept.&nbsp; The mutable traits are defined only for
 objects that exactly model the concept.&nbsp; Both read only traits and mutable
 traits need to be defined for a type to model a concept, but a type can be used
 without defining the mutable traits as long as no API that needs to modify the
 object is used with that type.&nbsp; For example, a triangle type could be
 registered as a polygon_concept and the read only traits but not the mutable
 traits defined for that triangle type.&nbsp; This would allow the triangle type
 to be passed into any API that expects a const reference to an object that models
 polygon.&nbsp;
 <p>An object that is a model of a given concept can usually be viewed as a model of any of its
 refinements if it is determined at runtime to conform to the restrictions of
 those concepts.&nbsp; This concept casting is accomplished through the
 <font face="Courier New">view_as&lt;&gt;()</font> function.&nbsp; For example if
 an object of conceptual type polygon 90 has four sides it must be a rectangle,
 and can be viewed as a rectangle with the following syntax:</p>
 <p><font face="Courier New">view_as&lt;rectangle_concept&gt;(polygon_90_object)</font></p>
 <p>The return value of <font face="Courier New">view_as&lt;&gt;()</font> can be
 passed into any interface that expects an object of the conceptual type
 specified in its template parameter.&nbsp; The exception to this ability to
 concept cast geometric objects is that polygon set objects cannot be viewed as
 individual polygons or rectangles.</p> <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" 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</a>)</td>
 		</tr>
 </table>

 </html>
	<!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" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:(null)1="http://www.w3.org/TR/REC-html40"><head><!--
	Copyright 2009-2010 Intel Corporation
	license banner
	-->
	<title>Boost Polygon Library: Overview</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><a href="index.htm">Boost.Polygon Main Page</a></li>
	<li>Design Overview</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>Polygon Library Design Overview</h1>

	<p>
	<p>The Polygon library uses C++-Concepts inspired template programming to
	provide generic library functions overloaded on concept type.  There are
	currently thirteen concepts in the Polygon library type system.  A concept
	object in the Polygon library is just an empty struct similar to a tag that
	would be used for tag dispatching.   These concepts are shown in the
	refinement diagram below.</p>


	</body><img border="0" src="images/refinements.png" width="466" height="369"><p>
	The arrows between diagram bubbles show concept refinement relationships.  This is
	similar, but not identical to, inheritance relationships between normal classes.
	A refinement of a concept narrows down the definition of a more general concept.
	For example, the rectangle concept is a refinement of a polygon concept because
	it restricts the polygon to a four sided, axis-parallel, rectilinear figure.  A refinement
	of a concept is always acceptable to an API that expects read only access to a
	given concept, but never acceptable to an API that expects to write to that
	concept.  There are three types of geometry in the polygon library, the
	general case, the case restricted to angles that are multiples of 45 degrees,
	and the Manhattan/rectilinear case where angles are restricted to multiples of
	90 degrees.   The refinement diagram shows that 90 degree concepts are
	refinements of 45 degree concepts, which are themselves refinements of the
	general case.  This allows the compiler to choose between the three
	implementations of algorithms to select the best algorithm for the conceptual
	data types passed to an overload of a function including heterogeneous
	combinations of 90, 45 and general case geometry.  To provide the
	<font face="Courier New">operator&</font> that performs the intersection on any
	pair of objects from the ten conceptual types related to each other through
	refinement in the diagraph above fully one hundred distinct combinations of
	conceptual types are supported by the library, but only three overloads are
	required to implement the operator (one for 90, one for 45 and one for arbitrary
	angle version of the intersection operation) because refinement generalizes the
	implementation of the interface.  In this way a fully symmetric, complete
	and internally consistent API is implemented to provide meaningful and correct
	behaviors for all combinations of argument types in all APIs where those types
	make sense.  For example, it doesn't make sense to copy data from a polygon
	into a rectangle, so attempting to do so yields a syntax error, while copying a
	rectangle into a polygon does make sense.  The <font face="Courier New">
	assign()</font> function that is used to copy geometry data between concepts
	instantiates for the 49 combinations of concepts that make sense, but not for
	the 51 combinations that are illegal.  The syntax error you will see when
	attempting an illegal assign operation is simple and clear because use of SFINAE
	by the library to overload generic functions means no matching function is found
	by the compiler in cases where no overload is provided.</p>
	<p>
	<font face="Courier New">error: no matching function for call to 'assign(rectangle_data<int>&,
	polygon_data<int>&)'</font></p>
	<p>Associated with each concept is a traits struct that generally must be
	specialized for a given data type to provide the concept mapping between the
	interfaces of the data type and the expected behaviors of an object of that type
	required by the library.  The library also provides its own data types for
	each concept that conform to the default traits definition.  These library
	provided data types are no more than dumb containers that provide access to
	their data and rely on the generic library functions to enforce invariants and
	provide useful behaviors specific to their type of geometry that would normally
	be member functions of the data type in an OO design.  The library data
	types conform to the default traits associated with their related geometry
	concept and are registered as models of that concept.  When a data
	type has been mapped to a concept through traits it needs to be registered
	as that conceptual type with the library by
	specializing the geometry_concept meta-function.  Once mapped and
	registered, a user data type can be used interchangeably with library data types
	in the generic free functions that are overloaded on concept.<p>Traits for
	mapping a data type to a concept are broken down into mutable and read only
	traits.  Read only traits are specialized internally to work with any types
	that are refinements of a concept.  The mutable traits are defined only for
	objects that exactly model the concept.  Both read only traits and mutable
	traits need to be defined for a type to model a concept, but a type can be used
	without defining the mutable traits as long as no API that needs to modify the
	object is used with that type.  For example, a triangle type could be
	registered as a polygon_concept and the read only traits but not the mutable
	traits defined for that triangle type.  This would allow the triangle type
	to be passed into any API that expects a const reference to an object that models
	polygon.
	<p>An object that is a model of a given concept can usually be viewed as a model of any of its
	refinements if it is determined at runtime to conform to the restrictions of
	those concepts.  This concept casting is accomplished through the
	<font face="Courier New">view_as<>()</font> function.  For example if
	an object of conceptual type polygon 90 has four sides it must be a rectangle,
	and can be viewed as a rectangle with the following syntax:</p>
	<p><font face="Courier New">view_as<rectangle_concept>(polygon_90_object)</font></p>
	<p>The return value of <font face="Courier New">view_as<>()</font> can be
	passed into any interface that expects an object of the conceptual type
	specified in its template parameter.  The exception to this ability to
	concept cast geometric objects is that polygon set objects cannot be viewed as
	individual polygons or rectangles.</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="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</a>)</td>
	</tr>
	</table>

	</html>