| 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 | |
| 15 | constexpr const float XEnd = XStart + XRange; |
| 16 | constexpr const float YEnd = YStart + YRange; |
| 17 | |
| 18 | // verify the null entry is first in the property table |
| 19 | static_assert(spatial_index_properties[0].m_tz == Tz::Undefined); |
| 20 | static_assert(spatial_index_properties[0].m_subdiv == 0); |
| 21 | |
| 22 | // z index conversions |
| 23 | constexpr 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 |
| 38 | static_assert(latlonToZ(lat: YStart, lon: XStart) == 0); |
| 39 | static_assert(latlonToZ(lat: YEnd - 1.0f / (1 << ZDepth), lon: XEnd - 1.0f / (1 << ZDepth)) == (1 << (2 * ZDepth)) - 1); |
| 40 | static_assert(latlonToZ(lat: YStart + YRange / 2.0f, lon: 0.0f) == ((1 << (2 * ZDepth - 1)) | (1 << (2 * ZDepth - 2)))); |
| 41 | |
| 42 | SpatialIndexProperty 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 |