1/*
2 SPDX-FileCopyrightText: 2021 Volker Krause <vkrause@kde.org>
3
4 SPDX-License-Identifier: LGPL-2.0-or-later
5*/
6
7#include "data/spatial_index_data.cpp"
8#include "data/spatial_index_parameters_p.h"
9#include "data/spatial_index_properties.cpp"
10#include "spatial_index_p.h"
11
12#include <cmath>
13#include <cstdint>
14
15constexpr const float XEnd = XStart + XRange;
16constexpr const float YEnd = YStart + YRange;
17
18// verify the null entry is first in the property table
19static_assert(spatial_index_properties[0].m_tz == Tz::Undefined);
20static_assert(spatial_index_properties[0].m_subdiv == 0);
21
22// z index conversions
23constexpr uint32_t latlonToZ(float lat, float lon)
24{
25 const uint32_t x = ((lon - XStart) / XRange) * (1 << ZDepth);
26 const uint32_t y = ((lat - YStart) / YRange) * (1 << ZDepth);
27 uint32_t z = 0;
28 for (int i = ZDepth - 1; i >= 0; --i) {
29 z <<= 1;
30 z += (y & (1 << i)) ? 1 : 0;
31 z <<= 1;
32 z += (x & (1 << i)) ? 1 : 0;
33 }
34 return z;
35}
36
37// "unit tests" for the z index conversion
38static_assert(latlonToZ(lat: YStart, lon: XStart) == 0);
39static_assert(latlonToZ(lat: YEnd - 1.0f / (1 << ZDepth), lon: XEnd - 1.0f / (1 << ZDepth)) == (1 << (2 * ZDepth)) - 1);
40static_assert(latlonToZ(lat: YStart + YRange / 2.0f, lon: 0.0f) == ((1 << (2 * ZDepth - 1)) | (1 << (2 * ZDepth - 2))));
41
42SpatialIndexProperty SpatialIndex::lookup(float lat, float lon)
43{
44 if (std::isnan(x: lat) || std::isnan(x: lon) || lon < XStart || lon >= XEnd || lat < YStart || lat >= YEnd) {
45 return spatial_index_properties[0];
46 }
47
48 const auto z = latlonToZ(lat, lon);
49 const auto it = std::upper_bound(first: std::begin(arr: spatial_index), last: std::end(arr: spatial_index), val: z);
50 if (it == std::begin(arr: spatial_index)) {
51 return spatial_index_properties[0];
52 }
53
54 return spatial_index_properties[(*std::prev(x: it)).propertyIndex()];
55}
56

source code of ki18n/src/localedata/spatial_index.cpp