summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--city/geometry-test.lua41
-rw-r--r--city/geometry.lua21
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
}