X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=blobdiff_plain;f=src%2Fquadtree.cpp;h=3d5dbeedb954a0d656d225e5b4124ca7d043bbae;hp=8474a7ff7c2c02efc3955f3d7cde823e315b3ca4;hb=326f04a375ce3120f7e8957e3d7cd5f296f513e3;hpb=7bd1c291a120559e209996a572f437cbe6f3e4a4

diff --git a/src/quadtree.cpp b/src/quadtree.cpp
index 8474a7f..3d5dbee 100644
--- a/src/quadtree.cpp
+++ b/src/quadtree.cpp
@@ -1,5 +1,6 @@
 #ifndef QUADTREE_REMOVED
 #include "quadtree.h"
+#include "document.h"
 
 namespace IPDF {
 
@@ -47,7 +48,7 @@ bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 	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;
-	Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
+	//Debug("%s is contained in %s\n", src.Str().c_str(), dst.Str().c_str());
 	return true;
 }
 
@@ -59,13 +60,13 @@ bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 	if (src.y < dst.y) return false;
 	if (src.x + src.w > dst.x + dst.w) return false;
 	if (src.y + src.h > dst.y + dst.h) return false;
-	Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
+	//Debug("%s is contained in %s... \n", src.Str().c_str(), dst.Str().c_str());
 	return true;
 }
 
 
 
-QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) const
+QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir, Document *addTo) const
 {
 	if (!xdir && !ydir) return start;
 
@@ -79,22 +80,45 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) co
 		case QTC_BOTTOM_LEFT:
 		{
 			if (nodes[start].child_type == QTC_TOP_LEFT)
+			{
 				newNode = nodes[nodes[start].parent].top_right;
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
+				}
+			}
 			else
+			{
 				newNode = nodes[nodes[start].parent].bottom_right;
-				
-			return GetNeighbour(newNode, xdir - 1, ydir);
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
+				}
+			}	
+			return GetNeighbour(newNode, xdir - 1, ydir, addTo);
 		}
 		case QTC_TOP_RIGHT:
 		case QTC_BOTTOM_RIGHT:
 		{
-			QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0);
+			QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0, addTo);
 			if (right_parent == -1) return -1;
 			if (nodes[start].child_type == QTC_TOP_RIGHT)
+			{
 				newNode = nodes[right_parent].top_left;
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(right_parent, QTC_TOP_LEFT);
+				}
+			}
 			else
+			{
 				newNode = nodes[right_parent].bottom_left;
-			return GetNeighbour(newNode, xdir - 1, ydir);
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(right_parent, QTC_BOTTOM_LEFT);
+				}
+			}
+			return GetNeighbour(newNode, xdir - 1, ydir, addTo);
 		}
 		default:
 			return -1;
@@ -111,22 +135,46 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) co
 		case QTC_BOTTOM_RIGHT:
 		{
 			if (nodes[start].child_type == QTC_TOP_RIGHT)
+			{
 				newNode = nodes[nodes[start].parent].top_left;
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
+				}
+			}
 			else
+			{
 				newNode = nodes[nodes[start].parent].bottom_left;
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
+				}
+			}
 				
-			return GetNeighbour(newNode, xdir + 1, ydir);
+			return GetNeighbour(newNode, xdir + 1, ydir, addTo);
 		}
 		case QTC_TOP_LEFT:
 		case QTC_BOTTOM_LEFT:
 		{
-			QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0);
+			QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0, addTo);
 			if (left_parent == -1) return -1;
 			if (nodes[start].child_type == QTC_TOP_LEFT)
+			{
 				newNode = nodes[left_parent].top_right;
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(left_parent, QTC_TOP_RIGHT);
+				}
+			}
 			else
+			{
 				newNode = nodes[left_parent].bottom_right;
-			return GetNeighbour(newNode, xdir + 1, ydir);
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(left_parent, QTC_BOTTOM_RIGHT);
+				}
+			}
+			return GetNeighbour(newNode, xdir + 1, ydir, addTo);
 		}
 		default:
 			return -1;
@@ -142,22 +190,45 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) co
 		case QTC_TOP_RIGHT:
 		{
 			if (nodes[start].child_type == QTC_TOP_LEFT)
+			{
 				newNode = nodes[nodes[start].parent].bottom_left;
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_LEFT);
+				}
+			}
 			else
+			{
 				newNode = nodes[nodes[start].parent].bottom_right;
-				
-			return GetNeighbour(newNode, xdir, ydir - 1);
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(nodes[start].parent, QTC_BOTTOM_RIGHT);
+				}
+			}	
+			return GetNeighbour(newNode, xdir, ydir - 1, addTo);
 		}
 		case QTC_BOTTOM_LEFT:
 		case QTC_BOTTOM_RIGHT:
 		{
-			QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1);
+			QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1, addTo);
 			if (bottom_parent == -1) return -1;
 			if (nodes[start].child_type == QTC_BOTTOM_LEFT)
+			{
 				newNode = nodes[bottom_parent].top_left;
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_LEFT);
+				}
+			}
 			else
+			{
 				newNode = nodes[bottom_parent].top_right;
-			return GetNeighbour(newNode, xdir, ydir - 1);
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(bottom_parent, QTC_TOP_RIGHT);
+				}
+			}
+			return GetNeighbour(newNode, xdir, ydir - 1, addTo);
 		}
 		default:
 			return -1;
@@ -173,22 +244,45 @@ QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) co
 		case QTC_BOTTOM_RIGHT:
 		{
 			if (nodes[start].child_type == QTC_BOTTOM_LEFT)
+			{
 				newNode = nodes[nodes[start].parent].top_left;
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_LEFT);
+				}
+			}
 			else
+			{
 				newNode = nodes[nodes[start].parent].top_right;
-				
-			return GetNeighbour(newNode, xdir, ydir + 1);
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(nodes[start].parent, QTC_TOP_RIGHT);
+				}
+			}	
+			return GetNeighbour(newNode, xdir, ydir + 1, addTo);
 		}
 		case QTC_TOP_LEFT:
 		case QTC_TOP_RIGHT:
 		{
-			QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1);
+			QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1, addTo);
 			if (top_parent == -1) return -1;
 			if (nodes[start].child_type == QTC_TOP_LEFT)
+			{
 				newNode = nodes[top_parent].bottom_left;
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_LEFT);
+				}
+			}
 			else
+			{
 				newNode = nodes[top_parent].bottom_right;
-			return GetNeighbour(newNode, xdir, ydir + 1);
+				if (addTo && newNode == -1)
+				{
+					newNode = addTo->GenQuadChild(top_parent, QTC_BOTTOM_RIGHT);
+				}
+			}
+			return GetNeighbour(newNode, xdir, ydir + 1, addTo);
 		}
 		default:
 			return -1;