geos_390_docs/classgeos_1_1shape_1_1fract...

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.11"/>
<title>GEOS: geos::shape::fractal::MortonCode Class Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">GEOS
   &#160;<span id="projectnumber">3.9.1dev</span>
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.11 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li class="current"><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="annotated.html"><span>Class&#160;List</span></a></li>
      <li><a href="inherits.html"><span>Class&#160;Hierarchy</span></a></li>
      <li><a href="functions.html"><span>Class&#160;Members</span></a></li>
    </ul>
  </div>
<div id="nav-path" class="navpath">
  <ul>
<li class="navelem"><a class="el" href="namespacegeos.html">geos</a></li><li class="navelem"><a class="el" href="namespacegeos_1_1shape.html">shape</a></li><li class="navelem"><a class="el" href="namespacegeos_1_1shape_1_1fractal.html">fractal</a></li><li class="navelem"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html">MortonCode</a></li>  </ul>
</div>
</div><!-- top -->
<div class="header">
  <div class="summary">
<a href="#pub-static-methods">Static Public Member Functions</a> &#124;
<a href="#pub-static-attribs">Static Public Attributes</a> &#124;
<a href="#pri-static-methods">Static Private Member Functions</a> &#124;
<a href="classgeos_1_1shape_1_1fractal_1_1MortonCode-members.html">List of all members</a>  </div>
  <div class="headertitle">
<div class="title">geos::shape::fractal::MortonCode Class Reference</div>  </div>
</div><!--header-->
<div class="contents">

<p><code>#include &lt;<a class="el" href="MortonCode_8h_source.html">MortonCode.h</a>&gt;</code></p>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-static-methods"></a>
Static Public Member Functions</h2></td></tr>
<tr class="memitem:a45b448560b3e255c9ddc409a2d7193a2"><td class="memItemLeft" align="right" valign="top">static uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a45b448560b3e255c9ddc409a2d7193a2">encode</a> (int x, int y)</td></tr>
<tr class="separator:a45b448560b3e255c9ddc409a2d7193a2"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a6cd61d0326b34bc1be208ee59ef5fae6"><td class="memItemLeft" align="right" valign="top">static <a class="el" href="classgeos_1_1geom_1_1Coordinate.html">geom::Coordinate</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a6cd61d0326b34bc1be208ee59ef5fae6">decode</a> (uint32_t index)</td></tr>
<tr class="separator:a6cd61d0326b34bc1be208ee59ef5fae6"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a82384b3513d4f5981649bccc7a728dcc"><td class="memItemLeft" align="right" valign="top">static uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a82384b3513d4f5981649bccc7a728dcc">levelSize</a> (uint32_t <a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a9729a4f273a232db789da021c706cdcf">level</a>)</td></tr>
<tr class="separator:a82384b3513d4f5981649bccc7a728dcc"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a479ef1436b1fb52a4a4431046b3b46d5"><td class="memItemLeft" align="right" valign="top">static uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a479ef1436b1fb52a4a4431046b3b46d5">maxOrdinate</a> (uint32_t <a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a9729a4f273a232db789da021c706cdcf">level</a>)</td></tr>
<tr class="separator:a479ef1436b1fb52a4a4431046b3b46d5"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a9729a4f273a232db789da021c706cdcf"><td class="memItemLeft" align="right" valign="top">static uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a9729a4f273a232db789da021c706cdcf">level</a> (uint32_t numPoints)</td></tr>
<tr class="separator:a9729a4f273a232db789da021c706cdcf"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-static-attribs"></a>
Static Public Attributes</h2></td></tr>
<tr class="memitem:ab75fbeb57a39a8593f8f968c10251644"><td class="memItemLeft" align="right" valign="top">static constexpr int&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#ab75fbeb57a39a8593f8f968c10251644">MAX_LEVEL</a> = 16</td></tr>
<tr class="separator:ab75fbeb57a39a8593f8f968c10251644"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pri-static-methods"></a>
Static Private Member Functions</h2></td></tr>
<tr class="memitem:a4befe024600ce6d6e9115e323efa2b65"><td class="memItemLeft" align="right" valign="top">static void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a4befe024600ce6d6e9115e323efa2b65">checkLevel</a> (uint32_t <a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a9729a4f273a232db789da021c706cdcf">level</a>)</td></tr>
<tr class="separator:a4befe024600ce6d6e9115e323efa2b65"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a9376eeaabd287c736f770d0359adf0fd"><td class="memItemLeft" align="right" valign="top">static uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a9376eeaabd287c736f770d0359adf0fd">interleave</a> (uint32_t x)</td></tr>
<tr class="separator:a9376eeaabd287c736f770d0359adf0fd"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a7b80966846b9c25b5973ce6a70623bc9"><td class="memItemLeft" align="right" valign="top">static uint32_t&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1shape_1_1fractal_1_1MortonCode.html#a7b80966846b9c25b5973ce6a70623bc9">deinterleave</a> (uint32_t x)</td></tr>
<tr class="separator:a7b80966846b9c25b5973ce6a70623bc9"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<div class="textblock"><p>Encodes points as the index along the planar Morton (Z-order) curve.</p>
<p>The planar Morton (Z-order) curve is a continuous space-filling curve. The Morton curve defines an ordering of the points in the positive quadrant of the plane. The index of a point along the Morton curve is called the Morton code.</p>
<p>A sequence of subsets of the Morton curve can be defined by a level number. Each level subset occupies a square range. The curve at level n M(n) contains 2^(n + 1) points. It fills the range square of side 2^level. Curve points have ordinates in the range [0, 2^level - 1]. The code for a given point is identical at all levels. The level simply determines the number of points in the curve subset and the size of the range square.</p>
<p>This implementation represents codes using 32-bit integers. This allows levels 0 to 16 to be handled. The class supports encoding points and decoding the point for a given code value.</p>
<p>The Morton order has the property that it tends to preserve locality. This means that codes which are near in value will have spatially proximate points. The converse is not always true - the delta between codes for nearby points is not always small. But the average delta is small enough that the Morton order is an effective way of linearizing space to support range queries.</p>
<dl class="section author"><dt>Author</dt><dd>Martin Davis</dd></dl>
<dl class="section see"><dt>See also</dt><dd><a class="el" href="classgeos_1_1shape_1_1fractal_1_1HilbertCode.html">HilbertCode</a> </dd></dl>

<p>Definition at line <a class="el" href="MortonCode_8h_source.html#l00066">66</a> of file <a class="el" href="MortonCode_8h_source.html">MortonCode.h</a>.</p>
</div><h2 class="groupheader">Member Function Documentation</h2>
<a class="anchor" id="a4befe024600ce6d6e9115e323efa2b65"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static void geos::shape::fractal::MortonCode::checkLevel </td>
          <td>(</td>
          <td class="paramtype">uint32_t&#160;</td>
          <td class="paramname"><em>level</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span><span class="mlabel">private</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="a6cd61d0326b34bc1be208ee59ef5fae6"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static <a class="el" href="classgeos_1_1geom_1_1Coordinate.html">geom::Coordinate</a> geos::shape::fractal::MortonCode::decode </td>
          <td>(</td>
          <td class="paramtype">uint32_t&#160;</td>
          <td class="paramname"><em>index</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>Computes the point on the Morton curve for a given index.</p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">index</td><td>the index of the point on the curve </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the point on the curve </dd></dl>

</div>
</div>
<a class="anchor" id="a7b80966846b9c25b5973ce6a70623bc9"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static uint32_t geos::shape::fractal::MortonCode::deinterleave </td>
          <td>(</td>
          <td class="paramtype">uint32_t&#160;</td>
          <td class="paramname"><em>x</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span><span class="mlabel">private</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="a45b448560b3e255c9ddc409a2d7193a2"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static uint32_t geos::shape::fractal::MortonCode::encode </td>
          <td>(</td>
          <td class="paramtype">int&#160;</td>
          <td class="paramname"><em>x</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">int&#160;</td>
          <td class="paramname"><em>y</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>Computes the index of the point (x,y) in the Morton curve ordering.</p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">x</td><td>the x ordinate of the point </td></tr>
    <tr><td class="paramname">y</td><td>the y ordinate of the point </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the index of the point along the Morton curve </dd></dl>

</div>
</div>
<a class="anchor" id="a9376eeaabd287c736f770d0359adf0fd"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static uint32_t geos::shape::fractal::MortonCode::interleave </td>
          <td>(</td>
          <td class="paramtype">uint32_t&#160;</td>
          <td class="paramname"><em>x</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span><span class="mlabel">private</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">

</div>
</div>
<a class="anchor" id="a9729a4f273a232db789da021c706cdcf"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static uint32_t geos::shape::fractal::MortonCode::level </td>
          <td>(</td>
          <td class="paramtype">uint32_t&#160;</td>
          <td class="paramname"><em>numPoints</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>The level of the finite Morton curve which contains at least the given number of points.</p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">numPoints</td><td>the number of points required </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the level of the curve </dd></dl>

</div>
</div>
<a class="anchor" id="a82384b3513d4f5981649bccc7a728dcc"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static uint32_t geos::shape::fractal::MortonCode::levelSize </td>
          <td>(</td>
          <td class="paramtype">uint32_t&#160;</td>
          <td class="paramname"><em>level</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>The number of points in the curve for the given level. The number of points is 2<sup>2 * level</sup>.</p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">level</td><td>the level of the curve </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the number of points </dd></dl>

</div>
</div>
<a class="anchor" id="a479ef1436b1fb52a4a4431046b3b46d5"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">static uint32_t geos::shape::fractal::MortonCode::maxOrdinate </td>
          <td>(</td>
          <td class="paramtype">uint32_t&#160;</td>
          <td class="paramname"><em>level</em></td><td>)</td>
          <td></td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>The maximum ordinate value for points in the curve for the given level. The maximum ordinate is 2<sup>level</sup> - 1.</p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">level</td><td>the level of the curve </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>the maximum ordinate value </dd></dl>

</div>
</div>
<h2 class="groupheader">Member Data Documentation</h2>
<a class="anchor" id="ab75fbeb57a39a8593f8f968c10251644"></a>
<div class="memitem">
<div class="memproto">
<table class="mlabels">
  <tr>
  <td class="mlabels-left">
      <table class="memname">
        <tr>
          <td class="memname">constexpr int geos::shape::fractal::MortonCode::MAX_LEVEL = 16</td>
        </tr>
      </table>
  </td>
  <td class="mlabels-right">
<span class="mlabels"><span class="mlabel">static</span></span>  </td>
  </tr>
</table>
</div><div class="memdoc">
<p>The maximum curve level that can be represented. </p>

<p>Definition at line <a class="el" href="MortonCode_8h_source.html#l00073">73</a> of file <a class="el" href="MortonCode_8h_source.html">MortonCode.h</a>.</p>

</div>
</div>
<hr/>The documentation for this class was generated from the following file:<ul>
<li><a class="el" href="MortonCode_8h_source.html">MortonCode.h</a></li>
</ul>
</div><!-- contents -->
<!-- start footer part -->
<hr class="footer"/><address class="footer"><small>
Generated by &#160;<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/>
</a> 1.8.11
</small></address>
</body>
</html>