summaryrefslogtreecommitdiff
path: root/city/geometry-test.lua
diff options
context:
space:
mode:
Diffstat (limited to 'city/geometry-test.lua')
-rw-r--r--city/geometry-test.lua58
1 files changed, 58 insertions, 0 deletions
diff --git a/city/geometry-test.lua b/city/geometry-test.lua
index 98275a3..28d55bc 100644
--- a/city/geometry-test.lua
+++ b/city/geometry-test.lua
@@ -360,3 +360,61 @@ test(
assert(n.point.y == 0.25)
end
)
+
+
+-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+--
+-- geom.quadtree
+--
+-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+test(
+ 'use quadtree to find closest points',
+ function()
+ local tree = geom.quadtree(w, h)
+
+ local N = 1000
+
+ -- insert N random points
+ local points = {}
+ for i=1,N do
+ local point = geom.point(math.random(), math.random())
+ table.insert(points, point)
+ tree:insert(point)
+ end
+
+ local find_closest = function(point)
+ local dist = math.huge
+ local closest
+ for _, pt in ipairs(points) do
+ if point:distance_to(pt) < dist then
+ dist = point:distance_to(pt)
+ closest = pt
+ end
+ end
+ return closest
+ end
+
+ -- check closest for N random points
+ for i=1,N do
+ local point = geom.point(math.random(), math.random())
+ local closest_bf = find_closest(point)
+ local closest_qt = tree:get_closest(point)
+
+ assert(closest_bf.x == closest_qt.x,
+ string.format(
+ 'bf: (%0.3f, %0.3f), qt: (%0.3f, %0.3f)',
+ closest_bf.x, closest_bf.y,
+ closest_qt.x, closest_qt.y
+ )
+ )
+ assert(closest_bf.y == closest_qt.y,
+ string.format(
+ 'bf: (%0.3f, %0.3f), qt: (%0.3f, %0.3f)',
+ closest_bf.x, closest_bf.y,
+ closest_qt.x, closest_qt.y
+ )
+ )
+ end
+ end
+)