From 342bc7a8caac79c28fc1c430926ea63d486303fa Mon Sep 17 00:00:00 2001
From: sanine <sanine.not@pm.me>
Date: Fri, 25 Feb 2022 12:00:54 -0600
Subject: add qt_node:query()

---
 city/geometry-test.lua | 41 +++++++++++++++++++++++++++++++++++++++++
 city/geometry.lua      | 21 ++++++++++++++++++++-
 2 files changed, 61 insertions(+), 1 deletion(-)

diff --git a/city/geometry-test.lua b/city/geometry-test.lua
index d48abbc..4c61cac 100644
--- a/city/geometry-test.lua
+++ b/city/geometry-test.lua
@@ -283,3 +283,44 @@ test(
       assert(node.children[1].point.y == 0.125)
    end
 )
+
+test(
+   'query qt_node with square',
+   function()
+      local node = geom.qt_node(geom.point(2, 2), 4)
+
+      local x0 = 0.5
+      local y0 = 0.5
+      for x = 0,3 do
+	 for y = 0,3 do
+	    node:insert(geom.point(x0 + x, y0 + y))
+	 end
+      end
+
+      local query_region = geom.square(geom.point(2, 2), 2)
+      local points = {}
+      node:query(query_region, points)
+
+      local expected_points = {
+	 geom.point(1.5, 1.5),
+	 geom.point(2.5, 1.5),
+	 geom.point(1.5, 2.5),
+	 geom.point(2.5, 2.5),
+      }
+
+      local is_expected = function(point)
+	 for _, pt in ipairs(expected_points) do
+	    if (point.x == pt.x) and (point.y == pt.y) then
+	       return true
+	    end
+	 end
+	 return false
+      end
+
+      assert(#points == 4)
+
+      for _, point in ipairs(points) do
+	 assert(is_expected(point))
+      end
+   end
+)
diff --git a/city/geometry.lua b/city/geometry.lua
index a24e508..e380173 100644
--- a/city/geometry.lua
+++ b/city/geometry.lua
@@ -89,7 +89,7 @@ geom.square = class{
 	 this(geom.point(x-d, y+d), d*2),
 	 this(geom.point(x+d, y+d), d*2),
       }
-   end
+   end,
 }
 
 
@@ -150,6 +150,25 @@ geom.qt_node = class{
 
       -- should never get here
       return false
+   end,
+
+   -- append any points within the supplied region under
+   -- the current node to the supplied array
+   query = function(self, region, points)
+      -- don't do anything if there's no intersection
+      if not self.square:intersects(region) then return end
+
+      if self:is_leaf() then
+	 if self.point and region:contains(self.point) then
+	    table.insert(points, self.point)
+	 end
+	 return
+      end
+
+      -- not a leaf node, recursively query children
+      for _, child in ipairs(self.children) do
+	 child:query(region, points)
+      end
    end
 }
 
-- 
cgit v1.2.1