Building Merger
Needs ReviewPublic

Authored by tandon on Dec 19 2016, 10:24 PM.

Details

Reviewers
rahn
nienhueser
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

Merged using QPolygonF::united()
Buildings not getting merged properly

Merged using clipper library union method
Buildings getting merged but some buildings disappear

Diff Detail

Repository
R34 Marble
Lint
Lint Skipped
Unit
Unit Tests Skipped
tandon retitled this revision from to Building Merger.Dec 19 2016, 10:24 PM
tandon updated this object.
tandon edited the test plan for this revision. (Show Details)
tandon added reviewers: nienhueser, rahn.
tandon set the repository for this revision to R34 Marble.
tandon added a project: Marble.
tandon added a subscriber: nienhueser.

Hi Akshat, thanks for looking into this again. I played a bit with the patch and get better results when using the IntPoint <=> GeoDataCoordinates builtin method. It remembers the association between both and restores them if possible. Clipper does not seem to guarantee that int coordinates stay exactly the same. See https://paste.kde.org/p8n7gmtm8 for an adjusted patch. I don't think that covers all cases though as the assertion also introduced in the adjusted patch still triggers, i.e. the unification returns more than one path. I wonder if this is the place where some buildings get lost?

tools/vectorosm-tilecreator/BuildingMerger.cpp
38

This creates a memory leak. Can be simplified to TagsFilter(document, Tags() << Tag("building", "*")) to avoid it

55

Needs a check for if (original->geometry()->nodeType() == GeoDataTypes::GeoDataPolygonType || original->geometry()->nodeType() == GeoDataTypes::GeoDataLinearRingType) because nodes are sometimes tagged as building as well.

Torsten @rahn, any suggestion on which tile level to show merged buildings? Here are some arguments to take into consideration: Merged buildings

  • are faster to render than single buildings
  • look "less cluttered" than single buildings
  • have no sensible house numbers and icons
  • increase the amount of data in tiles
  • can not (easily) co-exist with single buildings in tile data if the merging happens on the server side

Based on that my suggestion is to include them in level 15 (and show up to level 16), and keep the existing approach at level 17 onward.

tandon updated this revision to Diff 10425.EditedJan 22 2017, 8:13 AM
tandon marked an inline comment as done.

Clipper was not able to merge some of the adjacent buildings (buildings which only share one common point), to circumvent this problem, I made a few changes in the way in which the edges of the building graph were contracted. Instead of treating the connected components of buildings as connected graphs, I am now treating them as trees, so as to prevent any kind of cyclic dependency b/w buildings. Doing this allows me to easily break a connected component into two or more connected components whenever clipper is not able to merge two adjacent buildings.
This trick is able to greatly improve the results but still there are a few error cases, which I am not able to figure out.

Original map

Merged buildings map

Larger map

Merged larger map(some buildings not merged properly)

A small sample of buildings which are not getting merged properly

tandon marked an inline comment as done.Jan 22 2017, 9:32 AM

Thanks for the update, sounds very promising!

tools/vectorosm-tilecreator/BuildingMerger.cpp
63

I wonder if using a QHash based on a QString is a problem here. Coordinates that are not further apart than ~1 meter cannot be distinguished this way, because the default precision of toString() is 5. Using a GeoDataCoordinates based QHash as in https://paste.kde.org/pvtwivsz0 solves that. Note that you have to update to latest master to avoid a linker error related to QHash and GeoDataCoordinates. Can you check if that makes a difference for the problem cases?

tandon updated this revision to Diff 10457.Jan 23 2017, 2:36 PM
tandon marked an inline comment as done.

Changed the QHash but the error still persists.

tandon added inline comments.Jan 23 2017, 9:53 PM
tools/vectorosm-tilecreator/BuildingMerger.cpp
63

I changed that QHash to use GeoDataCoordinates but the same error still persists.