]>
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" | |
3 | xmlns:v="urn:schemas-microsoft-com:vml" | |
4 | xmlns:o="urn:schemas-microsoft-com:office:office" | |
5 | xmlns:(null)1="http://www.w3.org/TR/REC-html40" lang="en"> | |
6 | <head> | |
7 | <!-- | |
8 | Copyright 2009-2010 Intel Corporation | |
9 | license banner | |
10 | --> | |
11 | <title>Boost Polygon Library: Overview</title> | |
12 | <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" /> | |
13 | <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> --> | |
14 | </head> | |
15 | <body> | |
16 | <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" | |
17 | cellpadding="0" cellspacing="0"> | |
18 | <tbody> | |
19 | <tr> | |
20 | <td style="background-color: rgb(238, 238, 238);" nowrap="1" | |
21 | valign="top"> | |
22 | <div style="padding: 5px;" align="center"> <img | |
23 | src="images/boost.png" border="0" height="86" width="277" /><a | |
24 | title="www.boost.org home page" href="http://www.boost.org/" | |
25 | tabindex="2" style="border: medium none ;"> </a> </div> | |
26 | <div style="margin: 5px;"> | |
27 | <h3 class="navbar">Contents</h3> | |
28 | <ul> | |
29 | <li><a href="index.htm">Boost.Polygon Main Page</a></li> | |
30 | <li>Design Overview</li> | |
31 | <li><a href="gtl_isotropy.htm">Isotropy</a></li> | |
32 | <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li> | |
33 | <li><a href="gtl_interval_concept.htm">Interval Concept</a></li> | |
34 | <li> <a href="gtl_point_concept.htm">Point Concept</a></li> | |
35 | <li><a href="gtl_segment_concept.htm">Segment Concept</a></li> | |
36 | <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li> | |
37 | <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li> | |
38 | <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 | |
39 | With Holes Concept</a></li> | |
40 | <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li> | |
41 | <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 | |
42 | With Holes Concept</a></li> | |
43 | <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li> | |
44 | <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With | |
45 | Holes Concept</a></li> | |
46 | <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set | |
47 | Concept</a></li> | |
48 | <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set | |
49 | Concept</a></li> | |
50 | <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li> | |
51 | <li><a href="gtl_connectivity_extraction_90.htm">Connectivity | |
52 | Extraction 90</a></li> | |
53 | <li><a href="gtl_connectivity_extraction_45.htm">Connectivity | |
54 | Extraction 45</a></li> | |
55 | <li><a href="gtl_connectivity_extraction.htm">Connectivity | |
56 | Extraction</a></li> | |
57 | <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li> | |
58 | <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li> | |
59 | <li><a href="gtl_property_merge.htm">Property Merge</a></li> | |
60 | <li><a href="voronoi_main.htm">Voronoi Main Page<br /> | |
61 | </a></li> | |
62 | <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br /> | |
63 | </li> | |
64 | <li><a href="voronoi_builder.htm">Voronoi Builder</a></li> | |
65 | <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li> | |
66 | </ul> | |
67 | <h3 class="navbar">Other Resources</h3> | |
68 | <ul> | |
69 | <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> | |
70 | <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 | |
71 | Presentation</a></li> | |
72 | <li><a href="analysis.htm">Performance Analysis</a></li> | |
73 | <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li> | |
74 | <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li> | |
75 | <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li> | |
76 | <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced | |
77 | Tutorial</a></li> | |
78 | </ul> | |
79 | </div> | |
80 | <h3 class="navbar">Polygon Sponsor</h3> | |
81 | <div style="padding: 5px;" align="center"> <img | |
82 | src="images/intlogo.gif" border="0" height="51" width="127" /><a | |
83 | title="www.adobe.com home page" href="http://www.adobe.com/" | |
84 | tabindex="2" style="border: medium none ;"> </a> </div> | |
85 | </td> | |
86 | <td | |
87 | style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" | |
88 | valign="top" width="100%"> | |
89 | <!-- End Header --><br /> | |
90 | <p> | |
91 | </p> | |
92 | <h1>Polygon Library Design Overview</h1> | |
93 | <p> </p> | |
94 | <p>The Polygon library uses C++-Concepts inspired template | |
95 | programming to provide generic library functions overloaded on concept | |
96 | type. There are currently thirteen concepts in the Polygon | |
97 | library type system. A concept object in the Polygon library is | |
98 | just an empty struct similar to a tag that would be used for tag | |
99 | dispatching. These concepts are shown in the refinement | |
100 | diagram below.</p> | |
101 | <img src="images/refinements.png" border="0" height="369" | |
102 | width="466" /> | |
103 | <p>The arrows between diagram bubbles show concept refinement | |
104 | relationships. This is similar, but not identical to, inheritance | |
105 | relationships between normal classes. A refinement of a concept | |
106 | narrows down the definition of a more general concept. For | |
107 | example, the rectangle concept is a refinement of a polygon concept | |
108 | because it restricts the polygon to a four sided, axis-parallel, | |
109 | rectilinear figure. A refinement of a concept is always | |
110 | acceptable to an API that expects read only access to a given concept, | |
111 | but never acceptable to an API that expects to write to that | |
112 | concept. There are three types of geometry in the polygon | |
113 | library, the general case, the case restricted to angles that are | |
114 | multiples of 45 degrees, and the Manhattan/rectilinear case where | |
115 | angles are restricted to multiples of 90 degrees. The | |
116 | refinement diagram shows that 90 degree concepts are refinements of 45 | |
117 | degree concepts, which are themselves refinements of the general | |
118 | case. This allows the compiler to choose between the three | |
119 | implementations of algorithms to select the best algorithm for the | |
120 | conceptual data types passed to an overload of a function including | |
121 | heterogeneous combinations of 90, 45 and general case geometry. | |
122 | To provide the | |
123 | <font face="Courier New">operator&</font> that performs the | |
124 | intersection on any pair of objects from the ten conceptual types | |
125 | related to each other through refinement in the diagraph above fully | |
126 | one hundred distinct combinations of conceptual types are supported by | |
127 | the library, but only three overloads are required to implement the | |
128 | operator (one for 90, one for 45 and one for arbitrary angle version of | |
129 | the intersection operation) because refinement generalizes the | |
130 | implementation of the interface. In this way a fully symmetric, | |
131 | complete and internally consistent API is implemented to provide | |
132 | meaningful and correct behaviors for all combinations of argument types | |
133 | in all APIs where those types make sense. For example, it doesn't | |
134 | make sense to copy data from a polygon into a rectangle, so attempting | |
135 | to do so yields a syntax error, while copying a rectangle into a | |
136 | polygon does make sense. The <font face="Courier New"> | |
137 | assign()</font> function that is used to copy geometry data between | |
138 | concepts instantiates for the 49 combinations of concepts that make | |
139 | sense, but not for the 51 combinations that are illegal. The | |
140 | syntax error you will see when attempting an illegal assign operation | |
141 | is simple and clear because use of SFINAE by the library to overload | |
142 | generic functions means no matching function is found by the compiler | |
143 | in cases where no overload is provided.</p> | |
144 | <p> | |
145 | <font face="Courier New">error: no matching function for call to | |
146 | 'assign(rectangle_data<int>&, polygon_data<int>&)'</font></p> | |
147 | <p>Associated with each concept is a traits struct that generally | |
148 | must be specialized for a given data type to provide the concept | |
149 | mapping between the interfaces of the data type and the expected | |
150 | behaviors of an object of that type required by the library. The | |
151 | library also provides its own data types for each concept that conform | |
152 | to the default traits definition. These library provided data | |
153 | types are no more than dumb containers that provide access to their | |
154 | data and rely on the generic library functions to enforce invariants | |
155 | and provide useful behaviors specific to their type of geometry that | |
156 | would normally be member functions of the data type in an OO | |
157 | design. The library data types conform to the default traits | |
158 | associated with their related geometry concept and are registered as | |
159 | models of that concept. When a data type has been mapped to a | |
160 | concept through traits it needs to be registered as that conceptual | |
161 | type with the library by specializing the geometry_concept | |
162 | meta-function. Once mapped and registered, a user data type can | |
163 | be used interchangeably with library data types in the generic free | |
164 | functions that are overloaded on concept.</p> | |
165 | <p>Traits for mapping a data type to a concept are broken down | |
166 | into mutable and read only traits. Read only traits are | |
167 | specialized internally to work with any types that are refinements of a | |
168 | concept. The mutable traits are defined only for objects that | |
169 | exactly model the concept. Both read only traits and mutable | |
170 | traits need to be defined for a type to model a concept, but a type can | |
171 | be used without defining the mutable traits as long as no API that | |
172 | needs to modify the object is used with that type. For example, a | |
173 | triangle type could be registered as a polygon_concept and the read | |
174 | only traits but not the mutable traits defined for that triangle | |
175 | type. This would allow the triangle type to be passed into any | |
176 | API that expects a const reference to an object that models | |
177 | polygon. </p> | |
178 | <p>An object that is a model of a given concept can usually be | |
179 | viewed as a model of any of its refinements if it is determined at | |
180 | runtime to conform to the restrictions of those concepts. This | |
181 | concept casting is accomplished through the | |
182 | <font face="Courier New">view_as<>()</font> function. | |
183 | For example if an object of conceptual type polygon 90 has four sides | |
184 | it must be a rectangle, and can be viewed as a rectangle with the | |
185 | following syntax:</p> | |
186 | <p><font face="Courier New">view_as<rectangle_concept>(polygon_90_object)</font></p> | |
187 | <p>The return value of <font face="Courier New">view_as<>()</font> | |
188 | can be passed into any interface that expects an object of the | |
189 | conceptual type specified in its template parameter. The | |
190 | exception to this ability to concept cast geometric objects is that | |
191 | polygon set objects cannot be viewed as individual polygons or | |
192 | rectangles.</p> | |
193 | </td> | |
194 | </tr> | |
195 | <tr> | |
196 | <td style="background-color: rgb(238, 238, 238);" nowrap="1" | |
197 | valign="top"> </td> | |
198 | <td | |
199 | style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" | |
200 | valign="top" width="100%"> | |
201 | <table class="docinfo" id="table1" frame="void" rules="none"> | |
202 | <colgroup> <col class="docinfo-name" /><col | |
203 | class="docinfo-content" /> </colgroup> <tbody valign="top"> | |
204 | <tr> | |
205 | <th class="docinfo-name">Copyright:</th> | |
206 |