]>
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" | |
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: 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"> --> | |
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><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 | |
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>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 /> | |
60 | </a></li> | |
61 | <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br /> | |
62 | </li> | |
63 | <li><a href="voronoi_builder.htm">Voronoi Builder</a></li> | |
64 | <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li> | |
65 | </ul> | |
66 | <h3 class="navbar">Other Resources</h3> | |
67 | <ul> | |
68 | <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> | |
69 | <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 | |
70 | Presentation</a></li> | |
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 | |
76 | Tutorial</a></li> | |
77 | </ul> | |
78 | </div> | |
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> | |
84 | </td> | |
85 | <td | |
86 | style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" | |
87 | valign="top" width="100%"> | |
88 | <!-- End Header --><br /> | |
89 | <p> | |
90 | </p> | |
91 | <h1>Connectivity Extraction</h1> | |
92 | <p> </p> | |
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 | |
106 | work.</p> | |
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%"> | |
117 | <tbody> | |
118 | <tr> | |
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> | |
122 | </tr> | |
123 | <tr> | |
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> | |
128 | </tr> | |
129 | <tr> | |
130 | <td width="586"><font face="Courier New">unsigned int <br /> | |
131 | <b>insert</b>(const | |
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> | |
135 | </tr> | |
136 | <tr> | |
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 | |
142 | node.</td> | |
143 | </tr> | |
144 | <tr> | |
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> | |
151 | </tr> | |
152 | </tbody> | |
153 | </table> | |
154 | </td> | |
155 | </tr> | |
156 | <tr> | |
157 | <td style="background-color: rgb(238, 238, 238);" nowrap="1" | |
158 | valign="top"> </td> | |
159 | <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"> | |
165 | <tr> | |
166 | <th class="docinfo-name">Copyright:</th> | |
167 |