File indexing completed on 2024-07-21 12:04:59

0001 // SPDX-License-Identifier: LGPL-2.1-or-later
0002 //
0003 // SPDX-FileCopyrightText: 2016 Dennis Nienhüser <nienhueser@kde.org>
0004 // SPDX-FileCopyrightText: 2016 David Kolozsvari <freedawson@gmail.com>
0005 //
0006 
0007 #include "VectorClipper.h"
0008 
0009 #include "TileId.h"
0010 
0011 #include "GeoDataLatLonAltBox.h"
0012 #include "GeoDataPolygon.h"
0013 #include "GeoDataRelation.h"
0014 #include "OsmObjectManager.h"
0015 #include "TileCoordsPyramid.h"
0016 
0017 
0018 #include <QDebug>
0019 #include <QPolygonF>
0020 #include <QPair>
0021 #include <QStringBuilder>
0022 
0023 namespace Marble {
0024 
0025 VectorClipper::VectorClipper(GeoDataDocument* document, int maxZoomLevel) :
0026     m_maxZoomLevel(maxZoomLevel)
0027 {
0028     for (auto feature: document->featureList()) {
0029         if (const auto placemark = geodata_cast<GeoDataPlacemark>(feature)) {
0030             // Select zoom level such that the placemark fits in a single tile
0031             int zoomLevel;
0032             qreal north, south, east, west;
0033             placemark->geometry()->latLonAltBox().boundaries(north, south, east, west);
0034             for (zoomLevel = maxZoomLevel; zoomLevel >= 0; --zoomLevel) {
0035                 if (TileId::fromCoordinates(GeoDataCoordinates(west, north), zoomLevel) ==
0036                         TileId::fromCoordinates(GeoDataCoordinates(east, south), zoomLevel)) {
0037                     break;
0038                 }
0039             }
0040             TileId const key = TileId::fromCoordinates(GeoDataCoordinates(west, north), zoomLevel);
0041             m_items[key] << placemark;
0042         } else if (GeoDataRelation *relation = geodata_cast<GeoDataRelation>(feature)) {
0043             m_relations << relation;
0044         } else {
0045             Q_ASSERT(false && "only placemark variants are supported so far");
0046         }
0047     }
0048 }
0049 
0050 GeoDataDocument *VectorClipper::clipTo(const GeoDataLatLonBox &tileBoundary, int zoomLevel)
0051 {
0052     bool const filterSmallAreas = zoomLevel > 10 && zoomLevel < 17;
0053     GeoDataDocument* tile = new GeoDataDocument();
0054     auto const clip = clipRect(tileBoundary);
0055     GeoDataLinearRing ring;
0056     ring << GeoDataCoordinates(tileBoundary.west(), tileBoundary.north());
0057     ring << GeoDataCoordinates(tileBoundary.east(), tileBoundary.north());
0058     ring << GeoDataCoordinates(tileBoundary.east(), tileBoundary.south());
0059     ring << GeoDataCoordinates(tileBoundary.west(), tileBoundary.south());
0060     qreal const minArea = filterSmallAreas ? 0.01 * area(ring) : 0.0;
0061     QSet<qint64> osmIds;
0062     for (GeoDataPlacemark const * placemark: potentialIntersections(tileBoundary)) {
0063         GeoDataGeometry const * const geometry = placemark ? placemark->geometry() : nullptr;
0064         if (geometry && tileBoundary.intersects(geometry->latLonAltBox())) {
0065             if (!filterSmallAreas && tileBoundary.contains(geometry->latLonAltBox())) {
0066                 tile->append(placemark->clone());
0067                 osmIds <<placemark->osmData().id();
0068             } else if (geodata_cast<GeoDataPolygon>(geometry)) {
0069                 clipPolygon(placemark, tileBoundary, clip, minArea, tile, osmIds);
0070             } else if (geodata_cast<GeoDataLineString>(geometry)) {
0071                 clipString<GeoDataLineString>(placemark, clip, minArea, tile, osmIds);
0072             } else if (geodata_cast<GeoDataLinearRing>(geometry)) {
0073                 clipString<GeoDataLinearRing>(placemark, clip, minArea, tile, osmIds);
0074             } else if (const auto building = geodata_cast<GeoDataBuilding>(geometry)) {
0075                 if (geodata_cast<GeoDataPolygon>(&static_cast<const GeoDataMultiGeometry*>(building->multiGeometry())->at(0))) {
0076                     clipPolygon(placemark, tileBoundary, clip, minArea, tile, osmIds);
0077                 } else if (geodata_cast<GeoDataLinearRing>(&static_cast<const GeoDataMultiGeometry*>(building->multiGeometry())->at(0))) {
0078                     clipString<GeoDataLinearRing>(placemark, clip, minArea, tile, osmIds);
0079                 }
0080             } else {
0081                 tile->append(placemark->clone());
0082                 osmIds << placemark->osmData().id();
0083             }
0084         }
0085     }
0086 
0087     for (auto relation: m_relations) {
0088         if (relation->containsAnyOf(osmIds)) {
0089             GeoDataRelation* multi = new GeoDataRelation;
0090             multi->osmData() = relation->osmData();
0091             tile->append(multi);
0092         }
0093     }
0094     return tile;
0095 }
0096 
0097 QVector<GeoDataPlacemark *> VectorClipper::potentialIntersections(const GeoDataLatLonBox &box) const
0098 {
0099     qreal north, south, east, west;
0100     box.boundaries(north, south, east, west);
0101     TileId const topLeft = TileId::fromCoordinates(GeoDataCoordinates(west, north), m_maxZoomLevel);
0102     TileId const bottomRight = TileId::fromCoordinates(GeoDataCoordinates(east, south), m_maxZoomLevel);
0103     QRect rect;
0104     rect.setCoords(topLeft.x(), topLeft.y(), bottomRight.x(), bottomRight.y());
0105 
0106     TileCoordsPyramid pyramid(0, m_maxZoomLevel);
0107     pyramid.setBottomLevelCoords(rect);
0108     QVector<GeoDataPlacemark *> result;
0109     for (int level = pyramid.topLevel(), maxLevel = pyramid.bottomLevel(); level <= maxLevel; ++level) {
0110         int x1, y1, x2, y2;
0111         pyramid.coords(level).getCoords(&x1, &y1, &x2, &y2);
0112         for (int x = x1; x <= x2; ++x) {
0113             for (int y = y1; y <= y2; ++y) {
0114                 result << m_items.value(TileId(0, level, x, y));
0115             }
0116         }
0117     }
0118     return result;
0119 }
0120 
0121 GeoDataDocument *VectorClipper::clipTo(unsigned int zoomLevel, unsigned int tileX, unsigned int tileY)
0122 {
0123     const GeoDataLatLonBox tileBoundary = m_tileProjection.geoCoordinates(zoomLevel, tileX, tileY);
0124 
0125     GeoDataDocument *tile = clipTo(tileBoundary, zoomLevel);
0126     QString tileName = QString("%1/%2/%3").arg(zoomLevel).arg(tileX).arg(tileY);
0127     tile->setName(tileName);
0128 
0129     return tile;
0130 }
0131 
0132 Clipper2Lib::Rect64 VectorClipper::clipRect(const GeoDataLatLonBox &box)
0133 {
0134     return { qRound64(box.west() * s_pointScale), qRound64(box.south() * s_pointScale),
0135              qRound64(box.east() * s_pointScale), qRound64(box.north() * s_pointScale) };
0136 }
0137 
0138 bool VectorClipper::canBeArea(GeoDataPlacemark::GeoDataVisualCategory visualCategory)
0139 {
0140     if (visualCategory >= GeoDataPlacemark::HighwaySteps && visualCategory <= GeoDataPlacemark::HighwayMotorway) {
0141         return false;
0142     }
0143     if (visualCategory >= GeoDataPlacemark::RailwayRail && visualCategory <= GeoDataPlacemark::RailwayFunicular) {
0144         return false;
0145     }
0146     if (visualCategory >= GeoDataPlacemark::AdminLevel1 && visualCategory <= GeoDataPlacemark::AdminLevel11) {
0147         return false;
0148     }
0149 
0150     if (visualCategory == GeoDataPlacemark::BoundaryMaritime || visualCategory == GeoDataPlacemark::InternationalDateLine) {
0151         return false;
0152     }
0153 
0154     return true;
0155 }
0156 
0157 qreal VectorClipper::area(const GeoDataLinearRing &ring)
0158 {
0159     int const n = ring.size();
0160     qreal area = 0;
0161     if (n<3) {
0162         return area;
0163     }
0164     for (int i = 1; i < n; ++i ){
0165         area += (ring[i].longitude() - ring[i-1].longitude() ) * ( ring[i].latitude() + ring[i-1].latitude());
0166     }
0167     area += (ring[0].longitude() - ring[n-1].longitude() ) * (ring[0].latitude() + ring[n-1].latitude());
0168     qreal const result = EARTH_RADIUS * EARTH_RADIUS * qAbs(area * 0.5);
0169     return result;
0170 }
0171 
0172 void VectorClipper::clipPolygon(const GeoDataPlacemark *placemark, const GeoDataLatLonBox &tileBoundary,
0173                                 const Clipper2Lib::Rect64 &clip, qreal minArea,
0174                                 GeoDataDocument *document, QSet<qint64> &osmIds)
0175 {
0176     bool isBuilding = false;
0177     GeoDataPolygon* polygon;
0178     std::unique_ptr<GeoDataPlacemark> copyPlacemark;
0179     if (const auto building = geodata_cast<GeoDataBuilding>(placemark->geometry())) {
0180         polygon = geodata_cast<GeoDataPolygon>(&static_cast<GeoDataMultiGeometry*>(building->multiGeometry())->at(0));
0181         isBuilding = true;
0182     } else {
0183         copyPlacemark.reset(new GeoDataPlacemark(*placemark));
0184         polygon = geodata_cast<GeoDataPolygon>(copyPlacemark->geometry());
0185     }
0186 
0187     if (minArea > 0.0 && area(polygon->outerBoundary()) < minArea) {
0188         return;
0189     }
0190     using namespace Clipper2Lib;
0191     Path64 path;
0192     path.reserve(qAsConst(polygon)->outerBoundary().size());
0193     for(auto const & node: qAsConst(polygon)->outerBoundary()) {
0194         path.push_back(coordinateToPoint(node));
0195     }
0196 
0197     Paths64 paths = Clipper2Lib::RectClip(clip, path);
0198     for(const auto &path: paths) {
0199         GeoDataPlacemark* newPlacemark = new GeoDataPlacemark;
0200         newPlacemark->setVisible(placemark->isVisible());
0201         newPlacemark->setVisualCategory(placemark->visualCategory());
0202         GeoDataLinearRing outerRing;
0203         OsmPlacemarkData const & placemarkOsmData = placemark->osmData();
0204         OsmPlacemarkData & newPlacemarkOsmData = newPlacemark->osmData();
0205         int index = -1;
0206         OsmPlacemarkData const & outerRingOsmData = placemarkOsmData.memberReference(index);
0207         OsmPlacemarkData & newOuterRingOsmData = newPlacemarkOsmData.memberReference(index);
0208         pathToRing(path, &outerRing, outerRingOsmData, newOuterRingOsmData);
0209 
0210         GeoDataPolygon* newPolygon = new GeoDataPolygon;
0211         newPolygon->setOuterBoundary(outerRing);
0212         if (isBuilding) {
0213             const auto building = geodata_cast<GeoDataBuilding>(placemark->geometry());
0214             GeoDataBuilding* newBuilding = new GeoDataBuilding(*building);
0215             newBuilding->multiGeometry()->clear();
0216             newBuilding->multiGeometry()->append(newPolygon);
0217             newPlacemark->setGeometry(newBuilding);
0218         } else {
0219             newPlacemark->setGeometry(newPolygon);
0220         }
0221         if (placemarkOsmData.id() > 0) {
0222             newPlacemarkOsmData.addTag(QStringLiteral("mx:oid"), QString::number(placemarkOsmData.id()));
0223         }
0224         copyTags(placemarkOsmData, newPlacemarkOsmData);
0225         copyTags(outerRingOsmData, newOuterRingOsmData);
0226         if (outerRingOsmData.id() > 0) {
0227             newOuterRingOsmData.addTag(QStringLiteral("mx:oid"), QString::number(outerRingOsmData.id()));
0228             osmIds.insert(outerRingOsmData.id());
0229         }
0230 
0231         auto const & innerBoundaries = qAsConst(polygon)->innerBoundaries();
0232         for (index = 0; index < innerBoundaries.size(); ++index) {
0233             auto const & innerBoundary = innerBoundaries.at(index);
0234             if ((minArea > 0.0 && area(innerBoundary) < minArea) || !tileBoundary.intersects(innerBoundary.latLonAltBox())) {
0235                 continue;
0236             }
0237 
0238             auto const & innerRingOsmData = placemarkOsmData.memberReference(index);
0239             // entirely contained in the tile, no need to attempt any clipping
0240             if (minArea == 0.0 && tileBoundary.contains(innerBoundary.latLonAltBox())) {
0241                 auto & newInnerRingOsmData = newPlacemarkOsmData.memberReference(newPolygon->innerBoundaries().size());
0242                 newPolygon->appendInnerBoundary(innerBoundary);
0243                 newInnerRingOsmData.setId(innerRingOsmData.id());
0244                 copyTags(innerRingOsmData, newInnerRingOsmData);
0245                 for(const auto &node: innerBoundary) {
0246                     newInnerRingOsmData.addNodeReference(node, innerRingOsmData.nodeReference(node));
0247                 }
0248                 osmIds.insert(innerRingOsmData.id());
0249                 continue;
0250             }
0251 
0252             Path64 innerPath;
0253             innerPath.reserve(innerBoundary.size());
0254             for(auto const & node: innerBoundary) {
0255                 innerPath.push_back(coordinateToPoint(node));
0256             }
0257             Paths64 innerPaths = Clipper2Lib::RectClip(clip, innerPath);
0258             for(auto const &innerPath: innerPaths) {
0259                 int const newIndex = newPolygon->innerBoundaries().size();
0260                 auto & newInnerRingOsmData = newPlacemarkOsmData.memberReference(newIndex);
0261                 GeoDataLinearRing innerRing;
0262                 pathToRing(innerPath, &innerRing, innerRingOsmData, newInnerRingOsmData);
0263                 newPolygon->appendInnerBoundary(innerRing);
0264                 if (innerRingOsmData.id() > 0) {
0265                     newInnerRingOsmData.addTag(QStringLiteral("mx:oid"), QString::number(innerRingOsmData.id()));
0266                     osmIds.insert(innerRingOsmData.id());
0267                 }
0268                 copyTags(innerRingOsmData, newInnerRingOsmData);
0269             }
0270         }
0271 
0272         OsmObjectManager::initializeOsmData(newPlacemark);
0273         document->append(newPlacemark);
0274         osmIds << placemark->osmData().id();
0275     }
0276 }
0277 
0278 void VectorClipper::copyTags(const GeoDataPlacemark &source, GeoDataPlacemark &target) const
0279 {
0280     copyTags(source.osmData(), target.osmData());
0281 }
0282 
0283 void VectorClipper::copyTags(const OsmPlacemarkData &originalPlacemarkData, OsmPlacemarkData &targetOsmData) const
0284 {
0285     for (auto iter=originalPlacemarkData.tagsBegin(), end=originalPlacemarkData.tagsEnd(); iter != end; ++iter) {
0286         targetOsmData.addTag(iter.key(), iter.value());
0287     }
0288 }
0289 
0290 }