diff options
Diffstat (limited to 'city')
| l--------- | city/.#geometry-test.lua | 1 | ||||
| -rw-r--r-- | city/geometry-test.lua | 96 | ||||
| -rw-r--r-- | city/geometry.lua | 44 | ||||
| -rw-r--r-- | city/util.lua | 37 |
4 files changed, 174 insertions, 4 deletions
diff --git a/city/.#geometry-test.lua b/city/.#geometry-test.lua deleted file mode 120000 index 4290946..0000000 --- a/city/.#geometry-test.lua +++ /dev/null @@ -1 +0,0 @@ -kate@amalthea.2265651:1645662843
\ No newline at end of file diff --git a/city/geometry-test.lua b/city/geometry-test.lua index 3227cd1..758ce95 100644 --- a/city/geometry-test.lua +++ b/city/geometry-test.lua @@ -1,5 +1,6 @@ local test = require('minunit').test local geom = require 'geometry' +local util = require 'util' -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -148,7 +149,100 @@ test( assert(node.square.center.y == 2) assert(node.square.span == 4) - assert(not node:is_leaf()) + assert(node:is_leaf()) + assert(not node.point) + end +) + +test( + 'insert points into qt_node', + function() + local center = geom.point(2, 2) + local node = geom.qt_node(center, 4) + + assert(node:is_leaf()) assert(not node.point) + + node:insert(geom.point(1, 1)) + assert(node:is_leaf()) + assert(node.point.x == 1) + assert(node.point.y == 1) + + node:insert(geom.point(3, 3)) + assert(not node:is_leaf()) + + assert(node.children[1]:is_leaf()) + assert(node.children[1].point.x == 1) + assert(node.children[1].point.y == 1) + + assert(node.children[2]:is_leaf()) + assert(not node.children[2].point) + + assert(node.children[3]:is_leaf()) + assert(not node.children[3].point) + + assert(node.children[4]:is_leaf()) + assert(node.children[4].point.x == 3) + assert(node.children[4].point.y == 3) + end +) + +test( + 'instert four points into qt_node', + function() + local center = geom.point(2, 2) + local node = geom.qt_node(center, 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)) + + assert(not node:is_leaf()) + + assert(node.children[2]:is_leaf()) + assert(not node.children[2].point) + assert(node.children[3]:is_leaf()) + assert(not node.children[3].point) + assert(node.children[4]:is_leaf()) + assert(not node.children[4].point) + + node = node.children[1].children[1] + assert(not node:is_leaf()) + + assert(not node.children[1]:is_leaf()) + assert(node.children[2]:is_leaf()) + assert(not node.children[2].point) + assert(node.children[3]:is_leaf()) + assert(not node.children[3].point) + assert(node.children[4]:is_leaf()) + assert(node.children[4].point.x == 1) + assert(node.children[4].point.y == 1) + + node = node.children[1] + assert(not node:is_leaf()) + + assert(node.children[2]:is_leaf()) + assert(not node.children[2].point) + assert(node.children[3]:is_leaf()) + assert(not node.children[3].point) + assert(node.children[4]:is_leaf()) + assert(node.children[4].point.x == 0.5) + assert(node.children[4].point.y == 0.5) + + node = node.children[1] + assert(not node:is_leaf()) + + assert(node.children[2]:is_leaf()) + assert(not node.children[2].point) + assert(node.children[3]:is_leaf()) + assert(not node.children[3].point) + assert(node.children[4]:is_leaf()) + assert(node.children[4].point.x == 0.25) + assert(node.children[4].point.y == 0.25) + + assert(node.children[1]:is_leaf()) + assert(node.children[1].point.x == 0.125) + assert(node.children[1].point.y == 0.125) end ) 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 diff --git a/city/util.lua b/city/util.lua new file mode 100644 index 0000000..49ead55 --- /dev/null +++ b/city/util.lua @@ -0,0 +1,37 @@ +local util = {} + +util.table_str = function(tbl, recursive, indent) + local tab = '\t' + + local recursive = recursive or false + local indent = indent or '' + + local str = '{' + + for key, value in pairs(tbl) do + local key_str, value_str + if type(key) == 'table' and recursive then + key_str = util.table_str(key, recursive, indent..tab) + else + key_str = tostring(key) + end + + if type(value) == 'table' and recursive then + value_str = util.table_str(value, recursive, indent..tab) + else + value_str = tostring(value) + end + + str = str .. string.format( + '\n%s%s = %s', indent..tab, + key_str, value_str) + end + + if string.len(str) > 1 then + str = str .. '\n' .. indent + end + str = str .. '}' + return str +end + +return util |