blob: fa578cd3a64543f40b5c0360225f1d226a763572 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
|
;;; Chickadee Game Toolkit
;;; Copyright © 2021 David Thompson <davet@gnu.org>
;;;
;;; Chickadee is free software: you can redistribute it and/or modify
;;; it under the terms of the GNU General Public License as published
;;; by the Free Software Foundation, either version 3 of the License,
;;; or (at your option) any later version.
;;;
;;; Chickadee is distributed in the hope that it will be useful, but
;;; WITHOUT ANY WARRANTY; without even the implied warranty of
;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
;;; General Public License for more details.
;;;
;;; You should have received a copy of the GNU General Public License
;;; along with this program. If not, see
;;; <http://www.gnu.org/licenses/>.
(define-module (tests quadtree)
#:use-module (tests utils)
#:use-module (srfi srfi-64)
#:use-module (chickadee data quadtree)
#:use-module (chickadee math rect))
(define (quadtree)
(make-quadtree (make-rect 0 0 100 100) #:max-size 3 #:max-depth 2))
(with-tests "quadtree"
(test-group "quadtree-insert!"
(test-group "inserting a single object"
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
(test-equal (quadtree-size q) 1)
(test-assert (quadtree-leaf? q))))
(test-group "inserting maximum objects for one node"
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'bar)
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'baz)
(test-equal (quadtree-size q) 3)
(test-assert (quadtree-leaf? q))))
(test-group "splitting where all objects move to child nodes"
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'foo)
(quadtree-insert! q (make-rect 10.0 60.0 10.0 10.0) 'bar)
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'baz)
(quadtree-insert! q (make-rect 60.0 10.0 10.0 10.0) 'frob)
(test-equal (quadtree-size q) 0)
(test-assert (not (quadtree-leaf? q)))))
(test-group "splitting where all objects stay in parent node"
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'foo)
(quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'bar)
(quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'baz)
(quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'frob)
(test-equal (quadtree-size q) 4)
(test-assert (quadtree-leaf? q)))))
(test-group "quadtree-delete!"
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
(quadtree-delete! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
(test-equal "deleting from a root node with 1 object"
(quadtree-size q) 0))
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
(quadtree-insert! q (make-rect 20.0 10.0 10.0 10.0) 'bar)
(quadtree-insert! q (make-rect 30.0 10.0 10.0 10.0) 'baz)
(quadtree-delete! q (make-rect 30.0 10.0 10.0 10.0) 'bar)
(test-equal "deleting from a root node with multiple objects"
(quadtree-size q) 2))
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
(quadtree-insert! q (make-rect 15.0 10.0 10.0 10.0) 'bar)
(quadtree-insert! q (make-rect 20.0 10.0 10.0 10.0) 'baz)
(quadtree-insert! q (make-rect 25.0 10.0 10.0 10.0) 'frob)
(test-assert "deleting from a lower node"
(quadtree-delete! q (make-rect 25.0 10.0 10.0 10.0) 'frob)))
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
(quadtree-insert! q (make-rect 15.0 10.0 10.0 10.0) 'bar)
(quadtree-insert! q (make-rect 20.0 10.0 10.0 10.0) 'baz)
(quadtree-insert! q (make-rect 25.0 10.0 10.0 10.0) 'frob)
(quadtree-delete! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
(test-assert "clearing out a level"
(quadtree-leaf? (quadtree-q3 q)))))
(test-group "quadtree-fold"
(test-equal "rect within a single leaf node at level 0"
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'one)
(quadtree-insert! q (make-rect 10.0 60.0 10.0 10.0) 'two)
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'three)
(quadtree-insert! q (make-rect 60.0 10.0 10.0 10.0) 'four)
(quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'five)
(quadtree-fold q (make-rect 0.0 0.0 40.0 40.0) '() cons))
'(three five))
(test-equal "rect spans multiple nodes at level 1"
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'one)
(quadtree-insert! q (make-rect 10.0 60.0 10.0 10.0) 'two)
(quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'three)
(quadtree-insert! q (make-rect 60.0 10.0 10.0 10.0) 'four)
(quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'five)
(quadtree-fold q (make-rect 0.0 0.0 60.0 40.0) '() cons))
'(four three five))
(test-equal "rect within a single leaf node at level 2"
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 80.0 80.0 10.0 10.0) 'one)
(quadtree-insert! q (make-rect 60.0 80.0 10.0 10.0) 'two)
(quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'three)
(quadtree-insert! q (make-rect 80.0 60.0 10.0 10.0) 'four)
(quadtree-insert! q (make-rect 65.0 65.0 10.0 10.0) 'five)
(quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'six)
(quadtree-fold q (make-rect 76.0 76.0 20.0 20.0) '() cons))
'(one five six))
(test-equal "rect spans multiple nodes at level 2"
(let ((q (quadtree)))
(quadtree-insert! q (make-rect 70.0 70.0 10.0 10.0) 'one)
(quadtree-insert! q (make-rect 60.0 80.0 10.0 10.0) 'two)
(quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'three)
(quadtree-insert! q (make-rect 80.0 60.0 10.0 10.0) 'four)
(quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'five)
(quadtree-fold q (make-rect 70.0 70.0 20.0 20.0) '() cons))
'(four three two one five))))
|
