1 /*
2 SPDX-FileCopyrightText: 2020 Volker Krause <vkrause@kde.org>
3
4 SPDX-License-Identifier: LGPL-2.0-or-later
5 */
6
7 #include "marblegeometryassembler_p.h"
8 #include "reassembly-logging.h"
9
10 #include <cassert>
11
12 using namespace KOSMIndoorMap;
13
14 enum { NodeMatchDistance = 2 }; // in 1e7th of a degree, 46 for the old Marble data, very small for the new one
15
16 /** Compare two coordinate while accounting for floating point noise. */
fuzzyEquals(OSM::Coordinate lhs,OSM::Coordinate rhs)17 static bool fuzzyEquals(OSM::Coordinate lhs, OSM::Coordinate rhs)
18 {
19 return std::abs((int32_t)lhs.latitude - (int32_t)rhs.latitude) <= NodeMatchDistance && std::abs((int32_t)lhs.longitude - (int32_t)rhs.longitude) <= NodeMatchDistance;
20 }
21
22 OSM::Id MarbleGeometryAssembler::s_nextInternalId = -(1ll << 32); // try to stay out of the way of the number space used by Marble tiles
23
24 MarbleGeometryAssembler::MarbleGeometryAssembler() = default;
25 MarbleGeometryAssembler::~MarbleGeometryAssembler() = default;
26
setDataSet(OSM::DataSet * dataSet)27 void MarbleGeometryAssembler::setDataSet(OSM::DataSet* dataSet)
28 {
29 assert(dataSet);
30 m_dataSet = dataSet;
31 m_mxoidKey = m_dataSet->makeTagKey("mx:oid");
32 m_typeKey = m_dataSet->makeTagKey("type");
33 }
34
merge(OSM::DataSetMergeBuffer * mergeBuffer)35 void MarbleGeometryAssembler::merge(OSM::DataSetMergeBuffer *mergeBuffer)
36 {
37 assert(m_dataSet);
38 m_nodeIdMap.clear();
39 m_wayIdMap.clear();
40 m_relIdMap.clear();
41
42 std::vector<OSM::Way> prevPendingWays;
43 std::swap(m_pendingWays, prevPendingWays);
44
45 mergeNodes(mergeBuffer);
46 deduplicateWays(mergeBuffer->ways);
47 remapWayNodes(mergeBuffer->ways);
48 mergeWays(mergeBuffer->ways);
49 mergeWays(prevPendingWays);
50 mergeRelations(mergeBuffer);
51
52 mergeBuffer->clear();
53 }
54
finalize()55 void MarbleGeometryAssembler::finalize()
56 {
57 for (auto &way : m_pendingWays) {
58 m_dataSet->addWay(std::move(way));
59 }
60 }
61
mergeNodes(OSM::DataSetMergeBuffer * mergeBuffer)62 void MarbleGeometryAssembler::mergeNodes(OSM::DataSetMergeBuffer *mergeBuffer)
63 {
64 // nodes of the first batch are just taken as-is
65 if (m_dataSet->nodes.empty()) {
66 m_dataSet->nodes = std::move(mergeBuffer->nodes);
67 std::sort(m_dataSet->nodes.begin(), m_dataSet->nodes.end());
68 return;
69 }
70
71 // for all subsequent batches we have to check for colliding synthetic ids, and if necessary remap those
72 m_dataSet->nodes.reserve(m_dataSet->nodes.size() + mergeBuffer->nodes.size());
73
74 for (auto &node : mergeBuffer->nodes) {
75 const auto it = std::lower_bound(m_dataSet->nodes.begin(), m_dataSet->nodes.end(), node);
76 if (it != m_dataSet->nodes.end() && (*it).id == node.id) {
77 if (node.id < 0) { // synthetic id collision, remap that
78 node.id = s_nextInternalId++;
79 m_nodeIdMap[(*it).id] = node.id;
80 m_dataSet->addNode(std::move(node));
81 }
82 // non-synthetic collisions are expected to be real duplicates, so nothing to do there
83 } else {
84 m_dataSet->nodes.insert(it, std::move(node));
85 }
86 }
87 }
88
mergeWays(std::vector<OSM::Way> & ways)89 void MarbleGeometryAssembler::mergeWays(std::vector<OSM::Way> &ways)
90 {
91 // for ways we do:
92 // 1. restore the original id
93 // 2. if a way with that id already exists, we merge with the geometry of the existing one
94
95 for (auto &way : ways) {
96 if (way.id > 0 || way.nodes.empty()) { // not a synthetic id
97 m_dataSet->addWay(std::move(way));
98 continue;
99 }
100
101 const OSM::Id mxoid = takeMxOid(way);
102 if (mxoid <= 0) { // shouldn't happen?
103 m_dataSet->addWay(std::move(way));
104 continue;
105 }
106
107 const auto syntheticId = way.id;
108 way.id = mxoid;
109
110 const auto it = std::lower_bound(m_dataSet->ways.begin(), m_dataSet->ways.end(), way);
111 if (it != m_dataSet->ways.end() && (*it).id == way.id) {
112 mergeWay(*it, way);
113
114 if (way.nodes.empty()) {
115 // way was fully merged
116 m_wayIdMap[syntheticId] = mxoid;
117 } else {
118 // defer to later (ie. more tiles loaded)
119 way.id = syntheticId;
120 OSM::setTagValue(way, m_mxoidKey, QByteArray::number((qlonglong)mxoid));
121 m_pendingWays.push_back(std::move(way));
122 }
123
124 } else {
125 m_wayIdMap[syntheticId] = mxoid;
126 m_dataSet->ways.insert(it, std::move(way));
127 }
128 }
129 }
130
isDuplicateWay(const OSM::Way & lhs,const OSM::Way & rhs)131 static bool isDuplicateWay(const OSM::Way &lhs, const OSM::Way &rhs)
132 {
133 if (lhs.nodes.size() != rhs.nodes.size()) {
134 return false;
135 }
136 for (std::size_t i = 0; i < lhs.nodes.size(); ++i) {
137 if (lhs.nodes[i] != rhs.nodes[i] && (lhs.nodes[i] > 0 || rhs.nodes[i] > 0)) {
138 return false;
139 }
140 }
141 return true;
142 }
143
deduplicateWays(std::vector<OSM::Way> & ways)144 void MarbleGeometryAssembler::deduplicateWays(std::vector<OSM::Way>& ways)
145 {
146 for (auto it = ways.begin(); it != ways.end();) {
147 if ((*it).id > 0) {
148 ++it;
149 continue;
150 }
151 const OSM::Id mxoid = OSM::tagValue(*it, m_mxoidKey).toLongLong();
152 if (mxoid == 0) {
153 ++it;
154 continue;
155 }
156
157 const auto duplIt = m_duplicateWays.find(mxoid);
158 if (duplIt != m_duplicateWays.end()) {
159 bool found = false;
160 for (auto it2 = (*duplIt).second.begin(); it2 != (*duplIt).second.end(); ++it2) {
161 if (isDuplicateWay(*it, ways[*it2])) {
162 m_wayIdMap[(*it).id] = mxoid;
163 qCDebug(ReassemblyLog) << "removing duplicate way:" << (*it).id << (*it).url();
164 it = ways.erase(it);
165 found = true;
166 break;
167 }
168 }
169 if (!found) {
170 m_duplicateWays[mxoid].push_back(std::distance(ways.begin(), it));
171 ++it;
172 }
173 } else {
174 m_duplicateWays[mxoid] = {(std::size_t)std::distance(ways.begin(), it)};
175 ++it;
176 }
177 }
178 m_duplicateWays.clear();
179 }
180
remapWayNodes(std::vector<OSM::Way> & ways) const181 void MarbleGeometryAssembler::remapWayNodes(std::vector<OSM::Way> &ways) const
182 {
183 if (m_nodeIdMap.empty()) {
184 return;
185 }
186
187 for (auto &way : ways) {
188 for (auto &id : way.nodes) {
189 if (id > 0) {
190 continue;
191 }
192 const auto it = m_nodeIdMap.find(id);
193 if (it != m_nodeIdMap.end()) {
194 id = (*it).second;
195 }
196 }
197 }
198 }
199
mergeWay(OSM::Way & way,OSM::Way & otherWay) const200 void MarbleGeometryAssembler::mergeWay(OSM::Way &way, OSM::Way &otherWay) const
201 {
202 // for merging two ways:
203 // - non-synthetic nodes remain unchanged, ways can only be merged on synthetic nodes
204 // - synthetic nodes are duplicated in both sets, we need to merge them by coordinate comparison
205 // - synthetic nodes can be removed, and so can edges between two adjacent synthetic nodes
206 // - closed polygons at least have one shared edge (possibly multiple adjacent or non-adjacent ones)
207 // - lines can only be merged at the beginning or the end, a line crossing the same boundary multiple times would be split at every boundary intersection
208 // - we can assume polygon orientation is preserved by the splitting
209
210 if (!way.isClosed() && !otherWay.isClosed()) {
211 mergeLine(way, otherWay);
212 } else {
213 way.nodes = mergeArea(way, otherWay);
214 }
215 }
216
mergeLine(OSM::Way & way,OSM::Way & otherWay) const217 void MarbleGeometryAssembler::mergeLine(OSM::Way &way, OSM::Way &otherWay) const
218 {
219 const auto begin1 = m_dataSet->node(way.nodes.front());
220 const auto end1 = m_dataSet->node(way.nodes.back());
221 const auto begin2 = m_dataSet->node(otherWay.nodes.front());
222 const auto end2 = m_dataSet->node(otherWay.nodes.back());
223 if (!begin1 || !end1 || !begin2 || !end2) {
224 qDebug() << "failed to find way nodes!?" << begin1 << end1 << begin2 << end2;;
225 return;
226 }
227
228 way.nodes.reserve(way.nodes.size() + otherWay.nodes.size() - 2);
229 if (fuzzyEquals(end1->coordinate, begin2->coordinate)) {
230 way.nodes.pop_back();
231 std::copy(std::next(otherWay.nodes.begin()), otherWay.nodes.end(), std::back_inserter(way.nodes));
232 } else if (fuzzyEquals(end1->coordinate, end2->coordinate)) {
233 way.nodes.pop_back();
234 std::copy(std::next(otherWay.nodes.rbegin()), otherWay.nodes.rend(), std::back_inserter(way.nodes));
235 } else if (fuzzyEquals(begin1->coordinate, end2->coordinate)) {
236 way.nodes.erase(way.nodes.begin());
237 way.nodes.insert(way.nodes.begin(), otherWay.nodes.begin(), std::prev(otherWay.nodes.end()));
238 } else if (fuzzyEquals(begin1->coordinate, begin2->coordinate)) {
239 way.nodes.erase(way.nodes.begin());
240 way.nodes.insert(way.nodes.begin(), otherWay.nodes.rbegin(), std::prev(otherWay.nodes.rend()));
241 } else {
242 //qDebug() << "unable to merge line:" << begin1->coordinate << end1->coordinate << begin2->coordinate << end2->coordinate;
243 return;
244 }
245
246 otherWay.nodes.clear(); // for the caller to notice we succeeded here
247 }
248
mergeArea(OSM::Way & way,OSM::Way & otherWay) const249 std::vector<OSM::Id> MarbleGeometryAssembler::mergeArea(OSM::Way &way, OSM::Way &otherWay) const
250 {
251 // sanity checks for assumptions below
252 if (way.nodes.size() < 3 || otherWay.nodes.size() < 3 || !way.isClosed() || !otherWay.isClosed()) {
253 qCWarning(ReassemblyLog()) << "got invalid polygons!" << way.url() << way.nodes.size() << way.isClosed() << otherWay.url() << otherWay.nodes.size() << otherWay.isClosed();
254 return way.nodes.empty() ? std::move(way.nodes) : std::move(otherWay.nodes);
255 }
256
257 // "open" the closed polygons (otherwise we have to special-case the closing edges in both ways below)
258 way.nodes.pop_back();
259 otherWay.nodes.pop_back();
260
261 std::vector<OSM::Id> nodes;
262 mergeAreaSection(nodes, way.nodes, way.nodes.begin(), otherWay.nodes);
263
264 // re-close the polygon
265 if (!nodes.empty()) {
266 nodes.push_back(nodes.front());
267 }
268
269 // if otherWay is still populated we failed to find a connecting node
270 // this can happen in a number of cases, such as the same area entering a tile
271 // twice but its connecting part still being in an not yet loaded tile
272 // we defer processing those to later, so just re-close the polygon here
273 if (!otherWay.nodes.empty()) {
274 otherWay.nodes.push_back(otherWay.nodes.front());
275 }
276 return nodes;
277 }
278
mergeAreaSection(std::vector<OSM::Id> & assembledPath,std::vector<OSM::Id> & path,const std::vector<OSM::Id>::iterator & pathBegin,std::vector<OSM::Id> & otherPath) const279 bool MarbleGeometryAssembler::mergeAreaSection(std::vector<OSM::Id> &assembledPath, std::vector<OSM::Id> &path, const std::vector<OSM::Id>::iterator &pathBegin, std::vector<OSM::Id> &otherPath) const
280 {
281 for (auto nodeIt = pathBegin; nodeIt != path.end(); ++nodeIt) {
282 if ((*nodeIt) >= 0) { // not synthetic
283 continue;
284 }
285 const auto node = m_dataSet->node(*nodeIt);
286 if (!node) { // should not happen?
287 qCDebug(ReassemblyLog) << "could not find node" << (*nodeIt);
288 continue;
289 }
290
291 // TODO orientation change?
292 // synthetic node, find a matching one in the other way and splice in that way
293 for (auto otherNodeIt = otherPath.begin(); otherNodeIt != otherPath.end(); ++otherNodeIt) {
294 if ((*otherNodeIt) >= 0) {
295 continue;
296 }
297
298 const auto otherNode = m_dataSet->node(*otherNodeIt);
299 if (!otherNode) {
300 qCDebug(ReassemblyLog) << "could not find node" << (*otherNodeIt);
301 continue;
302 }
303
304 if (!fuzzyEquals(node->coordinate, otherNode->coordinate)) {
305 continue;
306 }
307
308 // found a matching synthetic node, continue in the other path
309 std::copy(pathBegin, nodeIt, std::back_inserter(assembledPath));
310 nodeIt = path.erase(pathBegin, ++nodeIt);
311 if (nodeIt == path.end()) {
312 nodeIt = path.begin();
313 }
314 otherNodeIt = otherPath.erase(otherNodeIt);
315 if (otherNodeIt == otherPath.end()) {
316 otherNodeIt = otherPath.begin();
317 }
318 // if otherPath was completely consumed, it would have switched back to us with its closing edge
319 // so add the remaining part of path here
320 if (mergeAreaSection(assembledPath, otherPath, otherNodeIt, path)) {
321 // qDebug() << " processing trailing path";
322 std::copy(nodeIt, path.end(), std::back_inserter(assembledPath));
323 std::copy(path.begin(), nodeIt, std::back_inserter(assembledPath));
324 path.clear();
325 }
326 return false;
327 }
328
329 }
330
331 // copy the final segment
332 std::copy(pathBegin, path.end(), std::back_inserter(assembledPath));
333 path.erase(pathBegin, path.end());
334
335 // wrap around when starting in the middle (can happen on the secondary path)
336 if (!path.empty()) {
337 return mergeAreaSection(assembledPath, path, path.begin(), otherPath);
338 }
339
340 return path.empty();
341 }
342
mergeRelations(OSM::DataSetMergeBuffer * mergeBuffer)343 void MarbleGeometryAssembler::mergeRelations(OSM::DataSetMergeBuffer *mergeBuffer)
344 {
345 // for relations we do:
346 // 1. restore the original id
347 // 2. replace all member ids with the restored ids for ways/relations
348 // 3. if a relations with the restored id already exists, merge with its content
349
350 for (auto &rel : mergeBuffer->relations) {
351 const OSM::Id mxoid = takeMxOid(rel);
352 if (mxoid <= 0) { // shouldn't happen?
353 m_dataSet->addRelation(std::move(rel));
354 continue;
355 }
356
357 m_relIdMap[rel.id] = mxoid;
358 rel.id = mxoid;
359
360 for (auto &member : rel.members) {
361 if (member.id >= 0) { // not a synthetic id
362 continue;
363 }
364
365 if (member.type() == OSM::Type::Node) {
366 const auto it = m_nodeIdMap.find(member.id);
367 if (it != m_nodeIdMap.end()) {
368 member.id = (*it).second;
369 }
370 } else if (member.type() == OSM::Type::Way) {
371 const auto it = m_wayIdMap.find(member.id);
372 if (it != m_wayIdMap.end()) {
373 member.id = (*it).second;
374 }
375 } else if (member.type() == OSM::Type::Relation) {
376 const auto it = m_relIdMap.find(member.id);
377 if (it != m_relIdMap.end()) {
378 member.id = (*it).second;
379 }
380 }
381 }
382
383 const auto it = std::lower_bound(m_dataSet->relations.begin(), m_dataSet->relations.end(), rel);
384 if (it != m_dataSet->relations.end() && (*it).id == rel.id) {
385 mergeRelation(*it, rel);
386 } else {
387 m_dataSet->relations.insert(it, std::move(rel));
388 }
389 }
390 }
391
mergeRelation(OSM::Relation & relation,const OSM::Relation & otherRelation) const392 void MarbleGeometryAssembler::mergeRelation(OSM::Relation& relation, const OSM::Relation& otherRelation) const
393 {
394 for (auto &otherMember : otherRelation.members) {
395 const auto it = std::find(relation.members.begin(), relation.members.end(), otherMember);
396 if (it == relation.members.end()) {
397 relation.members.push_back(otherMember);
398 }
399 }
400
401 // multi-polygons can exist entirely out of synthetic polygons, e.g. if the source was a set of lines rather than closed polygons
402 // merging those would not have happened before (as we wouldn't know what to merge it with), so we need to do this here
403 if (OSM::tagValue(relation, m_typeKey) == "multipolygon") {
404 for (auto it = relation.members.begin(); it != relation.members.end();) {
405 if ((*it).id > 0 || (*it).type() != OSM::Type::Way) {
406 ++it;
407 continue;
408 }
409 // TODO look up role names once via DataSet::role
410 if (std::strcmp((*it).role().name(), "outer") != 0 && std::strcmp((*it).role().name(), "inner") != 0) {
411 ++it;
412 continue;
413 }
414
415 auto way = m_dataSet->way((*it).id);
416 if (!way || !way->isClosed()) {
417 ++it;
418 continue;
419 }
420
421 bool merged = false;
422 for (auto it2 = std::next(it); it2 != relation.members.end(); ++it2) {
423 if ((*it2).id > 0 || (*it2).type() != OSM::Type::Way || (*it2).role() != (*it).role()) {
424 continue;
425 }
426
427 auto otherWay = m_dataSet->way((*it2).id);
428 if (!otherWay || !otherWay->isClosed()) {
429 continue;
430 }
431
432 way->nodes = mergeArea(*way, *otherWay);
433 if (otherWay->nodes.empty()) {
434 relation.members.erase(it2);
435 merged = true;
436 break;
437 }
438 }
439 if (!merged) {
440 ++it;
441 }
442 }
443 }
444 }
445
446 template<typename Elem>
takeMxOid(Elem & elem) const447 OSM::Id MarbleGeometryAssembler::takeMxOid(Elem &elem) const
448 {
449 const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), m_mxoidKey, [](const auto &lhs, const auto &rhs) { return lhs.key < rhs; });
450 if (it != elem.tags.end() && (*it).key == m_mxoidKey) {
451 bool result = false;
452 const OSM::Id id = (*it).value.toLongLong(&result);
453 if (result) {
454 elem.tags.erase(it);
455 return id;
456 }
457 }
458 return {};
459 }
460