projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
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. In the example below CCoordinate is registered as a model | |
| 98 | of coordinate concept.</p> | |
| 99 | <p> <font face="Courier New">template <><br /> | |
| 100 | struct geometry_concept<CCoordinate> { 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. 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. The definition of coordinate_traits and its | |
| 108 | specialization for int are shown below.</p> | |
| 109 | <p> <font face="Courier New">template <typename T><br /> | |
| 110 | struct coordinate_traits {};<br /> | |
| 111 | <br /> | |
| 112 | template <><br /> | |
| 113 | struct coordinate_traits<int> {<br /> | |
| 114 | typedef int coordinate_type;<br /> | |
| 115 | typedef long double area_type;<br /> | |
| 116 | typedef long long manhattan_area_type;<br /> | |
| 117 | typedef unsigned long long unsigned_area_type;<br /> | |
| 118 | typedef long long coordinate_difference;<br /> | |
| 119 | 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. 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. 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. 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 <typename T><br /> | |
| 132 | struct high_precision_type {<br /> | |
| 133 | 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 <typename | |
| 138 | coordinate_type_1, typename coordinate_type_2><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. 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<128> is an example of a user defined | |
| 151 | coordinate data type that satisfies the coordinate concept. In | |
| 152 | general a data type should define std::numeric_limits and be | |
| 153 | integer-like. 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"> </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 |