add multi-recursion insert test

1 files changed, 42 insertions, 2 deletions

diff --git a/city/geometry.lua b/city/geometry.lua
index 78c2aa7..5893731 100644
--- a/city/geometry.lua
+++ b/city/geometry.lua
@@ -96,9 +96,49 @@ geom.qt_node = class{
    end,
 
    is_leaf = function(self)
-      if self.children then return true end
-      return false
+      if self.children then return false end
+      return true
    end,
+
+   insert = function(self, point)
+      if not self.square:contains(point) then
+	 -- point isn't even in this region
+	 return false
+      end
+      
+      if self:is_leaf() and not self.point then
+	 -- no preexisting point, just store it
+	 self.point = point
+	 return true
+      end
+
+      if self:is_leaf() then
+	 -- subdivide and re-insert original point
+	 -- and then insert new point again
+	 local self_point = self.point
+	 self.point = nil
+	 self.children = {}
+	 local this = getmetatable(self).__index
+	 local child_regions = self.square:divide()
+	 for _, region in ipairs(child_regions) do
+	    table.insert(
+	       self.children,
+	       this(region.center, region.span)
+	    )
+	 end
+	 self:insert(self_point)
+	 self:insert(point)
+	 return true
+      end
+
+      -- not a leaf node
+      for _, child in ipairs(self.children) do
+	 if child:insert(point) then return true end
+      end
+
+      -- should never get here
+      return false
+   end
 }
 
 return geom