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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
from math import pi
import unittest
from GeoSpatialTools import haversine
from GeoSpatialTools.quadtree import QuadTree, Record, Rectangle, Ellipse
class TestRect(unittest.TestCase):
def test_contains(self):
rect = Rectangle(10, 5, 20, 10)
points: list[Record] = [
Record(10, 5),
Record(20, 10),
Record(0, 0),
Record(12.8, 2.1),
Record(-2, -9.2),
]
expected = [True, True, True, True, False]
res = list(map(rect.contains, points))
assert res == expected
def test_intersection(self):
rect = Rectangle(10, 5, 20, 10)
test_rects: list[Rectangle] = [
Rectangle(10, 5, 18, 8),
Rectangle(25, 5, 9, 12),
Rectangle(15, 8, 12, 7),
]
expected = [True, False, True]
res = list(map(rect.intersects, test_rects))
assert res == expected
class TestQuadTree(unittest.TestCase):
def test_divides(self):
boundary = Rectangle(10, 4, 20, 8)
qtree = QuadTree(boundary)
expected: list[Rectangle] = [
Rectangle(5, 6, 10, 4),
Rectangle(15, 6, 10, 4),
Rectangle(5, 2, 10, 4),
Rectangle(15, 2, 10, 4),
]
qtree.divide()
res = [
qtree.northwest.boundary,
qtree.northeast.boundary,
qtree.southwest.boundary,
qtree.southeast.boundary,
]
assert res == expected
def test_insert(self):
boundary = Rectangle(10, 4, 20, 8)
qtree = QuadTree(boundary, capacity=3)
points: list[Record] = [
Record(10, 5),
Record(19, 1),
Record(0, 0),
Record(-2, -9.2),
Record(12.8, 2.1),
]
expected = [
points[:3],
[],
[],
[],
[points[-1]],
]
for point in points:
qtree.insert(point)
assert qtree.divided
res = [
qtree.points,
qtree.northwest.points,
qtree.northeast.points,
qtree.southwest.points,
qtree.southeast.points,
]
assert res == expected
def test_query(self):
boundary = Rectangle(10, 4, 20, 8)
qtree = QuadTree(boundary, capacity=3)
points: list[Record] = [
Record(10, 5),
Record(19, 1),
Record(0, 0),
Record(-2, -9.2),
Record(12.8, 2.1),
]
test_rect = Rectangle(12.5, 2.5, 1, 1)
expected = [Record(12.8, 2.1)]
for point in points:
qtree.insert(point)
res = qtree.query(test_rect)
assert res == expected
def test_ellipse_query(self):
d1 = haversine(0, 2.5, 1, 2.5)
d2 = haversine(0, 2.5, 0, 3.0)
theta = 0
ellipse = Ellipse(12.5, 2.5, d1, d2, theta)
# TEST: distint locii
assert (ellipse.p1_lon, ellipse.p1_lat) != (
ellipse.p2_lon,
ellipse.p2_lat,
)
# TEST: Near Boundary Points
assert ellipse.contains(Record(13.49, 2.5))
assert ellipse.contains(Record(11.51, 2.5))
assert ellipse.contains(Record(12.5, 2.99))
assert ellipse.contains(Record(12.5, 2.01))
assert not ellipse.contains(Record(13.51, 2.5))
assert not ellipse.contains(Record(11.49, 2.5))
assert not ellipse.contains(Record(12.5, 3.01))
assert not ellipse.contains(Record(12.5, 1.99))
boundary = Rectangle(10, 4, 20, 8)
qtree = QuadTree(boundary, capacity=3)
points: list[Record] = [
Record(10, 5),
Record(19, 1),
Record(0, 0),
Record(-2, -9.2),
Record(13.5, 2.6), # Just North of Eastern edge
Record(12.6, 3.0), # Just East of Northern edge
Record(12.8, 2.1),
# Locii
Record(ellipse.p1_lon, ellipse.p1_lat),
Record(ellipse.p2_lon, ellipse.p2_lat),
]
expected = [
Record(12.8, 2.1),
Record(ellipse.p1_lon, ellipse.p1_lat),
Record(ellipse.p2_lon, ellipse.p2_lat),
]
for point in points:
qtree.insert(point)
res = qtree.query_ellipse(ellipse)
assert res == expected
if __name__ == "__main__":
unittest.main()