diff options
| -rw-r--r-- | city/geometry-test.lua | 36 | ||||
| -rw-r--r-- | city/geometry.lua | 14 |
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 } |