File indexing completed on 2024-11-24 04:15:38

 /*
     SPDX-FileCopyrightText: 2020 Volker Krause <vkrause@kde.org>
 
     SPDX-License-Identifier: LGPL-2.0-or-later
 */
 
 #include "marblegeometryassembler_p.h"
 #include "reassembly-logging.h"
 
 #include <cassert>
 
 using namespace KOSMIndoorMap;
 
 enum { NodeMatchDistance = 2 }; // in 1e7th of a degree, 46 for the old Marble data, very small for the new one
 
 /** Compare two coordinate while accounting for floating point noise. */
 static bool fuzzyEquals(OSM::Coordinate lhs, OSM::Coordinate rhs)
 {
     return std::abs((int32_t)lhs.latitude - (int32_t)rhs.latitude) <= NodeMatchDistance && std::abs((int32_t)lhs.longitude - (int32_t)rhs.longitude) <= NodeMatchDistance;
 }
 
 OSM::Id MarbleGeometryAssembler::s_nextInternalId = -(1ll << 32); // try to stay out of the way of the number space used by Marble tiles
 
 MarbleGeometryAssembler::MarbleGeometryAssembler() = default;
 MarbleGeometryAssembler::~MarbleGeometryAssembler() = default;
 
 void MarbleGeometryAssembler::setDataSet(OSM::DataSet* dataSet)
 {
     assert(dataSet);
     m_dataSet = dataSet;
     m_mxoidKey = m_dataSet->makeTagKey("mx:oid");
     m_typeKey = m_dataSet->makeTagKey("type");
 }
 
 void MarbleGeometryAssembler::merge(OSM::DataSetMergeBuffer *mergeBuffer)
 {
     assert(m_dataSet);
     m_nodeIdMap.clear();
     m_wayIdMap.clear();
     m_relIdMap.clear();
 
     std::vector<OSM::Way> prevPendingWays;
     std::swap(m_pendingWays, prevPendingWays);
 
     mergeNodes(mergeBuffer);
     deduplicateWays(mergeBuffer->ways);
     remapWayNodes(mergeBuffer->ways);
     mergeWays(mergeBuffer->ways);
     mergeWays(prevPendingWays);
     mergeRelations(mergeBuffer);
 
     mergeBuffer->clear();
 }
 
 void MarbleGeometryAssembler::finalize()
 {
     m_dataSet->ways.reserve(m_dataSet->ways.size() + m_pendingWays.size());
     for (auto &way : m_pendingWays) {
         if (!std::binary_search(m_dataSet->ways.begin(), m_dataSet->ways.end(), way)) {
             m_dataSet->ways.push_back(std::move(way));
         }
     }
     std::sort(m_dataSet->ways.begin(), m_dataSet->ways.end());
 }
 
 void MarbleGeometryAssembler::mergeNodes(OSM::DataSetMergeBuffer *mergeBuffer)
 {
     // nodes of the first batch are just taken as-is
     if (m_dataSet->nodes.empty()) {
         m_dataSet->nodes = std::move(mergeBuffer->nodes);
         std::sort(m_dataSet->nodes.begin(), m_dataSet->nodes.end());
         return;
     }
 
     // find nodes we already know
     // - for synthetic nodes those are collisions we need to remap
     // - for normal nodes, those are real duplicates and can be omitted
     // we do this in-place in the merge buffer, to avoid O(n^2) removal or insertion ops
     // (which matters here as this grows with the number of tiles we load)
     for (auto &node : mergeBuffer->nodes) {
         const auto it = std::lower_bound(m_dataSet->nodes.begin(), m_dataSet->nodes.end(), node);
         if (it != m_dataSet->nodes.end() && (*it).id == node.id) {
             if (node.id < 0) { // synthetic id collision, remap that
                 node.id = s_nextInternalId++;
                 m_nodeIdMap[(*it).id] = node.id;
             } else {
                 node.id = 0;
             }
         }
     }
 
     // append the new nodes (those not marked with id == 0), then sort the result
     m_dataSet->nodes.reserve(m_dataSet->nodes.size() + mergeBuffer->nodes.size());
     for (auto &node : mergeBuffer->nodes) {
         if (node.id) {
             m_dataSet->nodes.push_back(std::move(node));
         }
     }
     std::sort(m_dataSet->nodes.begin(), m_dataSet->nodes.end());
 }
 
 void MarbleGeometryAssembler::mergeWays(std::vector<OSM::Way> &ways)
 {
     // for ways we do:
     // 1. restore the original id
     // 2. if a way with that id already exists, we merge with the geometry of the existing one
 
     for (auto &way : ways) {
         if (way.id > 0 || way.nodes.empty()) { // not a synthetic id
             m_dataSet->addWay(std::move(way));
             continue;
         }
 
         const OSM::Id mxoid = takeMxOid(way);
         if (mxoid <= 0) { // shouldn't happen?
             m_dataSet->addWay(std::move(way));
             continue;
         }
 
         const auto syntheticId = way.id;
         way.id = mxoid;
 
         const auto it = std::lower_bound(m_dataSet->ways.begin(), m_dataSet->ways.end(), way);
         if (it != m_dataSet->ways.end() && (*it).id == way.id) {
             mergeWay(*it, way);
 
             if (way.nodes.empty()) {
                 // way was fully merged
                 m_wayIdMap[syntheticId] = mxoid;
             } else {
                 // defer to later (ie. more tiles loaded)
                 way.id = syntheticId;
                 OSM::setTagValue(way, m_mxoidKey, QByteArray::number((qlonglong)mxoid));
                 m_pendingWays.push_back(std::move(way));
             }
 
         } else {
             m_wayIdMap[syntheticId] = mxoid;
             m_dataSet->ways.insert(it, std::move(way));
         }
     }
 }
 
 static bool isDuplicateWay(const OSM::Way &lhs, const OSM::Way &rhs)
 {
     if (lhs.nodes.size() != rhs.nodes.size()) {
         return false;
     }
     for (std::size_t i = 0; i < lhs.nodes.size(); ++i) {
         if (lhs.nodes[i] != rhs.nodes[i] && (lhs.nodes[i] > 0 || rhs.nodes[i] > 0)) {
             return false;
         }
     }
     return true;
 }
 
 void MarbleGeometryAssembler::deduplicateWays(std::vector<OSM::Way>& ways)
 {
     for (auto it = ways.begin(); it != ways.end();) {
         if ((*it).id > 0) {
             ++it;
             continue;
         }
         const OSM::Id mxoid = OSM::tagValue(*it, m_mxoidKey).toLongLong();
         if (mxoid == 0) {
             ++it;
             continue;
         }
 
         const auto duplIt = m_duplicateWays.find(mxoid);
         if (duplIt != m_duplicateWays.end()) {
             bool found = false;
             for (auto it2 = (*duplIt).second.begin(); it2 != (*duplIt).second.end(); ++it2) {
                 if (isDuplicateWay(*it, ways[*it2])) {
                     m_wayIdMap[(*it).id] = mxoid;
                     qCDebug(ReassemblyLog) << "removing duplicate way:" << (*it).id << (*it).url();
                     it = ways.erase(it);
                     found = true;
                     break;
                 }
             }
             if (!found) {
                 m_duplicateWays[mxoid].push_back(std::distance(ways.begin(), it));
                 ++it;
             }
         } else {
             m_duplicateWays[mxoid] = {(std::size_t)std::distance(ways.begin(), it)};
             ++it;
         }
     }
     m_duplicateWays.clear();
 }
 
 void MarbleGeometryAssembler::remapWayNodes(std::vector<OSM::Way> &ways) const
 {
     if (m_nodeIdMap.empty()) {
         return;
     }
 
     for (auto &way : ways) {
         for (auto &id : way.nodes) {
             if (id > 0) {
                 continue;
             }
             const auto it = m_nodeIdMap.find(id);
             if (it != m_nodeIdMap.end()) {
                 id = (*it).second;
             }
         }
     }
 }
 
 void MarbleGeometryAssembler::mergeWay(OSM::Way &way, OSM::Way &otherWay) const
 {
     // for merging two ways:
     // - non-synthetic nodes remain unchanged, ways can only be merged on synthetic nodes
     // - synthetic nodes are duplicated in both sets, we need to merge them by coordinate comparison
     // - synthetic nodes can be removed, and so can edges between two adjacent synthetic nodes
     // - closed polygons at least have one shared edge (possibly multiple adjacent or non-adjacent ones)
     // - 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
     // - we can assume polygon orientation is preserved by the splitting
 
     // in some cases the Marble tile generator produces both ways and areas for the same polygon
     // e.g. for something way-like itself used in a multipolygon relations, with both being tagged
     // we ignore the way in that case and rely solely on area merging
 
     if (!way.isClosed() && !otherWay.isClosed()) {
         mergeLine(way, otherWay);
     } else if (way.isClosed() && !otherWay.isClosed()) {
         return;
     } else if (!way.isClosed() && otherWay.isClosed()) {
         std::swap(way, otherWay);
         return;
     } else {
         way.nodes = mergeArea(way, otherWay);
     }
 }
 
 void MarbleGeometryAssembler::mergeLine(OSM::Way &way, OSM::Way &otherWay) const
 {
     const auto begin1 = m_dataSet->node(way.nodes.front());
     const auto end1 = m_dataSet->node(way.nodes.back());
     const auto begin2 = m_dataSet->node(otherWay.nodes.front());
     const auto end2 = m_dataSet->node(otherWay.nodes.back());
     if (!begin1 || !end1 || !begin2 || !end2) {
         qDebug() << "failed to find way nodes!?" << begin1 << end1 << begin2 << end2;;
         return;
     }
 
     // only merge ways on synthetic nodes (the < 0 checks)
     // it is possible to end up here with mergable non-synthetic nodes, in case of a circular
     // path that the Marble tile generator classified as a line rather than an area
     // in this case we do not want to merge the nodes as that would eliminate that node
 
     way.nodes.reserve(way.nodes.size() + otherWay.nodes.size() - 2);
     if (end1->id < 0 && begin2->id < 0 && fuzzyEquals(end1->coordinate, begin2->coordinate)) {
         way.nodes.pop_back();
         std::copy(std::next(otherWay.nodes.begin()), otherWay.nodes.end(), std::back_inserter(way.nodes));
     } else if (end1->id < 0 && end2->id < 0 && fuzzyEquals(end1->coordinate, end2->coordinate)) {
         way.nodes.pop_back();
         std::copy(std::next(otherWay.nodes.rbegin()), otherWay.nodes.rend(), std::back_inserter(way.nodes));
     } else if (begin1->id < 0 && end2->id < 0 && fuzzyEquals(begin1->coordinate, end2->coordinate)) {
         way.nodes.erase(way.nodes.begin());
         way.nodes.insert(way.nodes.begin(), otherWay.nodes.begin(), std::prev(otherWay.nodes.end()));
     } else if (begin1->id < 0 && begin2->id < 0 && fuzzyEquals(begin1->coordinate, begin2->coordinate)) {
         way.nodes.erase(way.nodes.begin());
         way.nodes.insert(way.nodes.begin(), otherWay.nodes.rbegin(), std::prev(otherWay.nodes.rend()));
     } else {
         //qDebug() << "unable to merge line:" << begin1->coordinate << end1->coordinate << begin2->coordinate << end2->coordinate;
         return;
     }
 
     otherWay.nodes.clear(); // for the caller to notice we succeeded here
 }
 
 std::vector<OSM::Id> MarbleGeometryAssembler::mergeArea(OSM::Way &way, OSM::Way &otherWay) const
 {
     // sanity checks for assumptions below
     if (way.nodes.size() < 3 || otherWay.nodes.size() < 3 || !way.isClosed() || !otherWay.isClosed()) {
         qCWarning(ReassemblyLog()) << "got invalid polygons!" << way.url() << way.nodes.size() << way.isClosed() << otherWay.url() << otherWay.nodes.size() << otherWay.isClosed();
         return way.nodes.empty() ? std::move(way.nodes) : std::move(otherWay.nodes);
     }
 
     // "open" the closed polygons (otherwise we have to special-case the closing edges in both ways below)
     way.nodes.pop_back();
     otherWay.nodes.pop_back();
 
     std::vector<OSM::Id> nodes;
     mergeAreaSection(nodes, way.nodes, way.nodes.begin(), otherWay.nodes);
 
     // re-close the polygon
     if (!nodes.empty()) {
         nodes.push_back(nodes.front());
     }
 
     // if otherWay is still populated we failed to find a connecting node
     // this can happen in a number of cases, such as the same area entering a tile
     // twice but its connecting part still being in an not yet loaded tile
     // we defer processing those to later, so just re-close the polygon here
     if (!otherWay.nodes.empty()) {
         otherWay.nodes.push_back(otherWay.nodes.front());
     }
     return nodes;
 }
 
 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
 {
     for (auto nodeIt = pathBegin; nodeIt != path.end(); ++nodeIt) {
         if ((*nodeIt) >= 0) { // not synthetic
             continue;
         }
         const auto node = m_dataSet->node(*nodeIt);
         if (!node) { // should not happen?
             qCDebug(ReassemblyLog) << "could not find node" << (*nodeIt);
             continue;
         }
 
         // TODO orientation change?
         // synthetic node, find a matching one in the other way and splice in that way
         for (auto otherNodeIt = otherPath.begin(); otherNodeIt != otherPath.end(); ++otherNodeIt) {
             if ((*otherNodeIt) >= 0) {
                 continue;
             }
 
             const auto otherNode = m_dataSet->node(*otherNodeIt);
             if (!otherNode) {
                 qCDebug(ReassemblyLog) << "could not find node" << (*otherNodeIt);
                 continue;
             }
 
             if (!fuzzyEquals(node->coordinate, otherNode->coordinate)) {
                 continue;
             }
 
             // found a matching synthetic node, continue in the other path
             std::copy(pathBegin, nodeIt, std::back_inserter(assembledPath));
             nodeIt = path.erase(pathBegin, ++nodeIt);
             if (nodeIt == path.end()) {
                 nodeIt = path.begin();
             }
             otherNodeIt = otherPath.erase(otherNodeIt);
             if (otherNodeIt == otherPath.end()) {
                 otherNodeIt = otherPath.begin();
             }
             // if otherPath was completely consumed, it would have switched back to us with its closing edge
             // so add the remaining part of path here
             if (mergeAreaSection(assembledPath, otherPath, otherNodeIt, path)) {
 //                 qDebug() << "      processing trailing path";
                 std::copy(nodeIt, path.end(), std::back_inserter(assembledPath));
                 std::copy(path.begin(), nodeIt, std::back_inserter(assembledPath));
                 path.clear();
             }
             return false;
         }
 
     }
 
     // copy the final segment
     std::copy(pathBegin, path.end(), std::back_inserter(assembledPath));
     path.erase(pathBegin, path.end());
 
     // wrap around when starting in the middle (can happen on the secondary path)
     if (!path.empty()) {
         return mergeAreaSection(assembledPath, path, path.begin(), otherPath);
     }
 
     return path.empty();
 }
 
 void MarbleGeometryAssembler::mergeRelations(OSM::DataSetMergeBuffer *mergeBuffer)
 {
     // for relations we do:
     // 1. restore the original id
     // 2. replace all member ids with the restored ids for ways/relations
     // 3. if a relations with the restored id already exists, merge with its content
 
     for (auto &rel : mergeBuffer->relations) {
         const OSM::Id mxoid = takeMxOid(rel);
         if (mxoid <= 0) { // shouldn't happen?
             m_dataSet->addRelation(std::move(rel));
             continue;
         }
 
         m_relIdMap[rel.id] = mxoid;
         rel.id = mxoid;
 
         for (auto &member : rel.members) {
             if (member.id >= 0) { // not a synthetic id
                 continue;
             }
 
             if (member.type() == OSM::Type::Node) {
                 const auto it = m_nodeIdMap.find(member.id);
                 if (it != m_nodeIdMap.end()) {
                     member.id = (*it).second;
                 }
             } else if (member.type() == OSM::Type::Way) {
                 const auto it = m_wayIdMap.find(member.id);
                 if (it != m_wayIdMap.end()) {
                     member.id = (*it).second;
                 }
             } else if (member.type() == OSM::Type::Relation) {
                 const auto it = m_relIdMap.find(member.id);
                 if (it != m_relIdMap.end()) {
                     member.id = (*it).second;
                 }
             }
         }
 
         const auto it = std::lower_bound(m_dataSet->relations.begin(), m_dataSet->relations.end(), rel);
         if (it != m_dataSet->relations.end() && (*it).id == rel.id) {
             mergeRelation(*it, rel);
         } else {
             m_dataSet->relations.insert(it, std::move(rel));
         }
     }
 }
 
 void MarbleGeometryAssembler::mergeRelation(OSM::Relation& relation, const OSM::Relation& otherRelation) const
 {
     for (auto &otherMember : otherRelation.members) {
         const auto it = std::find(relation.members.begin(), relation.members.end(), otherMember);
         if (it == relation.members.end()) {
             relation.members.push_back(otherMember);
         }
     }
 
     // multi-polygons can exist entirely out of synthetic polygons, e.g. if the source was a set of lines rather than closed polygons
     // merging those would not have happened before (as we wouldn't know what to merge it with), so we need to do this here
     if (OSM::tagValue(relation, m_typeKey) == "multipolygon") {
         for (auto it = relation.members.begin(); it != relation.members.end();) {
             if ((*it).id > 0 || (*it).type() != OSM::Type::Way) {
                 ++it;
                 continue;
             }
             // TODO look up role names once via DataSet::role
             if (std::strcmp((*it).role().name(), "outer") != 0 && std::strcmp((*it).role().name(), "inner") != 0) {
                 ++it;
                 continue;
             }
 
             auto way = m_dataSet->way((*it).id);
             if (!way || !way->isClosed()) {
                 ++it;
                 continue;
             }
 
             bool merged = false;
             for (auto it2 = std::next(it); it2 != relation.members.end(); ++it2) {
                 if ((*it2).id > 0 || (*it2).type() != OSM::Type::Way || (*it2).role() != (*it).role()) {
                     continue;
                 }
 
                 auto otherWay = m_dataSet->way((*it2).id);
                 if (!otherWay || !otherWay->isClosed()) {
                     continue;
                 }
 
                 way->nodes = mergeArea(*way, *otherWay);
                 if (otherWay->nodes.empty()) {
                     relation.members.erase(it2);
                     merged = true;
                     break;
                 }
             }
             if (!merged) {
                 ++it;
             }
         }
     }
 }
 
 template<typename Elem>
 OSM::Id MarbleGeometryAssembler::takeMxOid(Elem &elem) const
 {
     const auto it = std::lower_bound(elem.tags.begin(), elem.tags.end(), m_mxoidKey, [](const auto &lhs, const auto &rhs) { return lhs.key < rhs; });
     if (it != elem.tags.end() && (*it).key == m_mxoidKey) {
         bool result = false;
         const OSM::Id id = (*it).value.toLongLong(&result);
         if (result) {
             elem.tags.erase(it);
             return id;
         }
     }
     return {};
 }