Added module to merge buildings
Needs ReviewPublic
Actions

Authored by tandon on Aug 9 2016, 7:33 AM.

Details

Reviewers

nienhueser
rahn

Maniphest Tasks

T3346: Merge building clusters into single polygons for level 13/15

Summary

Uses DBSCAN clustering algorithm to identify building clusters and then merges these clusters using QPolygonF::united() method.

However, the buildings are not getting correctly written in the output OSM file.
We are getting buildings of the form

    <tag k="building" v="yes"/>
    <nd ref="2454247856"/>
    <nd ref="3530939281"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="1251325411"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="0"/>
    <nd ref="2454247856"/>
</way>

I suspect that it might be due to OsmWriters since I checked the generated GeoDataPlacemark of merged buildings and these were having legitimate longitude, latitude values.

Also, the regionQuery() method, which queries neighboring buildings for cluster formation purposes, has a runtime of O(n) due to which our clustering takes O(n*n) time. As discussed with @nienhueser, Once we get the output right i.e. correctly merged buildings , regionQuery() can be optimized by using Quadtrees or R-Trees.

Diff Detail

Repository

R34 Marble

Lint

Lint Skipped

Unit

Unit Tests Skipped

tandon updated this revision to Diff 5752.Aug 9 2016, 7:33 AM

tandon retitled this revision from to Added module to merge buildings.

tandon updated this object.

tandon edited the test plan for this revision. (Show Details)

tandon added reviewers: rahn, nienhueser.

tandon set the repository for this revision to R34 Marble.

tandon added subscribers: Marble, nienhueser.

tandon added a task: T3346: Merge building clusters into single polygons for level 13/15.Aug 9 2016, 7:39 AM

Node references being 0 might likely be introduced by me when working on the o5m writer in the last days. I will look into it later.

Looks great!

tools/osm-simplify/BuildingCluster.h
25	Better pass a pointer here.
tools/osm-simplify/main.cpp
452	Please use GeoDataDocumentWriter::write(outputName, *map) instead (determines file type by extension and allows saving as .o5m as well once that is fully implemented)

This patch contains fixes for 2 of the 3 major problems,

-It fixes the appearance of star shaped aberrations in the output osm file.
-It fixes the bug which caused loss in detail of merged buildings

@nienhueser suggested the fix for the star shaped aberrations on the lines of http://gis.stackexchange.com/a/60253 .
However, this fix involves buffering/offsetting the polygon. Since implementing offsetting algorithm is not trivial, Clipper(http://www.angusj.com/delphi/clipper.php) library was used so as to provide the buffer functionality.

The loss in detail of merged buildings was due to precision problems in QPolygonF::united()
This was fixed by scaling the nodes of the polygon by a factor of 10000000 and then scaling them down by the same factor.

However, the 3rd problem - loss of some buildings in the final output still persists and in fact has been aggravated by the buffering. Since merging the buildings now involves buffferings, some of the buildings get merged with their neighboring buildings but when the merged polygon is buffered negatively, it results in loss of buildings.
I have tried to correct this by testing the algorithm for different scale values taken for buffering but still this problem persists.

Input

Buffered positively (by a factor of 4.4)
(In the program buffering is not done for all the polygons at once.
In the program we iterate over the polygons of a cluster, 2 neighboring polygons are buffered positively, united and then buffered negatively. The below pic is only for representation of buffering)

Output (obtained by buffering down negatively)

As you can see , some of the buildings are dissolved in their neighboring buildings and hence disappear in the final output. This is mostly due to buffering and I think can be corrected by taking appropriate values for the scale factor, buffer factor, epsilon boundary etc.
Another reason, seems to be the neighbor selection criteria during cluster formation. Right now, due to a rectangular bounding box, some of the buildings, which are not even nearby are getting clustered together into single buildings leading to disappearance of building blocks. This can be rectified by implementing a more stricter polygon bounding box instead of a rectangle bounding box.

Revision Contents
Changeset List

		Path
A	M	src/3rdparty/polyclipping/CMakeLists.txt (12 lines)
A	M	src/3rdparty/polyclipping/clipper.hpp (395 lines)
A	M	src/3rdparty/polyclipping/clipper.cpp (4464 lines)
M		src/CMakeLists.txt (1 line)
A	M	tools/osm-simplify/BuildingBlock.h (75 lines)
A	M	tools/osm-simplify/BuildingBlock.cpp (219 lines)
A	M	tools/osm-simplify/BuildingCluster.h (35 lines)
A	M	tools/osm-simplify/BuildingCluster.cpp (56 lines)
A	M	tools/osm-simplify/BuildingDensityClustering.h (51 lines)
A	M	tools/osm-simplify/BuildingDensityClustering.cpp (169 lines)
A	M	tools/osm-simplify/BuildingMerger.h (37 lines)
A	M	tools/osm-simplify/BuildingMerger.cpp (73 lines)
M		tools/osm-simplify/CMakeLists.txt (7 lines)
M		tools/osm-simplify/main.cpp (23 lines)