[Differential] [Request, 562 lines] D3747: Building Merger

[tandon (Akshat Tandon)]

tandon created this revision.
tandon added reviewers: nienhueser, rahn.
tandon added a subscriber: nienhueser.
tandon set the repository for this revision to R34 Marble.
tandon added a project: Marble.

REVISION SUMMARY
  The older buildings merger was using DBSCAN clustering algorithm to identify building clusters and was then merging all the buildings in a particular cluster into a single building. However, this approach was resulting in formation of irregular buildings/polygons.
  
  This new buildings merger, instead of finding cluster of buildings, is finding buildings which share a common boundary and all the buildings which share a common boundary are then merged into a single building.
  
  The algorithm was suggested to me by @nienhueser
  
  > The idea is to construct a graph where each node is a building and two nodes are connected by an edge in case they share a common point. This could be done by using a QHash<GeoDataCoordinates, QSet<GeoDataPlacemark*> > which would be filled by iterating over all outer boundaries of the building polygons. Afterwards this data structure would have to be converted to a graph. An adjacency matrix might be an easy way to represent/construct it. In the last step the clustering could be performed in that graph: all nodes connected by edges are a cluster.
  
  After forming the graph, the program is finding strongly connected components to identify the buildings which share a common boundary. Each graph component is then merged into a single building. This is done via edge-contraction, i.e. the program takes two adjacent nodes(buildings) of a graph and merges them into a single node. It keeps on doing this for a component till a single node/building is reached.
  
  However, some problems are still persisting-
  
  In-spite of having common boundaries, QPolygonF::united() is not merging two adjacent buildings correctly.
  In order to circumvent this problem, I used clipper libraries union method. This corrected the above problem, but lead to disappearance of many building blocks.
  
  Original 
  F832602: sample.png <https://phabricator.kde.org/F832602>
  
  Merged using QPolygonF::united()
  Buildings not getting merged properly
  F832609: qpol.png <https://phabricator.kde.org/F832609>
  
  Merged using clipper library union method
  Buildings getting merged but some buildings disappear
  F832610: clipp.png <https://phabricator.kde.org/F832610>

REPOSITORY
  R34 Marble

REVISION DETAIL
  https://phabricator.kde.org/D3747

AFFECTED FILES
  tools/vectorosm-tilecreator/BuildingBlock.cpp
  tools/vectorosm-tilecreator/BuildingBlock.h
  tools/vectorosm-tilecreator/BuildingMerger.cpp
  tools/vectorosm-tilecreator/BuildingMerger.h
  tools/vectorosm-tilecreator/CMakeLists.txt
  tools/vectorosm-tilecreator/vectorosm-tilecreator.cpp

EMAIL PREFERENCES
  https://phabricator.kde.org/settings/panel/emailpreferences/

To: tandon, nienhueser, rahn
Cc: nienhueser, mnafees, shentey, chaz6, dkolozsvari, cmihalache, rahn, marble-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/marble-devel/attachments/20161219/1a802099/attachment.html>