ceph/src/boost/libs/polygon/doc/gtl_connectivity_extraction_45.htm

   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>Connectivity Extraction 45</li>
  54         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  55 Extraction</a></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 45</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.&nbsp; One supported graph formats is
  97 std::vector&lt;std::set&lt;int&gt; &gt; 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.&nbsp; 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&nbsp;&nbsp; The other supported graph format is
 103 std::map&lt;int, std::set&lt;int&gt; &gt; which is slightly easier to
 104 work with, but potentially more expensive.&nbsp; 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 &lt;typename
 110 coordinate_type&gt;<br />
 111 class connectivity_extraction_45;</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_45</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_45</font></b><font
 125  face="Courier New">(<br />
 126 &nbsp;&nbsp;&nbsp;&nbsp; const connectivity_extraction_45&amp; 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_45_set_data&lt;coordinate_type&gt;&amp; 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 &lt;class GeoObjT&gt;<br />
 139 unsigned int <b>insert</b>(const GeoObjT&amp; geoObj)</font></td>
 140             <td>Insert a geometry object that is a refinement of
 141 polygon 45 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 &lt;class GraphT&gt;<br />
 147 void <b>extract</b>(GraphT&amp; graph)</font></td>
 148             <td>Accepts a graph object that conforms to the
 149 expectations defined above.&nbsp; 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"> &nbsp;</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             <td>Copyright © Intel Corporation 2008-2010.</td>
 168           </tr>
 169           <tr class="field">
 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>
 177           </tr>
 178         </tbody>
 179       </table>
 180       </td>
 181     </tr>
 182   </tbody>
 183 </table>
 184 </body>
 185 </html>