Skip to content

Commit b5460ba

Browse files
lonvialonvia
authored
Merge pull request #1651 from joto/geometry-refactor-expire3
Refactor of expire code
2 parents 9cde168 + 8249a8f commit b5460ba

5 files changed

Lines changed: 148 additions & 174 deletions

File tree

‎src/expire-tiles.cpp‎

Lines changed: 59 additions & 99 deletions
Original file line numberDiff line numberDiff line change
@@ -28,13 +28,11 @@
2828
#include "options.hpp"
2929
#include "reprojection.hpp"
3030
#include "table.hpp"
31+
#include "tile.hpp"
3132
#include "wkb.hpp"
3233

33-
#define EARTH_CIRCUMFERENCE 40075016.68
34-
#define HALF_EARTH_CIRCUMFERENCE (EARTH_CIRCUMFERENCE / 2)
35-
3634
// How many tiles worth of space to leave either side of a changed feature
37-
#define TILE_EXPIRY_LEEWAY 0.1
35+
static constexpr double const tile_expiry_leeway = 0.1;
3836

3937
tile_output_t::tile_output_t(char const *filename)
4038
: outfile(fopen(filename, "a"))
@@ -62,25 +60,23 @@ void tile_output_t::output_dirty_tile(tile_t const &tile)
6260
fmt::print(outfile, "{}/{}/{}\n", tile.zoom(), tile.x(), tile.y());
6361
}
6462

63+
expire_tiles::expire_tiles(uint32_t max_zoom, double max_bbox,
64+
const std::shared_ptr<reprojection> &projection)
65+
: m_projection(projection), m_max_bbox(max_bbox), m_maxzoom(max_zoom),
66+
m_map_width(1U << m_maxzoom)
67+
{}
68+
6569
void expire_tiles::output_and_destroy(char const *filename, uint32_t minzoom)
6670
{
6771
tile_output_t output_writer{filename};
6872
output_and_destroy<tile_output_t>(output_writer, minzoom);
6973
}
7074

71-
expire_tiles::expire_tiles(uint32_t max, double bbox,
72-
const std::shared_ptr<reprojection> &proj)
73-
: max_bbox(bbox), maxzoom(max), projection(proj)
74-
{
75-
map_width = 1U << maxzoom;
76-
tile_width = EARTH_CIRCUMFERENCE / map_width;
77-
}
78-
7975
void expire_tiles::expire_tile(uint32_t x, uint32_t y)
8076
{
8177
// Only try to insert to tile into the set if the last inserted tile
8278
// is different from this tile.
83-
tile_t const new_tile{maxzoom, x, y};
79+
tile_t const new_tile{m_maxzoom, x, y};
8480
if (!m_prev_tile.valid() || m_prev_tile != new_tile) {
8581
m_dirty_tiles.insert(new_tile.quadkey());
8682
m_prev_tile = new_tile;
@@ -89,26 +85,25 @@ void expire_tiles::expire_tile(uint32_t x, uint32_t y)
8985

9086
uint32_t expire_tiles::normalise_tile_x_coord(int x) const
9187
{
92-
x %= map_width;
88+
x %= m_map_width;
9389
if (x < 0) {
94-
x = (map_width - x) + 1;
90+
x = (m_map_width - x) + 1;
9591
}
9692
return static_cast<uint32_t>(x);
9793
}
9894

99-
void expire_tiles::coords_to_tile(double lon, double lat, double *tilex,
100-
double *tiley)
95+
geom::point_t expire_tiles::coords_to_tile(geom::point_t const &point)
10196
{
102-
auto const c = projection->target_to_tile(geom::point_t{lon, lat});
97+
auto const c = m_projection->target_to_tile(point);
10398

104-
*tilex = map_width * (0.5 + c.x() / EARTH_CIRCUMFERENCE);
105-
*tiley = map_width * (0.5 - c.y() / EARTH_CIRCUMFERENCE);
99+
return {m_map_width * (0.5 + c.x() / tile_t::earth_circumference),
100+
m_map_width * (0.5 - c.y() / tile_t::earth_circumference)};
106101
}
107102

108103
void expire_tiles::from_point_list(geom::point_list_t const &list)
109104
{
110-
for_each_segment(list, [&](geom::point_t a, geom::point_t b) {
111-
from_line(a.x(), a.y(), b.x(), b.y());
105+
for_each_segment(list, [&](geom::point_t const &a, geom::point_t const &b) {
106+
from_line(a, b);
112107
});
113108
}
114109

@@ -154,41 +149,26 @@ void expire_tiles::from_geometry(geom::geometry_t const &geom, osmid_t osm_id)
154149
/*
155150
* Expire tiles that a line crosses
156151
*/
157-
void expire_tiles::from_line(double lon_a, double lat_a, double lon_b,
158-
double lat_b)
152+
void expire_tiles::from_line(geom::point_t const &a, geom::point_t const &b)
159153
{
160-
double tile_x_a = NAN;
161-
double tile_y_a = NAN;
162-
double tile_x_b = NAN;
163-
double tile_y_b = NAN;
154+
auto tilec_a = coords_to_tile(a);
155+
auto tilec_b = coords_to_tile(b);
164156

165-
coords_to_tile(lon_a, lat_a, &tile_x_a, &tile_y_a);
166-
coords_to_tile(lon_b, lat_b, &tile_x_b, &tile_y_b);
167-
168-
if (tile_x_a > tile_x_b) {
157+
if (tilec_a.x() > tilec_b.x()) {
169158
/* We always want the line to go from left to right - swap the ends if it doesn't */
170-
double temp = tile_x_b;
171-
tile_x_b = tile_x_a;
172-
tile_x_a = temp;
173-
temp = tile_y_b;
174-
tile_y_b = tile_y_a;
175-
tile_y_a = temp;
159+
std::swap(tilec_a, tilec_b);
176160
}
177161

178-
double const x_len = tile_x_b - tile_x_a;
179-
if (x_len > map_width / 2) {
162+
double const x_len = tilec_b.x() - tilec_a.x();
163+
if (x_len > m_map_width / 2) {
180164
/* If the line is wider than half the map, assume it
181165
crosses the international date line.
182166
These coordinates get normalised again later */
183-
tile_x_a += map_width;
184-
double temp = tile_x_b;
185-
tile_x_b = tile_x_a;
186-
tile_x_a = temp;
187-
temp = tile_y_b;
188-
tile_y_b = tile_y_a;
189-
tile_y_a = temp;
167+
tilec_a.set_x(tilec_a.x() + m_map_width);
168+
std::swap(tilec_a, tilec_b);
190169
}
191-
double const y_len = tile_y_b - tile_y_a;
170+
171+
double const y_len = tilec_b.y() - tilec_a.y();
192172
double const hyp_len = sqrt(pow(x_len, 2) + pow(y_len, 2)); /* Pythagoras */
193173
double const x_step = x_len / hyp_len;
194174
double const y_step = y_len / hyp_len;
@@ -199,10 +179,10 @@ void expire_tiles::from_line(double lon_a, double lat_a, double lon_b,
199179
if (next_step > hyp_len) {
200180
next_step = hyp_len;
201181
}
202-
double x1 = tile_x_a + ((double)step * x_step);
203-
double y1 = tile_y_a + ((double)step * y_step);
204-
double x2 = tile_x_a + ((double)next_step * x_step);
205-
double y2 = tile_y_a + ((double)next_step * y_step);
182+
double x1 = tilec_a.x() + ((double)step * x_step);
183+
double y1 = tilec_a.y() + ((double)step * y_step);
184+
double x2 = tilec_a.x() + ((double)next_step * x_step);
185+
double y2 = tilec_a.y() + ((double)next_step * y_step);
206186

207187
/* The line (x1,y1),(x2,y2) is up to 1 tile width long
208188
x1 will always be <= x2
@@ -214,10 +194,10 @@ void expire_tiles::from_line(double lon_a, double lat_a, double lon_b,
214194
y2 = y1;
215195
y1 = temp;
216196
}
217-
for (int x = x1 - TILE_EXPIRY_LEEWAY; x <= x2 + TILE_EXPIRY_LEEWAY;
197+
for (int x = x1 - tile_expiry_leeway; x <= x2 + tile_expiry_leeway;
218198
++x) {
219199
uint32_t const norm_x = normalise_tile_x_coord(x);
220-
for (int y = y1 - TILE_EXPIRY_LEEWAY; y <= y2 + TILE_EXPIRY_LEEWAY;
200+
for (int y = y1 - tile_expiry_leeway; y <= y2 + tile_expiry_leeway;
221201
++y) {
222202
if (y >= 0) {
223203
expire_tile(norm_x, static_cast<uint32_t>(y));
@@ -232,56 +212,46 @@ void expire_tiles::from_line(double lon_a, double lat_a, double lon_b,
232212
*/
233213
int expire_tiles::from_bbox(geom::box_t const &box)
234214
{
235-
double const min_lon = box.min_x();
236-
double const min_lat = box.min_y();
237-
double const max_lon = box.max_x();
238-
double const max_lat = box.max_y();
239-
240-
return from_bbox(min_lon, min_lat, max_lon, max_lat);
241-
}
242-
243-
int expire_tiles::from_bbox(double min_lon, double min_lat, double max_lon,
244-
double max_lat)
245-
{
246-
if (maxzoom == 0) {
215+
if (!enabled()) {
247216
return 0;
248217
}
249218

250-
double const width = max_lon - min_lon;
251-
double const height = max_lat - min_lat;
252-
if (width > HALF_EARTH_CIRCUMFERENCE + 1) {
219+
double const width = box.width();
220+
double const height = box.height();
221+
if (width > tile_t::half_earth_circumference + 1) {
253222
/* Over half the planet's width within the bounding box - assume the
254223
box crosses the international date line and split it into two boxes */
255-
int ret =
256-
from_bbox(-HALF_EARTH_CIRCUMFERENCE, min_lat, min_lon, max_lat);
257-
ret += from_bbox(max_lon, min_lat, HALF_EARTH_CIRCUMFERENCE, max_lat);
224+
int ret = from_bbox({-tile_t::half_earth_circumference, box.min_y(),
225+
box.min_x(), box.max_y()});
226+
ret += from_bbox({box.max_x(), box.min_y(),
227+
tile_t::half_earth_circumference, box.max_y()});
258228
return ret;
259229
}
260230

261-
if (width > max_bbox || height > max_bbox) {
231+
if (width > m_max_bbox || height > m_max_bbox) {
262232
return -1;
263233
}
264234

265235
/* Convert the box's Mercator coordinates into tile coordinates */
266-
double tmp_x = NAN;
267-
double tmp_y = NAN;
268-
coords_to_tile(min_lon, max_lat, &tmp_x, &tmp_y);
269-
int min_tile_x = tmp_x - TILE_EXPIRY_LEEWAY;
270-
int min_tile_y = tmp_y - TILE_EXPIRY_LEEWAY;
271-
coords_to_tile(max_lon, min_lat, &tmp_x, &tmp_y);
272-
int max_tile_x = tmp_x + TILE_EXPIRY_LEEWAY;
273-
int max_tile_y = tmp_y + TILE_EXPIRY_LEEWAY;
236+
auto const tmp_min = coords_to_tile({box.min_x(), box.max_y()});
237+
int min_tile_x = tmp_min.x() - tile_expiry_leeway;
238+
int min_tile_y = tmp_min.y() - tile_expiry_leeway;
239+
240+
auto const tmp_max = coords_to_tile({box.max_x(), box.min_y()});
241+
int max_tile_x = tmp_max.x() + tile_expiry_leeway;
242+
int max_tile_y = tmp_max.y() + tile_expiry_leeway;
243+
274244
if (min_tile_x < 0) {
275245
min_tile_x = 0;
276246
}
277247
if (min_tile_y < 0) {
278248
min_tile_y = 0;
279249
}
280-
if (max_tile_x > map_width) {
281-
max_tile_x = map_width;
250+
if (max_tile_x > m_map_width) {
251+
max_tile_x = m_map_width;
282252
}
283-
if (max_tile_y > map_width) {
284-
max_tile_y = map_width;
253+
if (max_tile_y > m_map_width) {
254+
max_tile_y = m_map_width;
285255
}
286256
for (int iterator_x = min_tile_x; iterator_x <= max_tile_x; ++iterator_x) {
287257
uint32_t const norm_x = normalise_tile_x_coord(iterator_x);
@@ -295,42 +265,32 @@ int expire_tiles::from_bbox(double min_lon, double min_lat, double max_lon,
295265

296266
int expire_tiles::from_result(pg_result_t const &result, osmid_t osm_id)
297267
{
298-
//bail if we dont care about expiry
299-
if (maxzoom == 0) {
268+
if (!enabled()) {
300269
return -1;
301270
}
302271

303-
//dirty the stuff
304272
auto const num_tuples = result.num_tuples();
305273
for (int i = 0; i < num_tuples; ++i) {
306274
char const *const wkb = result.get_value(i, 0);
307275
from_geometry(ewkb_to_geom(decode_hex(wkb)), osm_id);
308276
}
309277

310-
//return how many rows were affected
311278
return num_tuples;
312279
}
313280

314281
void expire_tiles::merge_and_destroy(expire_tiles &other)
315282
{
316-
if (map_width != other.map_width) {
283+
if (m_map_width != other.m_map_width) {
317284
throw std::runtime_error{"Unable to merge tile expiry sets when "
318285
"map_width does not match: {} != {}."_format(
319-
map_width, other.map_width)};
320-
}
321-
322-
if (tile_width != other.tile_width) {
323-
throw std::runtime_error{"Unable to merge tile expiry sets when "
324-
"tile_width does not match: {} != {}."_format(
325-
tile_width, other.tile_width)};
286+
m_map_width, other.m_map_width)};
326287
}
327288

328289
if (m_dirty_tiles.empty()) {
329290
m_dirty_tiles = std::move(other.m_dirty_tiles);
330291
} else {
331292
m_dirty_tiles.insert(other.m_dirty_tiles.begin(),
332293
other.m_dirty_tiles.end());
294+
other.m_dirty_tiles.clear();
333295
}
334-
335-
other.m_dirty_tiles.clear();
336296
}

‎src/expire-tiles.hpp‎

Lines changed: 17 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -42,18 +42,17 @@ class tile_output_t
4242
void output_dirty_tile(tile_t const &tile);
4343
};
4444

45-
struct expire_tiles
45+
class expire_tiles
4646
{
47-
expire_tiles(uint32_t maxzoom, double maxbbox,
47+
public:
48+
expire_tiles(uint32_t max_zoom, double max_bbox,
4849
const std::shared_ptr<reprojection> &projection);
4950

50-
bool enabled() const noexcept { return maxzoom != 0; }
51+
bool enabled() const noexcept { return m_maxzoom != 0; }
5152

5253
void from_geometry(geom::geometry_t const &geom, osmid_t osm_id);
5354

5455
int from_bbox(geom::box_t const &box);
55-
int from_bbox(double min_lon, double min_lat, double max_lon,
56-
double max_lat);
5756

5857
/**
5958
* Expire tiles based on an osm id.
@@ -90,7 +89,7 @@ struct expire_tiles
9089
template <class TILE_WRITER>
9190
void output_and_destroy(TILE_WRITER &output_writer, uint32_t minzoom)
9291
{
93-
assert(minzoom <= maxzoom);
92+
assert(minzoom <= m_maxzoom);
9493
// build a sorted vector of all expired tiles
9594
std::vector<uint64_t> tiles_maxzoom(m_dirty_tiles.begin(),
9695
m_dirty_tiles.end());
@@ -101,10 +100,10 @@ struct expire_tiles
101100
*
102101
* last_quadkey is initialized with a value which is not expected to exist
103102
* (larger than largest possible quadkey). */
104-
uint64_t last_quadkey = 1ULL << (2 * maxzoom);
103+
uint64_t last_quadkey = 1ULL << (2 * m_maxzoom);
105104
std::size_t count = 0;
106105
for (auto const quadkey : tiles_maxzoom) {
107-
for (uint32_t dz = 0; dz <= maxzoom - minzoom; ++dz) {
106+
for (uint32_t dz = 0; dz <= m_maxzoom - minzoom; ++dz) {
108107
// scale down to the current zoom level
109108
uint64_t qt_current = quadkey >> (dz * 2);
110109
/* If dz > 0, there are propably multiple elements whose quadkey
@@ -115,7 +114,7 @@ struct expire_tiles
115114
continue;
116115
}
117116
auto const tile =
118-
tile_t::from_quadkey(qt_current, maxzoom - dz);
117+
tile_t::from_quadkey(qt_current, m_maxzoom - dz);
119118
output_writer.output_dirty_tile(tile);
120119
++count;
121120
}
@@ -135,7 +134,7 @@ struct expire_tiles
135134
/**
136135
* Converts from target coordinates to tile coordinates.
137136
*/
138-
void coords_to_tile(double lon, double lat, double *tilex, double *tiley);
137+
geom::point_t coords_to_tile(geom::point_t const &point);
139138

140139
/**
141140
* Expire a single tile.
@@ -145,20 +144,21 @@ struct expire_tiles
145144
*/
146145
void expire_tile(uint32_t x, uint32_t y);
147146
uint32_t normalise_tile_x_coord(int x) const;
148-
void from_line(double lon_a, double lat_a, double lon_b, double lat_b);
147+
void from_line(geom::point_t const &a, geom::point_t const &b);
149148

150149
void from_point_list(geom::point_list_t const &list);
151150

152-
double tile_width;
153-
double max_bbox;
154-
int map_width;
155-
uint32_t maxzoom;
156-
std::shared_ptr<reprojection> projection;
151+
/// This is where we collect all the expired tiles.
152+
std::unordered_set<uint64_t> m_dirty_tiles;
157153

158154
/// The tile which has been added last to the unordered set.
159155
tile_t m_prev_tile;
160156

161-
std::unordered_set<uint64_t> m_dirty_tiles;
157+
std::shared_ptr<reprojection> m_projection;
158+
159+
double m_max_bbox;
160+
uint32_t m_maxzoom;
161+
int m_map_width;
162162
};
163163

164164
#endif // OSM2PGSQL_EXPIRE_TILES_HPP

0 commit comments

Comments
 (0)