KOSMIndoorMap

marblegeometryassembler.cpp
1 /*
2  SPDX-FileCopyrightText: 2020 Volker Krause <[email protected]>
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. */
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 
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 
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 
55 void MarbleGeometryAssembler::finalize()
56 {
57  for (auto &way : m_pendingWays) {
58  m_dataSet->addWay(std::move(way));
59  }
60 }
61 
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 
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 
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 
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 
181 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 
200 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 
217 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 
249 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 
279 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 
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 
392 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>
447 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 }
OSM-based multi-floor indoor maps for buildings.
Coordinate, stored as 1e7 * degree to avoid floating point precision issues, and offset to unsigned v...
Definition: datatypes.h:37
Holds OSM elements produced by a parser prior to merging into OSM::DataSet.
void setTagValue(Elem &elem, TagKey key, const QByteArray &value)
Inserts a new tag, or updates an existing one.
Definition: datatypes.h:433
QByteArray tagValue(const Elem &elem, TagKey key)
Returns the tag value for key of elem.
Definition: datatypes.h:353
QByteArray number(int n, int base)
int64_t Id
OSM element identifier.
Definition: datatypes.h:27
qlonglong toLongLong(bool *ok, int base) const const
An OSM way.
Definition: datatypes.h:206
TagKey makeTagKey(const char *keyName, StringMemory keyMemOpt=StringMemory::Transient)
Create a tag key for the given tag name.
Definition: datatypes.cpp:17
An OSM relation.
Definition: datatypes.h:270
A set of nodes, ways and relations.
Definition: datatypes.h:283
KIOCORE_EXPORT CopyJob * move(const QUrl &src, const QUrl &dest, JobFlags flags=DefaultFlags)
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Sat Oct 23 2021 23:03:45 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.