diff --git a/src/map/loader/maploader.cpp b/src/map/loader/maploader.cpp index 68ca004..5e82634 100644 --- a/src/map/loader/maploader.cpp +++ b/src/map/loader/maploader.cpp @@ -1,175 +1,176 @@ /* Copyright (C) 2020 Volker Krause This program is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include "maploader.h" #include "boundarysearch.h" #include #include #include #include #include enum { TileZoomLevel = 17 }; inline void initResources() // needs to be outside of a namespace { Q_INIT_RESOURCE(assets); } using namespace KOSMIndoorMap; MapLoader::MapLoader(QObject *parent) : QObject(parent) { initResources(); connect(&m_tileCache, &TileCache::tileLoaded, this, &MapLoader::downloadFinished); } MapLoader::~MapLoader() = default; void MapLoader::loadFromO5m(const QString &fileName) { QElapsedTimer loadTime; loadTime.start(); QFile f(fileName); if (!f.open(QFile::ReadOnly)) { qCritical() << f.fileName() << f.errorString(); return; } const auto data = f.map(0, f.size()); OSM::DataSet ds; OSM::O5mParser p(&ds); p.parse(data, f.size()); m_data.setDataSet(std::move(ds)); qDebug() << "o5m loading took" << loadTime.elapsed() << "ms"; Q_EMIT done(); } void MapLoader::loadForCoordinate(double lat, double lon) { m_tileBbox = {}; m_pendingTiles.clear(); m_boundarySearcher.init(OSM::Coordinate(lat, lon)); const auto tile = Tile::fromCoordinate(lat, lon, TileZoomLevel); m_pendingTiles.push_back(tile); m_loadedTiles = QRect(tile.x, tile.y, 1, 1); downloadTiles(); } MapData&& MapLoader::takeData() { return std::move(m_data); } void MapLoader::downloadTiles() { for (const auto &tile : m_pendingTiles) { m_tileCache.ensureCached(tile); } if (m_tileCache.pendingDownloads() == 0) { loadTiles(); } else { Q_EMIT isLoadingChanged(); } } void MapLoader::downloadFinished() { if (m_tileCache.pendingDownloads() > 0) { return; } loadTiles(); } void MapLoader::loadTiles() { QElapsedTimer loadTime; loadTime.start(); OSM::O5mParser p(&m_dataSet); //p.setMergeBuffer(&m_mergeBuffer); for (const auto &tile : m_pendingTiles) { const auto fileName = m_tileCache.cachedTile(tile); qDebug() << fileName; QFile f(fileName); if (!f.open(QFile::ReadOnly)) { qWarning() << f.fileName() << f.errorString(); break; } const auto data = f.map(0, f.size()); p.parse(data, f.size()); //m_marbleMerger.merge(&m_dataSet, &m_mergeBuffer); m_tileBbox = OSM::unite(m_tileBbox, tile.boundingBox()); } m_pendingTiles.clear(); const auto bbox = m_boundarySearcher.boundingBox(m_dataSet); qDebug() << "needed bbox:" << bbox << "got:" << m_tileBbox << m_loadedTiles; // expand left and right if (bbox.min.longitude < m_tileBbox.min.longitude) { m_loadedTiles.setLeft(m_loadedTiles.left() - 1); for (int y = m_loadedTiles.top(); y <= m_loadedTiles.bottom(); ++y) { m_pendingTiles.push_back(Tile(m_loadedTiles.left(), y, TileZoomLevel)); } } if (bbox.max.longitude > m_tileBbox.max.longitude) { m_loadedTiles.setRight(m_loadedTiles.right() + 1); for (int y = m_loadedTiles.top(); y <= m_loadedTiles.bottom(); ++y) { m_pendingTiles.push_back(Tile(m_loadedTiles.right(), y, TileZoomLevel)); } } // expand top/bottom: note that geographics and slippy map tile coordinates have a different understanding on what is "top" if (bbox.max.latitude > m_tileBbox.max.latitude) { m_loadedTiles.setTop(m_loadedTiles.top() - 1); for (int x = m_loadedTiles.left(); x <= m_loadedTiles.right(); ++x) { m_pendingTiles.push_back(Tile(x, m_loadedTiles.top(), TileZoomLevel)); } } if (bbox.min.latitude < m_tileBbox.min.latitude) { m_loadedTiles.setBottom(m_loadedTiles.bottom() + 1); for (int x = m_loadedTiles.left(); x <= m_loadedTiles.right(); ++x) { m_pendingTiles.push_back(Tile(x, m_loadedTiles.bottom(), TileZoomLevel)); } } if (!m_pendingTiles.empty()) { downloadTiles(); return; } + //m_marbleMerger.finalize(&m_dataSet, &m_mergeBuffer); m_data.setDataSet(std::move(m_dataSet)); m_data.setBoundingBox(bbox); qDebug() << "o5m loading took" << loadTime.elapsed() << "ms"; Q_EMIT isLoadingChanged(); Q_EMIT done(); } bool MapLoader::isLoading() const { return m_tileCache.pendingDownloads() > 0; } diff --git a/src/map/loader/marblegeometryassembler.cpp b/src/map/loader/marblegeometryassembler.cpp index cf409f5..cddc137 100644 --- a/src/map/loader/marblegeometryassembler.cpp +++ b/src/map/loader/marblegeometryassembler.cpp @@ -1,289 +1,321 @@ /* Copyright (C) 2020 Volker Krause This program is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include "marblegeometryassembler.h" using namespace KOSMIndoorMap; /** 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) < 10 && std::abs((int32_t)lhs.longitude - (int32_t)rhs.longitude) < 10; } void MarbleGeometryAssembler::merge(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer) { + m_dataSet = dataSet; m_wayIdMap.clear(); m_relIdMap.clear(); m_mxoidKey = dataSet->tagKey("mx:oid"); - mergeNodes(dataSet, mergeBuffer); - mergeWays(dataSet, mergeBuffer); - mergeRelations(dataSet, mergeBuffer); + mergeNodes(mergeBuffer); + mergeWays(mergeBuffer); + mergeRelations(mergeBuffer); mergeBuffer->clear(); + std::swap(m_pendingWays, mergeBuffer->ways); // ways we have to try again + m_dataSet = nullptr; } -void MarbleGeometryAssembler::mergeNodes(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer) +void MarbleGeometryAssembler::finalize(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer) +{ + for (auto &way : mergeBuffer->ways) { + dataSet->addWay(std::move(way)); + } +} + +void MarbleGeometryAssembler::mergeNodes(OSM::DataSetMergeBuffer *mergeBuffer) { // nodes we just take as-is, they are not split/renamed; at worst we get a few extra for split geometry - if (dataSet->nodes.empty()) { - dataSet->nodes = std::move(mergeBuffer->nodes); - std::sort(dataSet->nodes.begin(), dataSet->nodes.end()); + if (m_dataSet->nodes.empty()) { + m_dataSet->nodes = std::move(mergeBuffer->nodes); + std::sort(m_dataSet->nodes.begin(), m_dataSet->nodes.end()); } else { - dataSet->nodes.reserve(dataSet->nodes.size() + mergeBuffer->nodes.size()); - std::move(mergeBuffer->nodes.begin(), mergeBuffer->nodes.end(), std::back_inserter(dataSet->nodes)); + m_dataSet->nodes.reserve(m_dataSet->nodes.size() + mergeBuffer->nodes.size()); + std::move(mergeBuffer->nodes.begin(), mergeBuffer->nodes.end(), std::back_inserter(m_dataSet->nodes)); } - std::sort(dataSet->nodes.begin(), dataSet->nodes.end()); + std::sort(m_dataSet->nodes.begin(), m_dataSet->nodes.end()); } -void MarbleGeometryAssembler::mergeWays(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer) +void MarbleGeometryAssembler::mergeWays(OSM::DataSetMergeBuffer *mergeBuffer) { // 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 : mergeBuffer->ways) { if (way.id > 0) { // not a synthetic id - dataSet->addWay(std::move(way)); + m_dataSet->addWay(std::move(way)); continue; } const OSM::Id mxoid = takeMxOid(way); if (mxoid <= 0) { // shouldn't happen? - dataSet->addWay(std::move(way)); + m_dataSet->addWay(std::move(way)); continue; } - m_wayIdMap[way.id] = mxoid; + const auto syntheticId = way.id; way.id = mxoid; - const auto it = std::lower_bound(dataSet->ways.begin(), dataSet->ways.end(), way); - if (it != dataSet->ways.end() && (*it).id == way.id) { - mergeWay(dataSet, *it, way); + 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; + m_pendingWays.push_back(std::move(way)); + } + } else { - dataSet->ways.insert(it, std::move(way)); + m_wayIdMap[syntheticId] = mxoid; + m_dataSet->ways.insert(it, std::move(way)); } } } -void MarbleGeometryAssembler::mergeWay(const OSM::DataSet *dataSet, OSM::Way &way, OSM::Way &otherWay) const +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 if (!way.isClosed() && !otherWay.isClosed()) { - mergeLine(dataSet, way, otherWay); + mergeLine(way, otherWay); } else { - way.nodes = mergeArea(dataSet, way, otherWay); + way.nodes = mergeArea(way, otherWay); } } -void MarbleGeometryAssembler::mergeLine(const OSM::DataSet *dataSet, OSM::Way &way, const OSM::Way &otherWay) const +void MarbleGeometryAssembler::mergeLine(OSM::Way &way, OSM::Way &otherWay) const { - const auto begin1 = nodeForId(dataSet, way.nodes.front()); - const auto end1 = nodeForId(dataSet, way.nodes.back()); - const auto begin2 = nodeForId(dataSet, otherWay.nodes.front()); - const auto end2 = nodeForId(dataSet, otherWay.nodes.back()); + const auto begin1 = nodeForId(way.nodes.front()); + const auto end1 = nodeForId(way.nodes.back()); + const auto begin2 = nodeForId(otherWay.nodes.front()); + const auto end2 = nodeForId(otherWay.nodes.back()); if (!begin1 || !end1 || !begin2 || !end2) { qDebug() << "failed to find way nodes!?" << begin1 << end1 << begin2 << end2;; return; } // TODO drop the extra synthetic nodes way.nodes.reserve(way.nodes.size() + otherWay.nodes.size()); if (fuzzyEquals(end1->coordinate, begin2->coordinate)) { std::copy(otherWay.nodes.begin(), otherWay.nodes.end(), std::back_inserter(way.nodes)); } else if (fuzzyEquals(end1->coordinate, end2->coordinate)) { std::copy(otherWay.nodes.rbegin(), otherWay.nodes.rend(), std::back_inserter(way.nodes)); } else if (fuzzyEquals(begin1->coordinate, end2->coordinate)) { way.nodes.insert(way.nodes.begin(), otherWay.nodes.begin(), otherWay.nodes.end()); } else if (fuzzyEquals(begin1->coordinate, begin2->coordinate)) { way.nodes.insert(way.nodes.begin(), otherWay.nodes.rbegin(), 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 MarbleGeometryAssembler::mergeArea(const OSM::DataSet *dataSet, OSM::Way &way, OSM::Way &otherWay) const +std::vector 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()) { qWarning() << "got invalid polygons!"; return way.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 nodes; - mergeAreaSection(dataSet, nodes, way.nodes, way.nodes.begin(), otherWay.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(const OSM::DataSet *dataSet, std::vector &assembledPath, std::vector &path, const std::vector::iterator &pathBegin, std::vector &otherPath) const +bool MarbleGeometryAssembler::mergeAreaSection(std::vector &assembledPath, std::vector &path, const std::vector::iterator &pathBegin, std::vector &otherPath) const { for (auto nodeIt = pathBegin; nodeIt != path.end(); ++nodeIt) { if ((*nodeIt) >= 0) { // not synthetic continue; } - const auto node = nodeForId(dataSet, (*nodeIt)); + const auto node = nodeForId(*nodeIt); if (!node) { // should not happen? qDebug() << "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 = nodeForId(dataSet, (*otherNodeIt)); + const auto otherNode = nodeForId(*otherNodeIt); if (!otherNode) { qDebug() << "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(dataSet, assembledPath, otherPath, otherNodeIt, path)) { + 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(dataSet, assembledPath, path, path.begin(), otherPath); + return mergeAreaSection(assembledPath, path, path.begin(), otherPath); } return path.empty(); } -void MarbleGeometryAssembler::mergeRelations(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer) +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? - dataSet->addRelation(std::move(rel)); + 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::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(dataSet->relations.begin(), dataSet->relations.end(), rel); - if (it != dataSet->relations.end() && (*it).id == rel.id) { + 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 { - dataSet->relations.insert(it, std::move(rel)); + 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); } } } template 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 {}; } -const OSM::Node* MarbleGeometryAssembler::nodeForId(const OSM::DataSet *dataSet, OSM::Id id) const +const OSM::Node* MarbleGeometryAssembler::nodeForId(OSM::Id id) const { - const auto it = std::lower_bound(dataSet->nodes.begin(), dataSet->nodes.end(), id); - if (it != dataSet->nodes.end() && (*it).id == id) { + const auto it = std::lower_bound(m_dataSet->nodes.begin(), m_dataSet->nodes.end(), id); + if (it != m_dataSet->nodes.end() && (*it).id == id) { return &(*it); } return nullptr; } diff --git a/src/map/loader/marblegeometryassembler.h b/src/map/loader/marblegeometryassembler.h index 8ffd9d5..062905b 100644 --- a/src/map/loader/marblegeometryassembler.h +++ b/src/map/loader/marblegeometryassembler.h @@ -1,61 +1,70 @@ /* Copyright (C) 2020 Volker Krause This program is free software; you can redistribute it and/or modify it under the terms of the GNU Library General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #ifndef KOSMINDOORMAP_MARBLEGEOMETRYASSEMBLER_H #define KOSMINDOORMAP_MARBLEGEOMETRYASSEMBLER_H #include #include #include namespace KOSMIndoorMap { /** Re-assemble broken up geometry in Marble vector tiles. */ class MarbleGeometryAssembler { public: + /** Merge @p mergeBuffer into @p dataSet. + * Data not mergable at this point (e.g. due to missing connecting tiles) + * remains in @p mergeBuffer. + */ void merge(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer); + /** Processes remaining elements that couldn't be merged. */ + void finalize(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer); private: - void mergeNodes(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer); - void mergeWays(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer); - void mergeRelations(OSM::DataSet *dataSet, OSM::DataSetMergeBuffer *mergeBuffer); + void mergeNodes(OSM::DataSetMergeBuffer *mergeBuffer); + void mergeWays(OSM::DataSetMergeBuffer *mergeBuffer); + void mergeRelations(OSM::DataSetMergeBuffer *mergeBuffer); - void mergeWay(const OSM::DataSet *dataSet, OSM::Way &way, OSM::Way &otherWay) const; - void mergeLine(const OSM::DataSet *dataSet, OSM::Way &way, const OSM::Way &otherWay) const; - std::vector mergeArea(const OSM::DataSet *dataSet, OSM::Way &way, OSM::Way &otherWay) const; + void mergeWay(OSM::Way &way, OSM::Way &otherWay) const; + void mergeLine(OSM::Way &way, OSM::Way &otherWay) const; + std::vector mergeArea(OSM::Way &way, OSM::Way &otherWay) const; /** * @returns @c true when @p path has been completely processed, @c false otherwise */ - bool mergeAreaSection(const OSM::DataSet *dataSet, std::vector &assembledPath, std::vector &path, const std::vector::iterator &pathBegin, std::vector &otherPath) const; + bool mergeAreaSection(std::vector &assembledPath, std::vector &path, const std::vector::iterator &pathBegin, std::vector &otherPath) const; void mergeRelation(OSM::Relation &relation, const OSM::Relation &otherRelation) const; template OSM::Id takeMxOid(Elem &elem) const; - const OSM::Node* nodeForId(const OSM::DataSet *dataSet, OSM::Id id) const; + const OSM::Node* nodeForId(OSM::Id id) const; + OSM::DataSet *m_dataSet = nullptr; OSM::TagKey m_mxoidKey; std::unordered_map m_wayIdMap; std::unordered_map m_relIdMap; + + std::vector m_pendingWays; }; } #endif // KOSMINDOORMAP_MARBLEGEOMETRYASSEMBLER_H