diff options
Diffstat (limited to 'city/geometry-test.lua')
-rw-r--r-- | city/geometry-test.lua | 58 |
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 +) |