diff options
| -rw-r--r-- | city/geometry-test.lua | 41 | ||||
| -rw-r--r-- | city/geometry.lua | 21 |
2 files changed, 61 insertions, 1 deletions
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 } |