| <!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" |
| 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" lang="en"> |
| <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" /> |
| <!-- <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><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_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>Polygon Library Design Overview</h1> |
| <p> </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> |
| <img src="images/refinements.png" border="0" height="369" |
| width="466" /> |
| <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> |
| <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> |
| <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> |
| </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="table1" 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> |
