[Differential] [Request, 562 lines] D3747: Building Merger
tandon (Akshat Tandon)
noreply at phabricator.kde.org
Mon Dec 19 22:24:47 UTC 2016
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.
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.
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>
To: tandon, nienhueser, rahn
Cc: nienhueser, mnafees, shentey, chaz6, dkolozsvari, cmihalache, rahn, marble-devel
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Marble-devel