ceph/src/boost/libs/polygon/doc/gtl_coordinate_concept.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: Coordinate Concept</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>Coordinate Concept</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>Coordinate Concept</h1>
  93       <p> The coordinate concept tag is <font face="Courier New">
  94 coordinate_concept</font></p>
  95       <p> To register a user defined type as a model of coordinate
  96 concept, specialize the geometry concept meta-function for that
  97 type.&nbsp; In the example below CCoordinate is registered as a model
  98 of coordinate concept.</p>
  99       <p> <font face="Courier New">template &lt;&gt;<br />
 100 struct geometry_concept&lt;CCoordinate&gt; { typedef coordinate_concept
 101 type; };</font></p>
 102       <p> The coordinate type is expected to be integral and built-in
 103 numerical data types such as float and int already have concept type
 104 traits specializations in the library.&nbsp; In the coordinate traits
 105 are type definitions for related types are provided to allow the
 106 library to choose the best type to cast to under various
 107 circumstances.&nbsp; The definition of coordinate_traits and its
 108 specialization for int are shown below.</p>
 109       <p> <font face="Courier New">template &lt;typename T&gt;<br />
 110 struct coordinate_traits {};<br />
 111       <br />
 112 template &lt;&gt;<br />
 113 struct coordinate_traits&lt;int&gt; {<br />
 114 &nbsp;&nbsp;&nbsp;&nbsp; typedef int coordinate_type;<br />
 115 &nbsp;&nbsp;&nbsp;&nbsp; typedef long double area_type;<br />
 116 &nbsp;&nbsp;&nbsp;&nbsp; typedef long long manhattan_area_type;<br />
 117 &nbsp;&nbsp;&nbsp;&nbsp; typedef unsigned long long unsigned_area_type;<br />
 118 &nbsp;&nbsp;&nbsp;&nbsp; typedef long long coordinate_difference;<br />
 119 &nbsp;&nbsp;&nbsp;&nbsp; typedef long double coordinate_distance;<br />
 120 };</font></p>
 121       <p> By making use of the coordinate traits of int the library is
 122 able to avoid overflow and handle the normal issues encountered when
 123 programming integer geometry.&nbsp; For the out of the ordinary issues
 124 there is a special meta-function that provides the library with a
 125 numerical type suitable for exact numerical calculations.&nbsp; It
 126 defaults to the highest precision data type available in most
 127 compilers, long double, but can be overridden by specializing for a
 128 particular coordinate type.&nbsp; Use of gmp multi-precision rational
 129 or similar data type is recommended for numerically robust calculations
 130 in the general polygon algorithms.</p>
 131       <p> <font face="Courier New">template &lt;typename T&gt;<br />
 132 struct high_precision_type {<br />
 133 &nbsp;&nbsp;&nbsp;&nbsp; typedef long double type;<br />
 134 };</font></p>
 135       <p> There is only one generic function on coordinate concepts,
 136 Euclidean distance.</p>
 137       <p> <font face="Courier New">template &lt;typename
 138 coordinate_type_1, typename coordinate_type_2&gt;<br />
 139 coordinate_difference euclidean_distance(coordinate_type_1,
 140 coordinate_type_2)</font></p>
 141       <p> This function returns the absolution value of the difference
 142 between the two coordinates.</p>
 143       <p> Note: older versions of the stl define a fully generic
 144 distance(T, T) function for computing the difference between two
 145 iterators.&nbsp; We were forced to name our distance function
 146 euclidean_distance to avoid name collision.</p>
 147       <p> The
 148       <a
 149  href="http://www.mentor.com/products/esl/high_level_synthesis/ac_datatypes">
 150 Algorithmic C</a> ac_int&lt;128&gt; is an example of a user defined
 151 coordinate data type that satisfies the coordinate concept.&nbsp; In
 152 general a data type should define std::numeric_limits and be
 153 integer-like.&nbsp; Floating point coordinate types are not supported
 154 by all the algorithms and generally not suitable for use with the
 155 library at present.</p>
 156       </td>
 157     </tr>
 158     <tr>
 159       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
 160  valign="top"> &nbsp;</td>
 161       <td
 162  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 163  valign="top" width="100%">
 164       <table class="docinfo" id="table1" frame="void" rules="none">
 165         <colgroup> <col class="docinfo-name" /><col
 166  class="docinfo-content" /> </colgroup> <tbody valign="top">
 167           <tr>
 168             <th class="docinfo-name">Copyright:</th>
 169             <td>Copyright © Intel Corporation 2008-2010.</td>
 170           </tr>
 171           <tr class="field">
 172             <th class="docinfo-name">License:</th>
 173             <td class="field-body">Distributed under the Boost Software
 174 License, Version 1.0. (See accompanying file <tt class="literal"> <span
 175  class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
 176  class="reference" target="_top"
 177  href="http://www.boost.org/LICENSE_1_0.txt">
 178 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 179           </tr>
 180         </tbody>
 181       </table>
 182       </td>
 183     </tr>
 184   </tbody>
 185 </table>
 186 </body>
 187 </html>