| 90 | |
| 91 | template <typename pT, typename CTYPE = float> |
| 92 | class DynamicQuadTree |
| 93 | { |
| 94 | public: |
| 95 | DynamicQuadTree(const geom2d::rect<CTYPE>& size, const size_t nDepth = 0, const size_t nMaxDepth = 8) |
| 96 | { |
| 97 | m_depth = nDepth; |
| 98 | m_rect = size; |
| 99 | m_maxdepth = nMaxDepth; |
| 100 | resize(m_rect); |
| 101 | } |
| 102 | |
| 103 | // Insert a region into this area |
| 104 | QuadTreeItemLocation<pT> insert(const pT item, const geom2d::rect<CTYPE>& itemsize) |
| 105 | { |
| 106 | for (int i = 0; i < 4; i++) |
| 107 | { |
| 108 | if (geom2d::contains(m_rChild[i], itemsize)) |
| 109 | { |
| 110 | // Have we reached depth limit? |
| 111 | if (m_depth + 1 < m_maxdepth) |
| 112 | { |
| 113 | // No, so does child exist? |
| 114 | if (!m_pChild[i]) |
| 115 | { |
| 116 | // No, so create it |
| 117 | m_pChild[i] = std::make_shared<DynamicQuadTree<pT>>(m_rChild[i], m_depth + 1, m_maxdepth); |
| 118 | } |
| 119 | |
| 120 | // Yes, so add item to it |
| 121 | return m_pChild[i]->insert(item, itemsize); |
| 122 | } |
| 123 | } |
| 124 | } |
| 125 | |
| 126 | // It didnt fit, so item must belong to this geom2d::rect<CTYPE> |
| 127 | m_pItems.push_back({ itemsize, item }); |
| 128 | return { &m_pItems, std::prev(m_pItems.end()) }; |
| 129 | } |
| 130 | |
| 131 | void relocate(pT item, const geom2d::rect<CTYPE>& rArea) |
| 132 | { |
| 133 | // Remove it |
| 134 | remove(item); |
| 135 | |
| 136 | // Reinsert it with new location |
| 137 | insert(item, rArea); |
| 138 | } |
| 139 | |
| 140 | size_t size() const |
| 141 | { |
| 142 | size_t nCount = m_pItems.size(); |
| 143 | for (int i = 0; i < 4; i++) |
| 144 | if (m_pChild[i]) nCount += m_pChild[i]->size(); |
| 145 | return nCount; |
| 146 | } |
| 147 | |
| 148 | void search(const geom2d::rect<CTYPE>& rArea, std::list<pT>& listItems) const |
| 149 | { |
nothing calls this directly
no outgoing calls
no test coverage detected