libs/geometry/doc/doxy/doxygen_output/html_by_doxygen/robustness.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html>
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
   5 <title>Boost.Geometry (aka GGL, Generic Geometry Library)</title>
   6 <link href="doxygen.css" rel="stylesheet" type="text/css">
   7 <link href="tabs.css" rel="stylesheet" type="text/css">
   8 </head>
   9 <table cellpadding="2" width="100%">
  10 <tbody>
  11 <tr>
  12 <td valign="top">
  13 <img alt="Boost.Geometry" src="images/ggl-logo-big.png" height="80" width="200">
  14 &nbsp;&nbsp;
  15 </td>
  16 <td valign="top" align="right">
  17 <a href="http://www.boost.org">
  18 <img alt="Boost C++ Libraries" src="images/accepted_by_boost.png" height="80" width="230" border="0">
  19 </a>
  20 </td>
  21 </tr>
  22 </tbody>
  23 </table>
  24 <!-- Generated by Doxygen 1.8.6 -->
  25   <div id="navrow1" class="tabs">
  26     <ul class="tablist">
  27       <li><a href="index.html"><span>Main&#160;Page</span></a></li>
  28       <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
  29       <li><a href="modules.html"><span>Modules</span></a></li>
  30       <li><a href="namespaces.html"><span>Namespaces</span></a></li>
  31       <li><a href="annotated.html"><span>Classes</span></a></li>
  32       <li><a href="files.html"><span>Files</span></a></li>
  33       <li><a href="examples.html"><span>Examples</span></a></li>
  34     </ul>
  35   </div>
  36 </div><!-- top -->
  37 <div class="header">
  38   <div class="headertitle">
  39 <div class="title">Boost.Geometry and Robustness </div>  </div>
  40 </div><!--header-->
  41 <div class="contents">
  42 <div class="textblock"><h1><a class="anchor" id="robustness_par1"></a>
  43 Introduction</h1>
  44 <p>Floating point coordinates have limited precision. Geometry algorithms have to take this into account.</p>
  45 <p>If differences between points are very small, it may lead to false result of a mathematical calculation performed on such points, what in turn, may cause algorithm result as inadequate to actual geometric situation. For example, a point which is located left from a segment, but <b>very</b> close to it, can be reported on that segment or right from it. Also if differences are a little larger, artifacts can be shown in geometric algorithms.</p>
  46 <p>See for more backgrounds e.g.:</p>
  47 <ul>
  48 <li><a href="http://www.mpi-inf.mpg.de/~kettner/pub/nonrobust_cgta_06.pdf">Classroom Examples of Robustness Problems in Geometric Computations</a></li>
  49 <li><a href="http://groups.csail.mit.edu/graphics/classes/6.838/S98/meetings/m12/pred/m12.html">Robust Predicates and Degeneracy</a></li>
  50 </ul>
  51 <p>Boost.Geometry is aware of these issues and provides several approaches to minimize the problems, or avoid them completely using</p>
  52 <ul>
  53 <li><a href="http://en.wikipedia.org/wiki/GNU_Multi-Precision_Library">GMP</a></li>
  54 <li><a href="http://en.wikipedia.org/wiki/Class_Library_for_Numbers">CLN</a></li>
  55 </ul>
  56 <h1><a class="anchor" id="robustness_par2"></a>
  57 Example</h1>
  58 <p>An example. Consider the elongated triangle and box below.</p>
  59 <div class="image">
  60 <img src="robust_triangle_box.png" alt="robust_triangle_box.png"/>
  61 </div>
  62 <p>The left edge of the triangle has a length of about the precision of the floating point grid. It is not possible to do this intersection correctly, using floating point. No library (using floating point) can do that, by nature of float point numerical representation. It is not possible to express the four different coordinates in the resulting intersected polygon. Theoretically distinct points will be assigned to the very same location.</p>
  63 <p>Also if the left edge is longer than that, or using double coordinates, those effects will be there. And of course not only in triangles, but any spiky feature in a polygon can result in non representable coordinates or zero-length edges.</p>
  64 <h1><a class="anchor" id="robustness_par3"></a>
  65 Coordinate types</h1>
  66 <p>All geometry types provided by Boost.Geometry, and types by the user, do have a coordinate type. For example</p>
  67 <div class="fragment"><div class="line">boost::geometry::point_xy&lt;float&gt; p1;</div>
  68 <div class="line">boost::geometry::point_xy&lt;double&gt; p2;</div>
  69 <div class="line">boost::geometry::point_xy&lt;long double&gt; p3;</div>
  70 </div><!-- fragment --><p>describes three points with different coordinate types, a 32 bits <a href="http://en.wikipedia.org/wiki/Single_precision">float</a>, a 64 bits <a href="http://en.wikipedia.org/wiki/Double_precision_floating-point_format">double</a>, a <a href="http://en.wikipedia.org/wiki/Long_double">long double</a>, not standardized by IEEE and is on some machines 96 bits (using a MSVC compiler it is a synonym for a double).</p>
  71 <p>By default, algorithms select the coordinate type of the input geometries. If there are two input geometries, and they have different coordinate types, the coordinate type with the most precision is selected. This is done by the meta-function <b>select_most_precise</b>.</p>
  72 <p>Boost.Geometry supports also high precision arithmetic types, by adaption. The numeric_adaptor, used for adaption, is not part of Boost.Geometry itself but developed by us and sent (as preview) to the Boost List (as it turned out, that functionality might also be provided by Boost.Math bindings, but the mechanism is the same). Types from the following libraries are supported:</p>
  73 <ul>
  74 <li>GMP (<a href="http://gmplib.org">http://gmplib.org</a>)</li>
  75 <li>CLN (<a href="http://www.ginac.de/CLN">http://www.ginac.de/CLN</a>)</li>
  76 </ul>
  77 <p>Note that the libraries themselves are not included in Boost.Geometry, they are completely independant of each other.</p>
  78 <p>These numeric types can be used as following: </p>
  79 <div class="fragment"><div class="line">boost::geometry::point_xy&lt;boost::numeric_adaptor::gmp_value_type&gt; p4;</div>
  80 <div class="line">boost::geometry::point_xy&lt;boost::numeric_adaptor::cln_value_type&gt; p5;</div>
  81 </div><!-- fragment --><p>All algorithms using these points will use the <b>GMP</b> resp. <b>CLN</b> library for calculations.</p>
  82 <h1><a class="anchor" id="robustness_par4"></a>
  83 Calculation types</h1>
  84 <p>If high precision arithmetic types are used as shown above, coordinates are stored in these points. That is not always necessary. Therefore, Boost.Geometry provides a second approach. It is possible to specify that only the calculation is done in high precision. This is done by specifying a strategy. For example, in area:</p>
  85 <p>Example: The code below shows the calculation of the area. Points are stored in double; calculation is done using <b>GMP</b> </p>
  86 <div class="fragment"><div class="line">{</div>
  87 <div class="line">    <span class="keyword">typedef</span> boost::geometry::point_xy&lt;double&gt; point_type;</div>
  88 <div class="line">    boost::geometry::linear_ring&lt;point_type&gt; ring;</div>
  89 <div class="line">    ring.push_back(boost::geometry::make&lt;point_type&gt;(0.0, 0.0));</div>
  90 <div class="line">    ring.push_back(boost::geometry::make&lt;point_type&gt;(0.0, 0.0012));</div>
  91 <div class="line">    ring.push_back(boost::geometry::make&lt;point_type&gt;(1234567.89012345, 0.0));</div>
  92 <div class="line">    ring.push_back(ring.front());</div>
  93 <div class="line"></div>
  94 <div class="line">    <span class="keyword">typedef</span> boost::numeric_adaptor::gmp_value_type gmp;</div>
  95 <div class="line"></div>
  96 <div class="line">    gmp <a class="code" href="group__area.html#gaf7a1c34467f74f290d0b090adb27db62">area</a> = <a class="code" href="group__area.html#gaf7a1c34467f74f290d0b090adb27db62">boost::geometry::area</a>(ring, boost::geometry::strategy::area::by_triangles&lt;point_type, gmp&gt;());</div>
  97 <div class="line">    std::cout &lt;&lt; area &lt;&lt; std::endl;</div>
  98 <div class="line">}</div>
  99 </div><!-- fragment --><p>Above shows how this is used to use <b>GMP</b> or <b>CLN</b> for double coordinates. Exactly the same mechanism works (of course) also to do calculation in double, where coordinates are stored in float.</p>
 100 <h1><a class="anchor" id="robustness_par5"></a>
 101 Strategies</h1>
 102 <p>In the previous section was shown that strategies have an optional template parameter <b>CalculationType</b> so enhance precision. However, the design of Boost.Geometry also allows that the user can implement a strategy himself. In that case he can implement the necessary predicates, or use the necessary floating point types, or even go to integer and back. Whatever he prefers.</p>
 103 <h1><a class="anchor" id="robustness_par6"></a>
 104 Examples</h1>
 105 <p>We show here some things which can occur in challenging domains.</p>
 106 <p>The image below is drawn in PowerPoint to predict what would happen at an intersection of two triangles using float coordinates in the range 1e-45.</p>
 107 <div class="image">
 108 <img src="robust_float.png" alt="robust_float.png"/>
 109 </div>
 110 <p>If we perform the intersection using Boost.Geometry, we get the effect that is presented on the pictures below, using float (left) and using double (right).</p>
 111 <div class="image">
 112 <img src="robust_triangles.png" alt="robust_triangles.png"/>
 113 </div>
 114 <p>This shows how double can solve issues which might be present in float. However, there are also cases which cannot be solved by double or long double. And there are also cases which give more deviations than just a move of the intersection points.</p>
 115 <p>We investigated this and created an artificial case. In this case, there are two stars, they are the same but one of them is rotated over an interval of about 1e-44. When those stars are intersected, the current Boost.Geometry implementation using float, double or long double will give some artifacts.</p>
 116 <p>Those artifacts are caused by taking the wrong paths on points where distances are zero (because they cannot be expressed in the used coordinate systems).</p>
 117 <p>If using <b>GMP</b> or <b>CLN</b>, the intersection is correct.</p>
 118 <div class="image">
 119 <img src="robust_stars.png" alt="robust_stars.png"/>
 120 </div>
 121 <p>Note again, these things happen in differences of about 1e-45. We can investigate if they can be reduced or sometimes even solved. However, they belong to the floating point approach, which is not exact.</p>
 122 <p>For many users, this all is not relevant. Using double they will be able to do all operations without any problems or artefacts. They can occur in real life, where differences are very small, or very large. Those users can use <b>GMP</b> to use Boost.Geometry without any problem.</p>
 123 <h1><a class="anchor" id="robustness_par7"></a>
 124 Future work</h1>
 125 <p>There are several methods to avoid instability and we don't know them all, some of them might be applicable to our algorithms. Therefore is stated that Boost.Geometry is "not checked on 100% robustness". As pointed out in the discussions on the Boost mailing list in spring '09 (a.o. <em>"The dependent concept should explicitely require unlimited precision since the library specifically uses it to *guarantee* robustness. [...] Users should be left with no choice but to pick some external component fulfilling the unlimited precision requirement"</em>), it seems that it is not possible to solve all these issues using any FP number, that it is necessary to use a library as GMP or CLN for this guarantee.</p>
 126 <p>Therefore we decided to go for supporting high precision numeric types first, and they are currently supported in most algorithms (a.o. area, length, perimeter, distance, centroid, intersection, union). However, we certainly are willing to take other measures as well.</p>
 127 <h1><a class="anchor" id="robustness_par8"></a>
 128 Summary</h1>
 129 <p>Boost.Geometry approach to support high precision:</p>
 130 <ul>
 131 <li>library users can use points with float, double, or long double coordinates (the default)</li>
 132 <li>for higher numerical robustness: users can call algorithms using another calculation type (e.g. <b>GMP</b> or <b>CLN</b>, ...)</li>
 133 <li>for higher numerical robustness: users can use points with <b>GMP</b> or <b>CLN</b> coordinates</li>
 134 <li>users can implement their own implementation and provide this as a strategy, the Boost.Geometry design allows this</li>
 135 <li>other measures can be implemented, described as future work. </li>
 136 </ul>
 137 </div></div><!-- contents -->
 138 <hr size="1">
 139 <table width="100%">
 140 <tbody>
 141 <tr>
 142 <td align="left"><small>
 143 <p>April 2, 2011</p>
 144 </small></td>
 145 <td align="right">
 146 <small>
 147 Copyright &copy; 2007-2011 Barend Gehrels, Amsterdam, the Netherlands<br>
 148 Copyright &copy; 2008-2011 Bruno Lalande, Paris, France<br>
 149 Copyright &copy; 2009-2010 Mateusz Loskot, London, UK<br>
 150 </small>
 151 </td>
 152 </tr>
 153 </tbody>
 154 </table>
 155 <address style="text-align: right;"><small>
 156 Documentation is generated by&nbsp;<a href="http://www.doxygen.org/index.html">Doxygen</a>
 157 </small></address>
 158 </body>
 159 </html>