Coverage for /home/runner/work/viur-core/viur-core/viur/src/viur/core/bones/spatial.py: 12%
160 statements
« prev ^ index » next coverage.py v7.6.3, created at 2024-10-16 22:16 +0000
1"""
2`spatial` contains
3- The `SpatialBone` to handle coordinates
4- and `haversine` to calculate the distance between two points on earth using their latitude and longitude.
5"""
7import logging
8from copy import deepcopy
9import typing as t
11import math
12from math import floor
14from viur.core import db
15from viur.core.bones.base import BaseBone, ReadFromClientError, ReadFromClientErrorSeverity
18def haversine(lat1, lng1, lat2, lng2):
19 """
20 Calculate the distance between two points on Earth's surface in meters.
22 This function uses the haversine formula to compute the great-circle distance between
23 two points on Earth's surface, specified by their latitude and longitude coordinates.
24 The haversine formula is particularly useful for small distances on the Earth's surface,
25 as it provides accurate results with good performance.
27 For more details on the haversine formula, see
28 `Haversine formula <https://en.wikipedia.org/wiki/Haversine_formula>`_.
30 :param float lat1: Latitude of the first point in decimal degrees.
31 :param float lng1: Longitude of the first point in decimal degrees.
32 :param float lat2: Latitude of the second point in decimal degrees.
33 :param float lng2: Longitude of the second point in decimal degrees.
34 :return: Distance between the two points in meters.
35 :rtype: float
36 """
37 lat1 = math.radians(lat1)
38 lng1 = math.radians(lng1)
39 lat2 = math.radians(lat2)
40 lng2 = math.radians(lng2)
41 distLat = lat2 - lat1
42 distlng = lng2 - lng1
43 d = math.sin(distLat / 2.0) ** 2.0 + math.cos(lat1) * math.cos(lat2) * math.sin(distlng / 2.0) ** 2.0
44 return math.atan2(math.sqrt(d), math.sqrt(1 - d)) * 12742000 # 12742000 = Avg. Earth size (6371km) in meters*2
47class SpatialBone(BaseBone):
48 r"""
49 The "SpatialBone" is a specific type of data structure designed to handle spatial data, such as geographical
50 coordinates or geometries. This bone would typically be used for representing and storing location-based data,
51 like the coordinates of a point of interest on a map or the boundaries of a geographic region.
52 This feature allows querying elements near a specific location. Before using, designate the map region for
53 which the index should be constructed. To ensure the best accuracy, minimize the region size; using the entire
54 world is not feasible since boundary wraps are not executed. GridDimensions indicates the number of sub-regions
55 the map will be partitioned into. Results beyond the size of these sub-regions will not be considered during
56 searches by this algorithm.
58 .. note:: Example:
59 When using this feature to find the nearest pubs, the algorithm could be set to consider
60 results within 100km but not those 500km away. Setting the sub-region size to roughly
61 100km in width and height allows the algorithm to exclude results further than 200km away
62 at the database-query-level, significantly enhancing performance and reducing query costs.
64 Example region: Germany: ```boundsLat=(46.988, 55.022), boundsLng=(4.997, 15.148)```
66 :param Tuple[float, float] boundsLat: The outer bounds (Latitude) of the region we will search in
67 :param Tuple[float, float] boundsLng: The outer bounds (Longitude) of the region we will search in
68 :param gridDimensions: (Tuple[int, int]) The number of sub-regions the map will be divided in
69 """
71 type = "spatial"
73 def __init__(self, *, boundsLat: tuple[float, float], boundsLng: tuple[float, float],
74 gridDimensions: tuple[int, int], **kwargs):
75 """
76 Initializes a new SpatialBone.
78 :param boundsLat: Outer bounds (Latitude) of the region we will search in.
79 :param boundsLng: Outer bounds (Longitude) of the region we will search in.
80 :param gridDimensions: Number of sub-regions the map will be divided in
81 """
82 super().__init__(**kwargs)
83 assert isinstance(boundsLat, tuple) and len(boundsLat) == 2, "boundsLat must be a tuple of (float, float)"
84 assert isinstance(boundsLng, tuple) and len(boundsLng) == 2, "boundsLng must be a tuple of (float, float)"
85 assert isinstance(gridDimensions, tuple) and len(
86 gridDimensions) == 2, "gridDimensions must be a tuple of (int, int)"
87 # Checks if boundsLat and boundsLng have possible values
88 # See https://docs.mapbox.com/help/glossary/lat-lon/
89 if not -90 <= boundsLat[0] <= 90:
90 raise ValueError(f"boundsLat[0] must be between -90 and 90. Got {boundsLat[0]!r}")
91 if not -90 <= boundsLat[1] <= 90:
92 raise ValueError(f"boundsLat[1] must be between -90 and 90. Got {boundsLat[1]!r}")
93 if not -180 <= boundsLng[0] <= 180:
94 raise ValueError(f"boundsLng[0] must be between -180 and 180. Got {boundsLng[0]!r}")
95 if not -180 <= boundsLng[1] <= 180:
96 raise ValueError(f"boundsLng[1] must be between -180 and 180. Got {boundsLng[1]!r}")
97 assert not (self.indexed and self.multiple), "Spatial-Bone cannot be indexed when multiple"
98 self.boundsLat = boundsLat
99 self.boundsLng = boundsLng
100 self.gridDimensions = gridDimensions
102 def getGridSize(self):
103 """
104 Calculate and return the size of the sub-regions in terms of fractions of latitude and longitude.
106 :return: A tuple containing the size of the sub-regions as (fractions-of-latitude, fractions-of-longitude)
107 :rtype: (float, float)
108 """
109 latDelta = float(self.boundsLat[1] - self.boundsLat[0])
110 lngDelta = float(self.boundsLng[1] - self.boundsLng[0])
111 return latDelta / float(self.gridDimensions[0]), lngDelta / float(self.gridDimensions[1])
113 def isInvalid(self, value: tuple[float, float]) -> str | bool:
114 """
115 Validate if the given point (latitude, longitude) falls within the specified boundaries.
116 Rejects all values outside the defined region.
118 :param value: A tuple containing the location of the entry as (latitude, longitude)
119 :return: An error description if the value is invalid or False if the value is valid
120 :rtype: str | bool
121 """
122 try:
123 lat, lng = value
124 except:
125 return "Invalid value entered"
126 if lat < self.boundsLat[0] or lat > self.boundsLat[1]:
127 return "Latitude out of range"
128 elif lng < self.boundsLng[0] or lng > self.boundsLng[1]:
129 return "Longitude out of range"
130 else:
131 return False
133 def singleValueSerialize(self, value, skel: 'SkeletonInstance', name: str, parentIndexed: bool):
134 """
135 Serialize a single value (latitude, longitude) for storage. If the bone is indexed, calculate
136 and add tile information for efficient querying.
138 :param value: A tuple containing the location of the entry as (latitude, longitude)
139 :param SkeletonInstance skel: The instance of the Skeleton this bone is attached to
140 :param str name: The name of this bone
141 :param bool parentIndexed: A boolean indicating if the parent bone is indexed
142 :return: A dictionary containing the serialized data, including coordinates and tile information (if indexed)
143 :rtype: dict | None
144 """
145 if not value:
146 return None
147 lat, lng = value
148 res = {
149 "coordinates": {
150 "lat": lat,
151 "lng": lng,
152 }
153 }
154 indexed = self.indexed and parentIndexed
155 if indexed:
156 gridSizeLat, gridSizeLng = self.getGridSize()
157 tileLat = int(floor((lat - self.boundsLat[0]) / gridSizeLat))
158 tileLng = int(floor((lng - self.boundsLng[0]) / gridSizeLng))
159 res["tiles"] = {
160 "lat": [tileLat - 1, tileLat, tileLat + 1],
161 "lng": [tileLng - 1, tileLng, tileLng + 1],
162 }
163 return res
165 def singleValueUnserialize(self, val):
166 """
167 Deserialize a single value (latitude, longitude) from the stored data.
169 :param val: A dictionary containing the serialized data, including coordinates
170 :return: A tuple containing the location of the entry as (latitude, longitude)
171 :rtype: Tuple[float, float] | None
172 """
173 if not val:
174 return None
175 return val["coordinates"]["lat"], val["coordinates"]["lng"]
177 def parseSubfieldsFromClient(self):
178 """
179 Determines if subfields (latitude and longitude) should be parsed from the client.
181 :return: Always returns True, as latitude and longitude are required
182 :rtype: bool
183 """
184 return True # We'll always get .lat and .lng
186 def isEmpty(self, value: t.Any):
187 """
188 Check if the given raw value is considered empty (either not present or equal to the empty value).
190 :param value: The raw value to be checked
191 :return: True if the raw value is considered empty, False otherwise
192 :rtype: bool
193 """
194 if not value:
195 return True
196 if isinstance(value, dict):
197 try:
198 rawLat = float(value["lat"])
199 rawLng = float(value["lng"])
200 return (rawLat, rawLng) == self.getEmptyValue()
201 except:
202 return True
203 return value == self.getEmptyValue()
205 def getEmptyValue(self) -> tuple[float, float]:
206 """
207 Returns an empty value for the bone, which represents an invalid position. Use 91.0, 181.0 as a special
208 marker for empty, as they are both out of range for Latitude (-90, +90) and Longitude (-180, 180), but will
209 be accepted by Vi and Admin.
211 :return: A tuple representing an empty value for this bone (91.0, 181.0)
212 :rtype: Tuple[float, float]
213 """
214 return 0.0, 0.0
216 def singleValueFromClient(self, value, skel, bone_name, client_data):
217 rawLat = value.get("lat", None)
218 rawLng = value.get("lng", None)
219 if rawLat is None and rawLng is None:
220 return self.getEmptyValue(), [
221 ReadFromClientError(ReadFromClientErrorSeverity.NotSet, "Field not submitted")]
222 elif rawLat is None or rawLng is None:
223 return self.getEmptyValue(), [ReadFromClientError(ReadFromClientErrorSeverity.Empty, "No value submitted")]
224 try:
225 rawLat = float(rawLat)
226 rawLng = float(rawLng)
227 # Check for NaNs
228 assert rawLat == rawLat
229 assert rawLng == rawLng
230 except:
231 return self.getEmptyValue(), [
232 ReadFromClientError(ReadFromClientErrorSeverity.Invalid, "Invalid value entered")]
233 err = self.isInvalid((rawLat, rawLng))
234 if err:
235 return self.getEmptyValue(), [ReadFromClientError(ReadFromClientErrorSeverity.Invalid, err)]
236 return (rawLat, rawLng), None
238 def buildDBFilter(
239 self,
240 name: str,
241 skel: 'viur.core.skeleton.SkeletonInstance',
242 dbFilter: db.Query,
243 rawFilter: dict,
244 prefix: t.Optional[str] = None
245 ) -> db.Query:
246 """
247 Parses the client's search filter specified in their request and converts it into a format understood by the
248 datastore.
249 - Ignore filters that do not target this bone.
250 - Safely handle malformed data in rawFilter (this parameter is directly controlled by the client).
252 For detailed information on how this geo-spatial search works, see the ViUR documentation.
254 :param str name: The property name this bone has in its Skeleton (not the description!)
255 :param SkeletonInstance skel: The skeleton this bone is part of
256 :param db.Query dbFilter: The current `viur.core.db.Query` instance to which the filters should be applied
257 :param dict rawFilter: The dictionary of filters the client wants to have applied
258 :param prefix: Optional string, specifying a prefix for the bone's name (default is None)
259 :return: The modified `viur.core.db.Query` instance
260 :rtype: db.Query
261 """
262 assert prefix is None, "You cannot use spatial data in a relation for now"
263 if name + ".lat" in rawFilter and name + ".lng" in rawFilter:
264 try:
265 lat = float(rawFilter[name + ".lat"])
266 lng = float(rawFilter[name + ".lng"])
267 except:
268 logging.debug(f"Received invalid values for lat/lng in {name}")
269 dbFilter.datastoreQuery = None
270 return
271 if self.isInvalid((lat, lng)):
272 logging.debug(f"Values out of range in {name}")
273 dbFilter.datastoreQuery = None
274 return
275 gridSizeLat, gridSizeLng = self.getGridSize()
276 tileLat = int(floor((lat - self.boundsLat[0]) / gridSizeLat))
277 tileLng = int(floor((lng - self.boundsLng[0]) / gridSizeLng))
278 assert isinstance(dbFilter.queries, db.QueryDefinition) # Not supported on multi-queries
279 origQuery = dbFilter.queries
280 # Lat - Right Side
281 q1 = deepcopy(origQuery)
282 q1.filters[name + ".coordinates.lat >="] = lat
283 q1.filters[name + ".tiles.lat ="] = tileLat
284 q1.orders = [(name + ".coordinates.lat", db.SortOrder.Ascending)]
285 # Lat - Left Side
286 q2 = deepcopy(origQuery)
287 q2.filters[name + ".coordinates.lat <"] = lat
288 q2.filters[name + ".tiles.lat ="] = tileLat
289 q2.orders = [(name + ".coordinates.lat", db.SortOrder.Descending)]
290 # Lng - Down
291 q3 = deepcopy(origQuery)
292 q3.filters[name + ".coordinates.lng >="] = lng
293 q3.filters[name + ".tiles.lng ="] = tileLng
294 q3.orders = [(name + ".coordinates.lng", db.SortOrder.Ascending)]
295 # Lng - Top
296 q4 = deepcopy(origQuery)
297 q4.filters[name + ".coordinates.lng <"] = lng
298 q4.filters[name + ".tiles.lng ="] = tileLng
299 q4.orders = [(name + ".coordinates.lng", db.SortOrder.Descending)]
300 dbFilter.queries = [q1, q2, q3, q4]
301 dbFilter._customMultiQueryMerge = lambda *args, **kwargs: self.customMultiQueryMerge(name, lat, lng, *args,
302 **kwargs)
303 dbFilter._calculateInternalMultiQueryLimit = self.calculateInternalMultiQueryLimit
305 def calculateInternalMultiQueryLimit(self, dbQuery: db.Query, targetAmount: int):
306 """
307 Provides guidance to viur.core.db.Query on the number of entries that should be fetched in each subquery.
309 :param dbQuery: The `viur.core.db.Query` instance
310 :param targetAmount: The desired number of entries to be returned from the db.Query
311 :return: The number of elements db.Query should fetch for each subquery
312 :rtype: int
313 """
314 return targetAmount * 2
316 def customMultiQueryMerge(self, name, lat, lng, dbFilter: db.Query,
317 result: list[db.Entity], targetAmount: int
318 ) -> list[db.Entity]:
319 """
320 Randomly returns 'targetAmount' elements from 'result'.
322 :param str name: The property-name this bone has in its Skeleton (not the description!)
323 :param lat: Latitude of the reference point
324 :param lng: Longitude of the reference point
325 :param dbFilter: The db.Query instance calling this function
326 :param result: The list of results for each subquery that was executed
327 :param int targetAmount: The desired number of results to be returned from db.Query
328 :return: List of elements to be returned from db.Query
329 :rtype: List[db.Entity]
330 """
331 assert len(result) == 4 # There should be exactly one result for each direction
332 result = [list(x) for x in result] # Remove the iterators
333 latRight, latLeft, lngBottom, lngTop = result
334 gridSizeLat, gridSizeLng = self.getGridSize()
335 # Calculate the outer bounds we've reached - used to tell to which distance we can
336 # prove the result to be correct.
337 # If a result further away than this distance there might be missing results before that result
338 # If there are no results in a give lane (f.e. because we are close the border and there is no point
339 # in between) we choose a arbitrary large value for that lower bound
340 expectedAmount = self.calculateInternalMultiQueryLimit(dbFilter,
341 targetAmount) # How many items we expect in each direction
342 limits = [
343 haversine(latRight[-1][name]["coordinates"]["lat"], lng, lat, lng) if latRight and len(
344 latRight) == expectedAmount else 2 ** 31, # Lat - Right Side
345 haversine(latLeft[-1][name]["coordinates"]["lat"], lng, lat, lng) if latLeft and len(
346 latLeft) == expectedAmount else 2 ** 31, # Lat - Left Side
347 haversine(lat, lngBottom[-1][name]["coordinates"]["lng"], lat, lng) if lngBottom and len(
348 lngBottom) == expectedAmount else 2 ** 31, # Lng - Bottom
349 haversine(lat, lngTop[-1][name]["coordinates"]["lng"], lat, lng) if lngTop and len(
350 lngTop) == expectedAmount else 2 ** 31, # Lng - Top
351 haversine(lat + gridSizeLat, lng, lat, lng),
352 haversine(lat, lng + gridSizeLng, lat, lng)
353 ]
354 dbFilter.customQueryInfo["spatialGuaranteedCorrectness"] = min(limits)
355 logging.debug(f"""SpatialGuaranteedCorrectness: { dbFilter.customQueryInfo["spatialGuaranteedCorrectness"]}""")
356 # Filter duplicates
357 tmpDict = {}
358 for item in (latRight + latLeft + lngBottom + lngTop):
359 tmpDict[str(item.key)] = item
360 # Build up the final results
361 tmpList = [(haversine(x[name]["coordinates"]["lat"], x[name]["coordinates"]["lng"], lat, lng), x) for x in
362 tmpDict.values()]
363 tmpList.sort(key=lambda x: x[0])
364 return [x[1] for x in tmpList[:targetAmount]]
366 def setBoneValue(
367 self,
368 skel: 'SkeletonInstance',
369 boneName: str,
370 value: t.Any,
371 append: bool,
372 language: None | str = None
373 ) -> bool:
374 """
375 Sets the value of the bone to the provided 'value'.
376 Sanity checks are performed; if the value is invalid, the bone value will revert to its original
377 (default) value and the function will return False.
379 :param skel: Dictionary with the current values from the skeleton the bone belongs to
380 :param boneName: The name of the bone that should be modified
381 :param value: The value that should be assigned. Its type depends on the type of the bone
382 :param append: If True, the given value will be appended to the existing bone values instead of
383 replacing them. Only supported on bones with multiple=True
384 :param language: Optional, the language of the value if the bone is language-aware
385 :return: A boolean indicating whether the operation succeeded or not
386 :rtype: bool
387 """
388 if append:
389 raise ValueError(f"append is not possible on {self.type} bones")
390 assert isinstance(value, tuple) and len(value) == 2, "Value must be a tuple of (lat, lng)"
391 skel[boneName] = value
393 def structure(self) -> dict:
394 return super().structure() | {
395 "boundslat": self.boundsLat,
396 "boundslng": self.boundsLng,
397 }