More QuadTree code.
authorDavid Gow <[email protected]>
Wed, 23 Jul 2014 04:50:48 +0000 (12:50 +0800)
committerDavid Gow <[email protected]>
Wed, 23 Jul 2014 04:50:48 +0000 (12:50 +0800)
src/document.cpp
src/document.h
src/quadtree.cpp
src/quadtree.h

index 041519c..80e0651 100644 (file)
@@ -94,6 +94,42 @@ void Document::GenBaseQuadtree()
        m_quadtree.root_id = 0;
 }
 
+QuadTreeIndex Document::GenQuadNode(QuadTreeIndex parent, QuadTreeNodeChildren type)
+{
+       QuadTreeIndex new_index = m_quadtree.nodes.size();
+       m_quadtree.nodes.push_back(QuadTreeNode{QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, QUADTREE_EMPTY, parent, type, 0, 0});
+
+       m_quadtree.nodes[new_index].object_begin = m_objects.bounds.size();
+       for (unsigned i = m_quadtree.nodes[parent].object_begin; i < m_quadtree.nodes[parent].object_end; ++i)
+       {
+               if (ContainedInQuadChild(m_objects.bounds[i], type))
+               {
+                       m_objects.bounds.push_back(TransformToQuadChild(m_objects.bounds[i], type));
+                       m_objects.types.push_back(m_objects.types[i]);
+                       m_objects.data_indices.push_back(m_objects.data_indices[i]);
+               }
+       }
+       m_quadtree.nodes[new_index].object_end = m_objects.bounds.size();
+       switch (type)
+       {
+               case QTC_TOP_LEFT:
+                       m_quadtree.nodes[parent].top_left = new_index;
+                       break;
+               case QTC_TOP_RIGHT:
+                       m_quadtree.nodes[parent].top_right = new_index;
+                       break;
+               case QTC_BOTTOM_LEFT:
+                       m_quadtree.nodes[parent].bottom_left = new_index;
+                       break;
+               case QTC_BOTTOM_RIGHT:
+                       m_quadtree.nodes[parent].bottom_right = new_index;
+                       break;
+               default:
+                       Fatal("Tried to add a QuadTree child of invalid type!");
+       }
+       return new_index;
+}
+
 #endif
 
 void Document::Load(const string & filename)
index 0f2fea1..39c6458 100644 (file)
@@ -27,6 +27,7 @@ namespace IPDF
 
 #ifndef QUADTREE_DISABLED
                        inline const QuadTree& GetQuadTree() { if (m_quadtree.root_id == QUADTREE_EMPTY) { GenBaseQuadtree(); } return m_quadtree; }
+                       QuadTreeIndex GenQuadNode(QuadTreeIndex parent, QuadTreeNodeChildren type);
 #endif
 
                private:
index 9ba2cee..e93a0f0 100644 (file)
@@ -39,6 +39,17 @@ Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
        return dst;
 }
 
+bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
+{
+       Rect std = {0,0,1,1};
+       Rect dst = TransformFromQuadChild(std, child_type);
+       if (src.x + src.w < dst.x) return false;
+       if (src.y + src.h < dst.y) return false;
+       if (src.x > dst.x + dst.w) return false;
+       if (src.y > dst.y + dst.h) return false;
+       return true;
+}
+
 }
 
 #endif
index 29d60ba..61f0a1b 100644 (file)
@@ -50,6 +50,7 @@ namespace IPDF
 
        Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
        Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
+       bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type);
 }
 
 #else

UCC git Repository :: git.ucc.asn.au