1 #ifndef OSMIUM_GEOM_TILE_HPP 2 #define OSMIUM_GEOM_TILE_HPP 3 4 /* 5 6 This file is part of Osmium (https://osmcode.org/libosmium). 7 8 Copyright 2013-2021 Jochen Topf <jochen@topf.org> and others (see README). 9 10 Boost Software License - Version 1.0 - August 17th, 2003 11 12 Permission is hereby granted, free of charge, to any person or organization 13 obtaining a copy of the software and accompanying documentation covered by 14 this license (the "Software") to use, reproduce, display, distribute, 15 execute, and transmit the Software, and to prepare derivative works of the 16 Software, and to permit third-parties to whom the Software is furnished to 17 do so, all subject to the following: 18 19 The copyright notices in the Software and this entire statement, including 20 the above license grant, this restriction and the following disclaimer, 21 must be included in all copies of the Software, in whole or in part, and 22 all derivative works of the Software, unless such copies or derivative 23 works are solely in the form of machine-executable object code generated by 24 a source language processor. 25 26 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 27 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 28 FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT 29 SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE 30 FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, 31 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 32 DEALINGS IN THE SOFTWARE. 33 34 */ 35 36 #include <osmium/geom/coordinates.hpp> 37 #include <osmium/geom/mercator_projection.hpp> 38 #include <osmium/osm/location.hpp> 39 40 #include <cassert> 41 #include <cstdint> 42 43 namespace osmium { 44 45 namespace geom { 46 47 namespace detail { 48 49 template <typename T> clamp(const T & value,const T & min,const T & max)50 inline constexpr const T& clamp(const T& value, const T& min, const T& max) { 51 return value < min ? min : (max < value ? max : value); 52 } 53 54 } // namespace detail 55 56 /** 57 * Returns the number of tiles (in each direction) for the given zoom 58 * level. 59 */ num_tiles_in_zoom(uint32_t zoom)60 inline constexpr uint32_t num_tiles_in_zoom(uint32_t zoom) noexcept { 61 return 1U << zoom; 62 } 63 64 /** 65 * Returns the width or height of a tile in web mercator coordinates for 66 * the given zoom level. 67 */ tile_extent_in_zoom(uint32_t zoom)68 inline constexpr double tile_extent_in_zoom(uint32_t zoom) noexcept { 69 return detail::max_coordinate_epsg3857 * 2 / num_tiles_in_zoom(zoom); 70 } 71 72 /** 73 * Get the tile x number from an x coordinate in web mercator 74 * projection in the given zoom level. Tiles are numbered from left 75 * to right. 76 */ mercx_to_tilex(uint32_t zoom,double x)77 inline constexpr uint32_t mercx_to_tilex(uint32_t zoom, double x) noexcept { 78 return static_cast<uint32_t>(detail::clamp<int32_t>( 79 static_cast<int32_t>((x + detail::max_coordinate_epsg3857) / tile_extent_in_zoom(zoom)), 80 0, num_tiles_in_zoom(zoom) - 1)); 81 } 82 83 /** 84 * Get the tile y number from an y coordinate in web mercator 85 * projection in the given zoom level. Tiles are numbered from top 86 * to bottom. 87 */ mercy_to_tiley(uint32_t zoom,double y)88 inline constexpr uint32_t mercy_to_tiley(uint32_t zoom, double y) noexcept { 89 return static_cast<uint32_t>(detail::clamp<int32_t>( 90 static_cast<int32_t>((detail::max_coordinate_epsg3857 - y) / tile_extent_in_zoom(zoom)), 91 0, num_tiles_in_zoom(zoom) - 1)); 92 } 93 94 /** 95 * A tile in the usual Mercator projection. 96 */ 97 struct Tile { 98 99 enum { 100 max_zoom = 30U 101 }; 102 103 /// x coordinate 104 uint32_t x; 105 106 /// y coordinate 107 uint32_t y; 108 109 /// Zoom level 110 uint32_t z; 111 112 /** 113 * Create a tile with the given zoom level and x and y tile 114 * coordinates. 115 * 116 * The values are not checked for validity. 117 * 118 * @pre @code zoom <= 30 && x < 2^zoom && y < 2^zoom @endcode 119 */ Tileosmium::geom::Tile120 explicit Tile(uint32_t zoom, uint32_t tx, uint32_t ty) noexcept : 121 x(tx), 122 y(ty), 123 z(zoom) { 124 assert(zoom <= max_zoom); 125 assert(x < num_tiles_in_zoom(zoom)); 126 assert(y < num_tiles_in_zoom(zoom)); 127 } 128 129 /** 130 * Create a tile with the given zoom level that contains the given 131 * location. 132 * 133 * The values are not checked for validity. 134 * 135 * @pre @code location.valid() && zoom <= 30 @endcode 136 */ Tileosmium::geom::Tile137 explicit Tile(uint32_t zoom, const osmium::Location& location) : 138 z(zoom) { 139 assert(zoom <= max_zoom); 140 assert(location.valid()); 141 const auto coordinates = lonlat_to_mercator(location); 142 x = mercx_to_tilex(zoom, coordinates.x); 143 y = mercy_to_tiley(zoom, coordinates.y); 144 } 145 146 /** 147 * Create a tile with the given zoom level that contains the given 148 * coordinates in Mercator projection. 149 * 150 * The values are not checked for validity. 151 * 152 * @pre @code coordinates.valid() && zoom <= 30 @endcode 153 */ Tileosmium::geom::Tile154 explicit Tile(uint32_t zoom, const osmium::geom::Coordinates& coordinates) : 155 z(zoom) { 156 assert(zoom <= max_zoom); 157 x = mercx_to_tilex(zoom, coordinates.x); 158 y = mercy_to_tiley(zoom, coordinates.y); 159 } 160 161 /** 162 * Check whether this tile is valid. For a tile to be valid the 163 * zoom level must be between 0 and 30 and the coordinates must 164 * each be between 0 and 2^zoom-1. 165 */ validosmium::geom::Tile166 bool valid() const noexcept { 167 if (z > max_zoom) { 168 return false; 169 } 170 const auto max = num_tiles_in_zoom(z); 171 return x < max && y < max; 172 } 173 174 }; // struct Tile 175 176 /// Tiles are equal if all their attributes are equal. operator ==(const Tile & lhs,const Tile & rhs)177 inline bool operator==(const Tile& lhs, const Tile& rhs) noexcept { 178 return lhs.z == rhs.z && lhs.x == rhs.x && lhs.y == rhs.y; 179 } 180 operator !=(const Tile & lhs,const Tile & rhs)181 inline bool operator!=(const Tile& lhs, const Tile& rhs) noexcept { 182 return !(lhs == rhs); 183 } 184 185 /** 186 * This defines an arbitrary order on tiles for use in std::map etc. 187 */ operator <(const Tile & lhs,const Tile & rhs)188 inline bool operator<(const Tile& lhs, const Tile& rhs) noexcept { 189 if (lhs.z < rhs.z) { 190 return true; 191 } 192 if (lhs.z > rhs.z) { 193 return false; 194 } 195 if (lhs.x < rhs.x) { 196 return true; 197 } 198 if (lhs.x > rhs.x) { 199 return false; 200 } 201 return lhs.y < rhs.y; 202 } 203 204 } // namespace geom 205 206 } // namespace osmium 207 208 #endif // OSMIUM_GEOM_TILE_HPP 209