From 9cd5a9f8ac5242cd220c9bae89432e817d548b83 Mon Sep 17 00:00:00 2001
From: sanine <sanine.not@pm.me>
Date: Fri, 25 Feb 2022 12:49:31 -0600
Subject: add qt_node:find_containing()

---
 city/geometry-test.lua | 36 ++++++++++++++++++++++++++++++++++++
 city/geometry.lua      | 14 ++++++++++++++
 2 files changed, 50 insertions(+)

diff --git a/city/geometry-test.lua b/city/geometry-test.lua
index 4c61cac..98275a3 100644
--- a/city/geometry-test.lua
+++ b/city/geometry-test.lua
@@ -324,3 +324,39 @@ test(
       end
    end
 )
+
+test(
+   'find containing node for points',
+   function()
+      local node = geom.qt_node(geom.point(2, 2), 4)
+
+      node:insert(geom.point(1, 1))
+      node:insert(geom.point(0.5, 0.5))
+      node:insert(geom.point(0.25, 0.25))
+      node:insert(geom.point(0.125, 0.125))
+
+      local point = geom.point(3, 1)
+      local n = node:find_containing(point)
+      assert(n:is_leaf())
+      assert(n.square.center.x == 3)
+      assert(n.square.center.y == 1)
+
+      point = geom.point(1, 3)
+      n = node:find_containing(point)
+      assert(n:is_leaf())
+      assert(n.square.center.x == 1)
+      assert(n.square.center.y == 3)
+
+      point = geom.point(3, 3)
+      n = node:find_containing(point)
+      assert(n:is_leaf())
+      assert(n.square.center.x == 3)
+      assert(n.square.center.y == 3)
+
+      point = geom.point(0.24, 0.24)
+      n = node:find_containing(point)
+      assert(n:is_leaf())
+      assert(n.point.x == 0.25)
+      assert(n.point.y == 0.25)
+   end
+)
diff --git a/city/geometry.lua b/city/geometry.lua
index e380173..410b4a3 100644
--- a/city/geometry.lua
+++ b/city/geometry.lua
@@ -169,6 +169,20 @@ geom.qt_node = class{
       for _, child in ipairs(self.children) do
 	 child:query(region, points)
       end
+   end,
+
+   -- return the leaf node containing the given point
+   -- returns nil if no such node exists (i.e. the point
+   -- is out of bounds)
+   find_containing = function(self, point)
+      if not self.square:contains(point) then return end
+
+      if self:is_leaf() then return self end
+
+      for _, child in ipairs(self.children) do
+	 local result = child:find_containing(point)
+	 if result then return result end
+      end
    end
 }
 
-- 
cgit v1.2.1