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,62 @@ +// +// 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; + + bool merge(const BuildingBlock &block); + + void addChild(BuildingBlock::Ptr); + + QList getChildren() const; + + int id() const; + + static ClipperLib::Path obtainClipperPath(const GeoDataLinearRing &ring); + + static GeoDataLinearRing obtainGeoDataLinearRing(const ClipperLib::Path &polygon); + + +private: + PlacemarkPtr m_placemark; + GeoDataLinearRing *m_boundary; + QList m_children; + 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,188 @@ +// +// 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; +} + +void BuildingBlock::addChild(BuildingBlock::Ptr block) +{ + m_children.append(block); +} + +QList BuildingBlock::getChildren() const +{ + return m_children; +} + +ClipperLib::Path BuildingBlock::obtainClipperPath(const GeoDataLinearRing &ring) +{ +// qDebug() << "Converting from GeoDataLinearRing to clipper polygon"; + ClipperLib::Path polygon; + QVector::const_iterator itr = ring.begin(); + for (; itr != ring.end(); ++itr) { + polygon << ClipperLib::IntPoint(itr); + } + return polygon; +} + +GeoDataLinearRing BuildingBlock::obtainGeoDataLinearRing(const ClipperLib::Path &polygon) +{ +// qDebug() << "Converting from Clipper polygon to GeoDataLinearRing"; + GeoDataLinearRing ring; + for (unsigned int i = 0; i < polygon.size(); ++i) { + ring << polygon[i].coordinates(); + } + return ring; +} + +bool BuildingBlock::merge(const BuildingBlock &block) +{ + //Returns true if merge successful else false + + 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 "< 1){ + return false; + } + +// Q_ASSERT(!(mergedPolygon.size() > 1)); + + m_boundary = new GeoDataLinearRing(BuildingBlock::obtainGeoDataLinearRing(mergedPolygon[0])); + +// end +// qDebug()<<"QPolygon merged: "<< mergedPolygon; +// m_boundary = LinearRingPtr(new GeoDataLinearRing(BuildingBlock::obtainGeoDataLinearRing(mergedPolygon))); + + + /* Printing nodes */ +// for (int i = 0; i < m_boundary->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"; + } + + return true; +// 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(Marble::GeoDataDocument *document, 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,227 @@ +// +// 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 + +#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, Tags() << Tag("building", "*")) +{ + qDebug() << " **** Starting the merge *****" << endl; + m_originalBuildings = accepted()->placemarkList().size(); + BuildingMerger::coordinatesToBuildingsMapping(); + BuildingMerger::createBuildingsGraph(); + auto components = findConnectedBuildings(); + printGraph(); + contractEdges(components); + m_mergedBuildings = components.size(); + modifyDocument(document, components); +} + +void BuildingMerger::coordinatesToBuildingsMapping() +{ + int counter = 1; + foreach (GeoDataPlacemark* original, accepted()->placemarkList()) { + if (original->geometry()->nodeType() == GeoDataTypes::GeoDataPolygonType || original->geometry()->nodeType() == GeoDataTypes::GeoDataLinearRingType) { + 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); + m_hash.insert(*itr, 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) { + qDebug() << "Parent:" << block->id() << "Child:" << itr.value()->id(); + block->addChild(itr.value()); + depthFirstSearch(itr.value()); + } + ++itr; + } +} + +void BuildingMerger::contractEdges(QVector &components) +{ + int count = 0; + qDebug() << "Original components size:" << components.size(); + for (int i = 0; i < components.size(); ++i) { + BuildingBlock::Ptr block = components[i]; + count += 1; + qDebug() << "Count " << count; + QList neighbours = block->getChildren(); + 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(); + bool success = block->merge(*neighbour); + neighbours.pop_front(); + if (success) { + QList adjacentNeighbours = neighbour->getChildren(); + foreach (BuildingBlock::Ptr adjacentNeighbour, adjacentNeighbours) { + neighbours.append(adjacentNeighbour); + } + } else { + qDebug() << "Block added to components"; + components.append(neighbour); + } + } + } + qDebug() << "Modified components size:" << components.size(); +} + +void BuildingMerger::modifyDocument(GeoDataDocument *document, 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 << (*itr)->clone(); + } + + // Removing all the placemarks from the GeoDocument + document->clear(); + + // Adding all the merged building placemarks to the GeoDocument + qDebug() << "Writing to tile" << components.size() << " , number of components"; + for(auto itr = components.begin(); itr != components.end(); ++itr) { + QString hn("addr:housenumber"); + if ((*itr)->placemark()->osmData().containsTagKey(hn)) { + QString temp = (*itr)->placemark()->osmData().tagValue(hn); + qDebug()<<"Merged block house number: "<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(*itr); + } + +// 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 @@ -20,6 +20,8 @@ add_library(${TARGET} STATIC ../mbtile-import/MbTileWriter.cpp clipper/clipper.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" @@ -289,6 +290,14 @@ 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) { @@ -324,6 +333,9 @@ if (originalWays > 0) { std::cout << " , " << originalWays << " ways merged to " << mergedWays; } + if (originalBuildings > 0) { + std::cout << ", " << originalBuildings << " buildings merged to "<< mergedBuildings; + } } else { TileDirectory::printProgress(count / double(total)); std::cout << " Skipping empty tile " << count << "/" << total << " (" << tile1->name().toStdString() << ").";