summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--city/geometry-test.lua36
-rw-r--r--city/geometry.lua14
2 files changed, 50 insertions, 0 deletions
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
}