X-Git-Url: https://git.ucc.asn.au/?p=ipdf%2Fcode.git;a=blobdiff_plain;f=src%2Fquadtree.cpp;h=8474a7ff7c2c02efc3955f3d7cde823e315b3ca4;hp=e93a0f0fd839c496d92f39a765166b5d1c2712c1;hb=888817a67a9d840be66b52811b01eb77f10ff3e6;hpb=b2d6929dfb8cd94c0447b350c9bafaa573a4a834

diff --git a/src/quadtree.cpp b/src/quadtree.cpp
index e93a0f0..8474a7f 100644
--- a/src/quadtree.cpp
+++ b/src/quadtree.cpp
@@ -12,11 +12,11 @@ Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 	dst.h *= 2;
 	if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
 	{
-		dst.x -= 1;
+		dst.y -= 1;
 	}
 	if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
 	{
-		dst.y -= 1;
+		dst.x -= 1;
 	}
 	return dst;
 }
@@ -24,22 +24,22 @@ Rect TransformToQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 Rect TransformFromQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 {
 	Rect dst = src;
-	dst.x *= 0.5;
-	dst.y *= 0.5;
-	dst.w *= 0.5;
-	dst.h *= 0.5;
 	if (child_type == QTC_BOTTOM_LEFT || child_type == QTC_BOTTOM_RIGHT)
 	{
-		dst.x += 1;
+		dst.y += 1;
 	}
 	if (child_type == QTC_TOP_RIGHT || child_type == QTC_BOTTOM_RIGHT)
 	{
-		dst.y += 1;
+		dst.x += 1;
 	}
+	dst.x *= 0.5;
+	dst.y *= 0.5;
+	dst.w *= 0.5;
+	dst.h *= 0.5;
 	return dst;
 }
 
-bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
+bool IntersectsQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
 {
 	Rect std = {0,0,1,1};
 	Rect dst = TransformFromQuadChild(std, child_type);
@@ -47,9 +47,156 @@ bool ContainedInQuadChild(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());
 	return true;
 }
 
+bool ContainedInQuadChild(const Rect& src, QuadTreeNodeChildren child_type)
+{
+	Rect std = {0,0,1,1};
+	Rect dst = TransformFromQuadChild(std, child_type);
+	if (src.x < dst.x) return false;
+	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());
+	return true;
+}
+
+
+
+QuadTreeIndex QuadTree::GetNeighbour(QuadTreeIndex start, int xdir, int ydir) const
+{
+	if (!xdir && !ydir) return start;
+
+	QuadTreeIndex newNode;
+	// Try moving to the right if that's easy.
+	if (xdir > 0)
+	{
+		switch (nodes[start].child_type)
+		{
+		case QTC_TOP_LEFT:
+		case QTC_BOTTOM_LEFT:
+		{
+			if (nodes[start].child_type == QTC_TOP_LEFT)
+				newNode = nodes[nodes[start].parent].top_right;
+			else
+				newNode = nodes[nodes[start].parent].bottom_right;
+				
+			return GetNeighbour(newNode, xdir - 1, ydir);
+		}
+		case QTC_TOP_RIGHT:
+		case QTC_BOTTOM_RIGHT:
+		{
+			QuadTreeIndex right_parent = GetNeighbour(nodes[start].parent, 1, 0);
+			if (right_parent == -1) return -1;
+			if (nodes[start].child_type == QTC_TOP_RIGHT)
+				newNode = nodes[right_parent].top_left;
+			else
+				newNode = nodes[right_parent].bottom_left;
+			return GetNeighbour(newNode, xdir - 1, ydir);
+		}
+		default:
+			return -1;
+
+		}
+	}
+
+	// Try moving to the left.
+	if (xdir < 0)
+	{
+		switch (nodes[start].child_type)
+		{
+		case QTC_TOP_RIGHT:
+		case QTC_BOTTOM_RIGHT:
+		{
+			if (nodes[start].child_type == QTC_TOP_RIGHT)
+				newNode = nodes[nodes[start].parent].top_left;
+			else
+				newNode = nodes[nodes[start].parent].bottom_left;
+				
+			return GetNeighbour(newNode, xdir + 1, ydir);
+		}
+		case QTC_TOP_LEFT:
+		case QTC_BOTTOM_LEFT:
+		{
+			QuadTreeIndex left_parent = GetNeighbour(nodes[start].parent, -1, 0);
+			if (left_parent == -1) return -1;
+			if (nodes[start].child_type == QTC_TOP_LEFT)
+				newNode = nodes[left_parent].top_right;
+			else
+				newNode = nodes[left_parent].bottom_right;
+			return GetNeighbour(newNode, xdir + 1, ydir);
+		}
+		default:
+			return -1;
+		}
+	}
+	
+	// Try moving to the bottom.
+	if (ydir > 0)
+	{
+		switch (nodes[start].child_type)
+		{
+		case QTC_TOP_LEFT:
+		case QTC_TOP_RIGHT:
+		{
+			if (nodes[start].child_type == QTC_TOP_LEFT)
+				newNode = nodes[nodes[start].parent].bottom_left;
+			else
+				newNode = nodes[nodes[start].parent].bottom_right;
+				
+			return GetNeighbour(newNode, xdir, ydir - 1);
+		}
+		case QTC_BOTTOM_LEFT:
+		case QTC_BOTTOM_RIGHT:
+		{
+			QuadTreeIndex bottom_parent = GetNeighbour(nodes[start].parent, 0, 1);
+			if (bottom_parent == -1) return -1;
+			if (nodes[start].child_type == QTC_BOTTOM_LEFT)
+				newNode = nodes[bottom_parent].top_left;
+			else
+				newNode = nodes[bottom_parent].top_right;
+			return GetNeighbour(newNode, xdir, ydir - 1);
+		}
+		default:
+			return -1;
+		}
+	}
+
+	// Try moving up, towards the sky.
+	if (ydir < 0)
+	{
+		switch (nodes[start].child_type)
+		{
+		case QTC_BOTTOM_LEFT:
+		case QTC_BOTTOM_RIGHT:
+		{
+			if (nodes[start].child_type == QTC_BOTTOM_LEFT)
+				newNode = nodes[nodes[start].parent].top_left;
+			else
+				newNode = nodes[nodes[start].parent].top_right;
+				
+			return GetNeighbour(newNode, xdir, ydir + 1);
+		}
+		case QTC_TOP_LEFT:
+		case QTC_TOP_RIGHT:
+		{
+			QuadTreeIndex top_parent = GetNeighbour(nodes[start].parent, 0, -1);
+			if (top_parent == -1) return -1;
+			if (nodes[start].child_type == QTC_TOP_LEFT)
+				newNode = nodes[top_parent].bottom_left;
+			else
+				newNode = nodes[top_parent].bottom_right;
+			return GetNeighbour(newNode, xdir, ydir + 1);
+		}
+		default:
+			return -1;
+		}
+	}
+	return -1;
+}
+
 }
 
 #endif