diff --git a/tools/vectorosm-tilecreator/BuildingBlock.h b/tools/vectorosm-tilecreator/BuildingBlock.h new file mode 100644 --- /dev/null +++ b/tools/vectorosm-tilecreator/BuildingBlock.h @@ -0,0 +1,61 @@ +// +// This file is part of the Marble Virtual Globe. +// +// This program is free software licensed under the GNU LGPL. You can +// find a copy of this license in LICENSE.txt in the top directory of +// the source code. +// +// Copyright 2016 Akshat Tandon +// + +#ifndef MARBLE_BUILDINGBLOCK_H +#define MARBLE_BUILDINGBLOCK_H + +#include "GeoDataPlacemark.h" +#include "GeoDataLinearRing.h" +#include "clipper/clipper.hpp" + +#include +#include + +namespace Marble +{ + +class BuildingBlock +{ +private: + typedef QSharedPointer PlacemarkPtr; + typedef QSharedPointer LinearRingPtr; + +public: + typedef QSharedPointer Ptr; + + BuildingBlock(const PlacemarkPtr &placemark, int id); + + PlacemarkPtr placemark() const; + + GeoDataLinearRing *boundary() const; + + void merge(const BuildingBlock &block); + + int id() const; + + static QPolygonF obtainQPolygonF(const GeoDataLinearRing &ring); + + static GeoDataLinearRing obtainGeoDataLinearRing(const QPolygonF &polygon); + + static ClipperLib::Path obtainClipperPath(const GeoDataLinearRing &ring); + + static GeoDataLinearRing obtainGeoDataLinearRing(const ClipperLib::Path &polygon); + + +private: + PlacemarkPtr m_placemark; + GeoDataLinearRing *m_boundary; + int m_id; +}; + + +} + +#endif diff --git a/tools/vectorosm-tilecreator/BuildingBlock.cpp b/tools/vectorosm-tilecreator/BuildingBlock.cpp new file mode 100644 --- /dev/null +++ b/tools/vectorosm-tilecreator/BuildingBlock.cpp @@ -0,0 +1,208 @@ +// +// This file is part of the Marble Virtual Globe. +// +// This program is free software licensed under the GNU LGPL. You can +// find a copy of this license in LICENSE.txt in the top directory of +// the source code. +// +// Copyright 2016 Akshat Tandon +// + +#include +#include + +#include "GeoDataPlacemark.h" +#include "GeoDataPolygon.h" +#include "GeoDataLinearRing.h" +#include "GeoDataTypes.h" +#include "GeoDataCoordinates.h" +#include "OsmPlacemarkData.h" +#include "BuildingBlock.h" +#include "clipper/clipper.hpp" + +namespace Marble +{ + +BuildingBlock::BuildingBlock(const PlacemarkPtr &placemark, int id) +{ + m_id = id; + m_placemark = placemark; + GeoDataLinearRing *original; + Q_ASSERT(placemark->geometry()->nodeType() == GeoDataTypes::GeoDataPolygonType || placemark->geometry()->nodeType() == GeoDataTypes::GeoDataLinearRingType); + if (placemark->geometry()->nodeType() == GeoDataTypes::GeoDataPolygonType) { + GeoDataPolygon *polygon = static_cast(placemark->geometry()); + original = &(polygon->outerBoundary()); + } else { + original = static_cast(placemark->geometry()); + } +// m_boundary = LinearRingPtr(new GeoDataLinearRing(*original)); + m_boundary = new GeoDataLinearRing(*original); + +// qDebug()<<"BuildingBlock created"; +} + + +BuildingBlock::PlacemarkPtr BuildingBlock::placemark() const +{ + return m_placemark; +} + +GeoDataLinearRing *BuildingBlock::boundary() const +{ + return m_boundary; +} + +int BuildingBlock::id() const +{ + return m_id; +} + +ClipperLib::Path BuildingBlock::obtainClipperPath(const GeoDataLinearRing &ring) +{ +// qDebug() << "Converting from GeoDataLinearRing to clipper polygon"; + qint64 scale = 100000000; + ClipperLib::Path polygon; + QVector::const_iterator itr = ring.begin(); + for (; itr != ring.end(); ++itr) { + GeoDataCoordinates coordinates = *itr; + qreal x = coordinates.longitude() * scale; + qreal y = coordinates.latitude() * scale; + qint64 x64 = static_cast(x); + qint64 y64 = static_cast(y); +// qDebug() << "X: " << x << " Y:" << y ; + ClipperLib::IntPoint point(x64, y64); + polygon << point; + } + return polygon; +} + +GeoDataLinearRing BuildingBlock::obtainGeoDataLinearRing(const ClipperLib::Path &polygon) +{ +// qDebug() << "Converting from Clipper polygon to GeoDataLinearRing"; + qint64 scale = 100000000; + GeoDataLinearRing ring; + for (unsigned int i = 0; i < polygon.size(); ++i) { + qreal x = polygon[i].X; + qreal y = polygon[i].Y; +// qDebug() << "X:" << x/scale << "Y:" << y/scale; + GeoDataCoordinates point(x/scale, y/scale); + ring << point; + } + return ring; +} + +QPolygonF BuildingBlock::obtainQPolygonF(const GeoDataLinearRing &ring) +{ + qint64 scale = 100000000; + QPolygonF polygon; + QVector::const_iterator itr = ring.begin(); + for (; itr != ring.end(); ++itr) { + GeoDataCoordinates coordinates = *itr; + qreal x = coordinates.longitude() * scale; + qreal y = coordinates.latitude() * scale; + polygon << QPointF(x, y); + } + return polygon; +} + +GeoDataLinearRing BuildingBlock::obtainGeoDataLinearRing(const QPolygonF &polygon) +{ + qint64 scale = 100000000; + GeoDataLinearRing ring; + QVector::const_iterator itr = polygon.begin(); + for(; itr != polygon.end(); ++itr) { + QPointF point = *itr; + GeoDataCoordinates coordinates(point.rx()/scale, point.ry()/scale); + ring << coordinates; + } + return ring; +} + +void BuildingBlock::merge(const BuildingBlock &block) +{ + QString hn("addr:housenumber"); + qDebug()<<""; + qDebug()<<"Merging the following blocks"; + if (placemark()->osmData().containsTagKey(hn)) { + QString temp = placemark()->osmData().tagValue(hn); + qDebug()<<"Block 1"<osmData().containsTagKey(hn)) { + qDebug()<<"Block 2:"<osmData().tagValue(hn); + } else { + qDebug() << "No house name for block 2"; + } + +// qDebug()<<"Merging blocks:"<< id() << " and "<size(); ++i) { +// qDebug()<<"Longitude: "<< m_boundary->at(i).longitude(); +// qDebug()<<"Latitude: "<< m_boundary->at(i).latitude(); +// qDebug()<< ""; +// } + /* end printing */ +// qDebug()<<"Merged ring obtained"; + + if (block.m_placemark->geometry()->nodeType() == GeoDataTypes::GeoDataPolygonType) { +// qDebug()<<"Block2 is a polygon"; + GeoDataPolygon *blockPolygon = static_cast(block.m_placemark->geometry()); + GeoDataPolygon *thisPolygon; +// qDebug()<<"Extracted polygon of block 2"; + if (m_placemark->geometry()->nodeType() == GeoDataTypes::GeoDataPolygonType) { + thisPolygon = static_cast(m_placemark->geometry()); + + } else { + thisPolygon = new GeoDataPolygon(); + m_placemark->setGeometry(thisPolygon); + } +// qDebug()<<"Extracted polygon of block 1"; + thisPolygon->setOuterBoundary(*m_boundary); +// qDebug()<<"Outer boundary set"; + QVector &innerRings = blockPolygon->innerBoundaries(); + for(int i = 0; i < innerRings.size(); ++i) { + thisPolygon->appendInnerBoundary(innerRings.at(i)); + } +// qDebug()<<"Inner boundary set"; + } else { +// qDebug()<<"Block 2 is not a polygon"; + if (m_placemark->geometry()->nodeType() == GeoDataTypes::GeoDataPolygonType) { + GeoDataPolygon *thisPolygon = static_cast(m_placemark->geometry()); + thisPolygon->setOuterBoundary(*m_boundary); + } else { + m_placemark->setGeometry(&(*m_boundary)); + } +// qDebug()<<"Geometry set"; + } +// qDebug()<< "Merge successfull"; +} + +} diff --git a/tools/vectorosm-tilecreator/BuildingMerger.h b/tools/vectorosm-tilecreator/BuildingMerger.h new file mode 100644 --- /dev/null +++ b/tools/vectorosm-tilecreator/BuildingMerger.h @@ -0,0 +1,55 @@ +// +// This file is part of the Marble Virtual Globe. +// +// This program is free software licensed under the GNU LGPL. You can +// find a copy of this license in LICENSE.txt in the top directory of +// the source code. +// +// Copyright 2016 Akshat Tandon +// + +#ifndef MARBLE_BUILDINGMERGER_H +#define MARBLE_BUILDINGMERGER_H + + +#include "GeoDataCoordinates.h" +#include "GeoDataLinearRing.h" + +#include "TagsFilter.h" +#include "BuildingBlock.h" + +namespace Marble { + +class BuildingMerger: public TagsFilter +{ +private: + typedef QSharedPointer PlacemarkPtr; + typedef QSharedPointer LinearRingPtr; + typedef QPair Tag; + typedef QVector Tags; + +public: + BuildingMerger(GeoDataDocument *document); + int originalBuildings() const; + int mergedBuildings() const; + +private: + void coordinatesToBuildingsMapping(); + void createBuildingsGraph(); + QVector findConnectedBuildings(); + void depthFirstSearch(BuildingBlock::Ptr block); + void contractEdges(QVector components); + void printGraph() const; + void modifyDocument(QVector components); + + QVector m_blocks; + QMultiHash m_hash; + QMultiHash m_adjacencyList; + QHash m_explored; + int m_originalBuildings; + int m_mergedBuildings; +}; + +} + +#endif diff --git a/tools/vectorosm-tilecreator/BuildingMerger.cpp b/tools/vectorosm-tilecreator/BuildingMerger.cpp new file mode 100644 --- /dev/null +++ b/tools/vectorosm-tilecreator/BuildingMerger.cpp @@ -0,0 +1,212 @@ +// +// This file is part of the Marble Virtual Globe. +// +// This program is free software licensed under the GNU LGPL. You can +// find a copy of this license in LICENSE.txt in the top directory of +// the source code. +// +// Copyright 2016 Akshat Tandon +// + +#include +#include +#include +#include + +#include "GeoDataTypes.h" +#include "GeoDataPlacemark.h" +#include "GeoDataDocument.h" +#include "GeoDataObject.h" +#include "GeoDataLineString.h" +#include "GeoDataLinearRing.h" +#include "GeoDataCoordinates.h" +#include "GeoDataPolygon.h" +#include "OsmPlacemarkData.h" +#include "StyleBuilder.h" +#include "OsmObjectManager.h" + +#include "BuildingMerger.h" +#include "BuildingBlock.h" +#include "TagsFilter.h" + +#include + +namespace Marble { + +BuildingMerger::BuildingMerger(GeoDataDocument *document) : + TagsFilter(document, *( new Tags(1, *(new Tag("building", "*")))) ) +{ + qDebug() << " **** Starting the merge *****" << endl; + m_originalBuildings = accepted()->placemarkList().size(); + BuildingMerger::coordinatesToBuildingsMapping(); + BuildingMerger::createBuildingsGraph(); + auto components = findConnectedBuildings(); + printGraph(); + m_mergedBuildings = components.size(); + contractEdges(components); + modifyDocument(components); +} + +void BuildingMerger::coordinatesToBuildingsMapping() +{ + int counter = 1; + foreach (GeoDataPlacemark* original, accepted()->placemarkList()) { + PlacemarkPtr placemark = PlacemarkPtr(new GeoDataPlacemark(*original)); + BuildingBlock::Ptr block = BuildingBlock::Ptr(new BuildingBlock(placemark, counter++)); + m_blocks.append(block); + + // Creates a mapping from coordinates to buildings + for (auto itr = block->boundary()->begin(); itr != block->boundary()->end(); ++itr) { + m_hash.insert((*itr).toString(), block); + } + } +} + +void BuildingMerger::createBuildingsGraph() +{ + // Creates a graph of buildings in which there is an edge b/w two buildings iff they have a common coordinate +// qDebug()<< "Creating graph"; + for (auto itr = m_hash.keyBegin(); itr != m_hash.keyEnd(); ++itr) { + QList values = m_hash.values(*itr); + for (int i = 0; i < values.size(); ++i) { + for (int j = i + 1; j < values.size(); ++j) { +// qDebug()<< "Adding edge"; + if (!m_adjacencyList.contains(values.at(i), values.at(j)) && values.at(i) != values.at(j)) { + qDebug()<<"Inserting edge b/w"<< values.at(i)->id() <<" -- "<< values.at(j)->id(); + m_adjacencyList.insert(values.at(i), values.at(j)); + } + if (!m_adjacencyList.contains(values.at(j), values.at(i)) && values.at(i) != values.at(j)) { + qDebug()<<"Inserting edge b/w"<< values.at(j)->id() <<" -- "<< values.at(i)->id(); + m_adjacencyList.insert(values.at(j), values.at(i)); + } + } + } + } +} + +void BuildingMerger::printGraph() const { + qDebug()<<"Graph"; + foreach (BuildingBlock::Ptr block, m_blocks) { +// qDebug()<<""; + std::cout <<"Node:"<< block->id() << ": "; + QList neighbours = m_adjacencyList.values(block); +// if (neighbours.size() != 0){ +// std::cout <<"Neighbours:"; +// } + for(auto itr = neighbours.begin(); itr != neighbours.end(); ++itr) { + std::cout << (*itr)->id() << " , "; + } +// qDebug() << " "; + std::cout << std::endl; + } + +} + +QVector BuildingMerger::findConnectedBuildings() +{ + foreach (BuildingBlock::Ptr block, m_blocks) { + m_explored.insert(block, false); + } + + QVector components; + foreach (BuildingBlock::Ptr block, m_blocks) { + if (m_explored[block] == false) { + components.append(block); + depthFirstSearch(block); + } + } + + qDebug()<< ""; + qDebug()<< "Number of buildings:"<< m_originalBuildings; + qDebug()<< "Number of components:"<< components.size(); + qDebug()<< ""; + qDebug()<<"Component blocks:"; + foreach (BuildingBlock::Ptr block, components) { + qDebug()<<"Block:"<< block->id(); + } + + return components; +} + +void BuildingMerger::depthFirstSearch(BuildingBlock::Ptr block) +{ + m_explored[block] = true; + auto itr = m_adjacencyList.find(block); + while (itr != m_adjacencyList.end() && itr.key() == block) { + if (m_explored[itr.value()] == false) { + depthFirstSearch(itr.value()); + } + ++itr; + } +} + +void BuildingMerger::contractEdges(QVector components) +{ + foreach (BuildingBlock::Ptr block, components) { + QList neighbours = m_adjacencyList.values(block); + while (neighbours.size() != 0) { + BuildingBlock::Ptr neighbour = neighbours.first(); + qDebug()<<"Current neighbours"; + foreach(BuildingBlock::Ptr x, neighbours){ + qDebug()<< x->id(); + } + +// qDebug()<<"Starting the merge"; + qDebug() << "Merging the nodes:" << block->id() << "--" << neighbour->id(); + block->merge(*neighbour); + neighbours.pop_front(); + QList adjacentNeighbours = m_adjacencyList.values(neighbour); + foreach (BuildingBlock::Ptr adjacentNeighbour, adjacentNeighbours) { + if (!neighbours.contains(adjacentNeighbour) && adjacentNeighbour != block) { + neighbours.append(adjacentNeighbour); +// qDebug()<< "Appending adjacent neighbour"; + } + if (m_adjacencyList.contains(adjacentNeighbour, neighbour)) { + m_adjacencyList.remove(adjacentNeighbour, neighbour); +// m_adjacencyList.insert(adjacentNeighbour, block); + } + } + m_adjacencyList.remove(neighbour); + } + } +} + +void BuildingMerger::modifyDocument(QVector components) +{ + qDebug()<<" Original number of placemarks:" << placemarks().size(); + // Extracting non-building placemarks from the GeoDocument + QVector rejectedPlacemarks; + for(auto itr = rejectedObjectsBegin(); itr != rejectedObjectsEnd(); ++itr) { + rejectedPlacemarks.append(**itr); + } + + // Removing all the placemarks from the GeoDocument + document()->clear(); + + // Adding all the merged building placemarks to the GeoDocument + for(auto itr = components.begin(); itr != components.end(); ++itr) { + GeoDataPlacemark *placemark = new GeoDataPlacemark(*((*itr)->placemark())); + document()->append(placemark); + } + + // Adding all the non-building placemarks to the GeoDocument + for(auto itr = rejectedPlacemarks.begin(); itr != rejectedPlacemarks.end(); ++itr) { + GeoDataPlacemark *placemark = new GeoDataPlacemark(*itr); + document()->append(placemark); + } + + qDebug()<<" Reduced number of placemarks:" << placemarks().size(); + +} + +int BuildingMerger::originalBuildings() const +{ + return m_originalBuildings; +} + +int BuildingMerger::mergedBuildings() const +{ + return m_mergedBuildings; +} + +} diff --git a/tools/vectorosm-tilecreator/CMakeLists.txt b/tools/vectorosm-tilecreator/CMakeLists.txt --- a/tools/vectorosm-tilecreator/CMakeLists.txt +++ b/tools/vectorosm-tilecreator/CMakeLists.txt @@ -22,6 +22,8 @@ clipper/clipper.cpp BaseClipper.cpp BaseFilter.cpp +BuildingBlock.cpp +BuildingMerger.cpp NodeReducer.cpp PeakAnalyzer.cpp SpellChecker.cpp diff --git a/tools/vectorosm-tilecreator/vectorosm-tilecreator.cpp b/tools/vectorosm-tilecreator/vectorosm-tilecreator.cpp --- a/tools/vectorosm-tilecreator/vectorosm-tilecreator.cpp +++ b/tools/vectorosm-tilecreator/vectorosm-tilecreator.cpp @@ -36,6 +36,7 @@ #include "VectorClipper.h" #include "NodeReducer.h" #include "WayConcatenator.h" +#include "BuildingMerger.h" #include "TileIterator.h" #include "TileDirectory.h" #include "MbTileWriter.h" @@ -280,13 +281,24 @@ typedef QSharedPointer GeoDocPtr; GeoDocPtr tile1 = GeoDocPtr(mapTiles.clip(zoomLevel, tileId.x(), tileId.y())); TagsFilter::removeAnnotationTags(tile1.data()); + int originalWays = 0; int mergedWays = 0; if (zoomLevel < 17) { WayConcatenator concatenator(tile1.data()); originalWays = concatenator.originalWays(); mergedWays = concatenator.mergedWays(); } + + int originalBuildings = 0; + int mergedBuildings = 0; + if (zoomLevel <= 17) { + BuildingMerger buildingMerger(tile1.data()); + originalBuildings = buildingMerger.originalBuildings(); + mergedBuildings = buildingMerger.mergedBuildings(); + } + + NodeReducer nodeReducer(tile1.data(), tileId); GeoDocPtr tile2 = GeoDocPtr(loader.clip(zoomLevel, tileId.x(), tileId.y())); if (tile1->size() > 0 && tile2->size() > 0) { @@ -326,7 +338,17 @@ TileDirectory::printProgress(count / double(total)); std::cout << " Skipping empty tile " << count << "/" << total << " (" << tile1->name().toStdString() << ")."; } - + TileDirectory::printProgress(count / double(total)); + std::cout << " Tile " << count << "/" << total << " ("; + std::cout << combined->name().toStdString() << ")."; + double const reduction = nodeReducer.removedNodes() / qMax(1.0, double(nodeReducer.remainingNodes() + nodeReducer.removedNodes())); + std::cout << " Node reduction: " << qRound(reduction * 100.0) << "%"; + if (originalWays > 0) { + std::cout << " , " << originalWays << " ways merged to " << mergedWays; + } + if (originalBuildings > 0){ + std::cout << ", " << originalBuildings << " buildings merged to "<< mergedBuildings; + } std::cout << std::string(20, ' ') << '\r'; std::cout.flush(); }