diff options
Diffstat (limited to 'geometry/cellid.hpp')
-rw-r--r-- | geometry/cellid.hpp | 41 |
1 files changed, 30 insertions, 11 deletions
diff --git a/geometry/cellid.hpp b/geometry/cellid.hpp index 2af9231d7c..5f7d9964ac 100644 --- a/geometry/cellid.hpp +++ b/geometry/cellid.hpp @@ -51,7 +51,7 @@ public: { ASSERT(IsValid(), (m_bits, m_level)); ASSERT_GREATER_OR_EQUAL(m_level, level, ()); - return CellId(m_bits >> ((m_level - level) << 1), level); + return CellId(m_bits >> (2 * (m_level - level)), level); } CellId Child(int8_t c) const @@ -203,8 +203,8 @@ public: { bool operator()(CellId<DEPTH_LEVELS> const & id1, CellId<DEPTH_LEVELS> const & id2) const { - int64_t const n1 = id1.ToInt64LevelZOrder(DEPTH_LEVELS); - int64_t const n2 = id2.ToInt64LevelZOrder(DEPTH_LEVELS); + int64_t const n1 = id1.ToInt64ZOrder(DEPTH_LEVELS); + int64_t const n2 = id2.ToInt64ZOrder(DEPTH_LEVELS); ASSERT_EQUAL(n1 < n2, id1.ToString() < id2.ToString(), (id1, id2)); return n1 < n2; } @@ -214,25 +214,39 @@ public: // Numbering // Default ToInt64(). - int64_t ToInt64(int depth) const { return ToInt64LevelZOrder(depth); } + int64_t ToInt64(int depth) const { return ToInt64ZOrder(depth); } // Default FromInt64(). - static CellId FromInt64(int64_t v, int depth) { return FromInt64LevelZOrder(v, depth); } + static CellId FromInt64(int64_t v, int depth) { return FromInt64ZOrder(v, depth); } - // Level order, numbering by Z-curve. - int64_t ToInt64LevelZOrder(int depth) const + // Returns the 1-based number this cell would get in the Z-curve ordering (pre-order + // traversal of the quadtree) of all the cells in the tree of depth |depth|. + // The tree of one vertex is assumed to have depth 1. + int64_t ToInt64ZOrder(int depth) const { ASSERT(0 < depth && depth <= DEPTH_LEVELS, (m_bits, m_level, depth)); ASSERT(IsValid(), (m_bits, m_level)); if (m_level >= depth) - return AncestorAtLevel(depth - 1).ToInt64(depth); + return AncestorAtLevel(depth - 1).ToInt64ZOrder(depth); uint64_t bits = m_bits; uint64_t res = 0; - for (int i = 0; i <= m_level; ++i, bits >>= 2) + // When counting, group the nodes by their level. + // All nodes to the left of the current one at its level + // and, for every ancestor, all nodes to the left of the ancestor + // at the ancestor's level will show up earlier during the traversal. + // All ancestors are visited before the current node, so add +1 for them. + // The result is 1-based, so add +1 for the node itself too. + for (int i = 0; i <= m_level; ++i) + { res += bits + 1; + bits >>= 2; + } + // By the same reasoning, if the children of every node are ordered + // left to right, then all nodes at deeper levels that + // are strictly to the left will be visited before the current one. bits = m_bits; for (int i = m_level + 1; i < depth; ++i) { @@ -245,8 +259,10 @@ public: return static_cast<int64_t>(res); } - // Level order, numbering by Z-curve. - static CellId FromInt64LevelZOrder(int64_t v, int depth) + // Returns the CellId with the 1-based number |v| in the Z-curve ordering (pre-order + // traversal of the quadtree) of all the cells in the tree of depth |depth|. + // The tree of one vertex is assumed to have depth 1. + static CellId FromInt64ZOrder(int64_t v, int depth) { ASSERT_GREATER(v, 0, ()); ASSERT(0 < depth && depth <= DEPTH_LEVELS, (v, depth)); @@ -266,6 +282,9 @@ public: } private: + // Returns the total number of nodes in the tree of depth |depth|. + // The tree of one vertex is assumed to have depth 1. + // The first few values are 1, 5, 21, 85. static uint64_t TreeSizeForDepth(int depth) { ASSERT(0 < depth && depth <= DEPTH_LEVELS, (depth)); |