]>
Commit | Line | Data |
---|---|---|
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 |