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">
8 Copyright 2009-2010 Intel Corporation
11 <title>Boost Polygon Library: Connectivity Extraction
45</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"> -->
16 <table style=
"margin: 0pt; padding: 0pt; width: 100%;" border=
"0"
17 cellpadding=
"0" cellspacing=
"0">
20 <td style=
"background-color: rgb(238, 238, 238);" nowrap=
"1"
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>
29 <li><a href=
"index.htm">Boost.Polygon Main Page
</a></li>
30 <li><a href=
"gtl_design_overview.htm">Design Overview
</a></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
48 <li><a href=
"gtl_polygon_45_set_concept.htm">Polygon
45 Set
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>Connectivity Extraction
</li>
56 <li><a href=
"gtl_property_merge_90.htm">Property Merge
90</a></li>
57 <li><a href=
"gtl_property_merge_45.htm">Property Merge
45</a></li>
58 <li><a href=
"gtl_property_merge.htm">Property Merge
</a></li>
59 <li><a href=
"voronoi_main.htm">Voronoi Main Page
<br />
61 <li><a href=
"voronoi_benchmark.htm">Voronoi Benchmark
</a><br />
63 <li><a href=
"voronoi_builder.htm">Voronoi Builder
</a></li>
64 <li><a href=
"voronoi_diagram.htm">Voronoi Diagram
</a></li>
66 <h3 class=
"navbar">Other Resources
</h3>
68 <li><a href=
"GTL_boostcon2009.pdf">GTL Boostcon
2009 Paper
</a></li>
69 <li><a href=
"GTL_boostcon_draft03.pdf">GTL Boostcon
2009
71 <li><a href=
"analysis.htm">Performance Analysis
</a></li>
72 <li><a href=
"gtl_tutorial.htm">Layout Versus Schematic Tutorial
</a></li>
73 <li><a href=
"gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial
</a></li>
74 <li><a href=
"voronoi_basic_tutorial.htm">Voronoi Basic Tutorial
</a></li>
75 <li><a href=
"voronoi_advanced_tutorial.htm">Voronoi Advanced
79 <h3 class=
"navbar">Polygon Sponsor
</h3>
80 <div style=
"padding: 5px;" align=
"center"> <img
81 src=
"images/intlogo.gif" border=
"0" height=
"51" width=
"127" /><a
82 title=
"www.adobe.com home page" href=
"http://www.adobe.com/"
83 tabindex=
"2" style=
"border: medium none ;"> </a> </div>
86 style=
"padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
87 valign=
"top" width=
"100%">
88 <!-- End Header --><br />
91 <h1>Connectivity Extraction
</h1>
93 <p>The connectivity extraction algorithm constructs the
94 connectivity graph where input polygon sets are modeled as graph nodes
95 and assigned node ids and overlap/touching between input polygon sets
96 is modeled as graph edges.
One supported graph formats is
97 std::vector
<std::set
<int
> > where node ids index into the
98 vector and the sets of integers at each index are the ids of nodes for
99 which an edge exists in the graph.
It is required that such
100 vector pre-allocate sufficient elements to store the graph generated by
101 the algorithm, because only the operator[] is used internally to access
102 the graph
The other supported graph format is
103 std::map
<int, std::set
<int
> > which is slightly easier to
104 work with, but potentially more expensive.
Improving the
105 interface to support more generic graph concepts is deferred to future
107 <p>The following is the declaration of the connectivity
108 extraction algorithm.
</p>
109 <p><font face=
"Courier New">template
<typename
110 coordinate_type
><br />
111 class connectivity_extraction;
</font></p>
112 <p>Example code
<a href=
"gtl_connectivity_extraction_usage.htm">connectivity_extraction_usage.cpp
</a>
113 demonstrates using the connectivity extraction algorithm to build a
114 connectivity graph on geometry.
</p>
115 <h2>Member Functions
</h2>
116 <table id=
"table1" border=
"1" width=
"100%">
119 <td width=
"586"><b><font face=
"Courier New">connectivity_extraction
</font></b><font
120 face=
"Courier New">()
</font></td>
121 <td>Default constructor.
</td>
124 <td width=
"586"><b><font face=
"Courier New">connectivity_extraction
</font></b><font
125 face=
"Courier New">(
<br />
126 const connectivity_extraction
& that)
</font></td>
127 <td>Copy construct.
</td>
130 <td width=
"586"><font face=
"Courier New">unsigned int
<br />
132 polygon_set_data
<coordinate_type
>& ps)
</font></td>
133 <td>I
<font face=
"Times New Roman">nsert a polygon set graph
134 node, the value returned is the id of the graph node.
</font></td>
137 <td width=
"586"><font face=
"Courier New">
138 template
<class GeoObjT
><br />
139 unsigned int
<b>insert
</b>(const GeoObjT
& geoObj)
</font></td>
140 <td>Insert a geometry object that is a refinement of
141 polygon set as a graph node, the return value is the id of the graph
145 <td width=
"586"><font face=
"Courier New">
146 template
<class GraphT
><br />
147 void
<b>extract
</b>(GraphT
& graph)
</font></td>
148 <td>Accepts a graph object that conforms to the
149 expectations defined above.
Performs connectivity extraction and
150 populates the graph object.
</td>
157 <td style=
"background-color: rgb(238, 238, 238);" nowrap=
"1"
158 valign=
"top"> </td>
160 style=
"padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
161 valign=
"top" width=
"100%">
162 <table class=
"docinfo" id=
"table2" frame=
"void" rules=
"none">
163 <colgroup> <col class=
"docinfo-name" /><col
164 class=
"docinfo-content" /> </colgroup> <tbody valign=
"top">
166 <th class=
"docinfo-name">Copyright:
</th>
167 <td>Copyright © Intel Corporation
2008-
2010.
</td>
170 <th class=
"docinfo-name">License:
</th>
171 <td class=
"field-body">Distributed under the Boost Software
172 License, Version
1.0. (See accompanying file
<tt class=
"literal"> <span
173 class=
"pre">LICENSE_1_0.txt
</span></tt> or copy at
<a
174 class=
"reference" target=
"_top"
175 href=
"http://www.boost.org/LICENSE_1_0.txt">
176 http://www.boost.org/LICENSE_1_0.txt
</a>)
</td>