Added node reducing module to osm-simplify
ClosedPublic

Authored by tandon on Jul 3 2016, 11:55 PM.

Details

Summary

Reduces the number of nodes of a line-string.

Before Reduction

After Reduction

(This diff also contains some part of koldav's code(main.cpp) since it was not pushed to main repository)

Diff Detail

Repository
R34 Marble
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
tandon retitled this revision from to Added node reducing module to osm-simplify.Jul 3 2016, 11:55 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 updated this object.Jul 3 2016, 11:57 PM
nienhueser accepted this revision.Jul 4 2016, 3:41 AM

Looks great!

tools/osm-simplify/NodeReducer.cpp
46

Erase will run in O(n), see http://doc.qt.io/qt-5/containers.html#algorithmic-complexity and this will slow down things considerably for large input. I wonder if we can avoid that. Does not need to be part of this patch, but lets keep it in mind for a next task.

This revision is now accepted and ready to land.Jul 4 2016, 3:41 AM
rahn added a comment.Jul 4 2016, 8:03 AM

It would be nice to have a better overview regarding the results: The node-drawing debug mode in the screenshots can only give a small idea about the impact of the tool. The reason is this:

In the Marble Graphics Pipeline we do filter nodes on the fly already! This is a multiple-stage process:

  • We assign a detail level to each node as part of calling lineString::optimized() inside the file loading runners (e.g. src/plugins/runner/osm/OsmWay.cpp)
  • We then skip the nodes based on the detail level during reprojection (e.g. src/lib/marble/projections/AzimuthalProjection.cpp and src/lib/marble/projections/CylindricalProjection.cpp) . For some file formats we don't apply lineString::optimized() - in that case we compare the distance of the current node to the previous node with the displayresolution.

This process already ensures visual filtering of the nodes, and the node-debugging visualization displays only those nodes which are the leftovers already. - So actually your screenshots shouldn't differ much.
The advantage of your tool is that for huge linestrings this reduction is done in advance already and reduces memory and the work that the dynamic detail level based filtering has to do.
Therefore in this case the removal statistics based on your qDebug output would be much more useful than what is displayed in the node-debugging-screenshots!

tools/osm-simplify/NodeReducer.cpp
44

There are two exceptions that we'd need to make here when it comes to erasing:

  1. The most important exception is that Starting and End-point need to be preserved!

Your current implementation doesn't necessarily keep the end-point which needs to be changed.
Can you fix this? :)

  1. In theory also street junctions should be excluded from erasing to ensure proper rendering:

Street Junctions require a shared point between both involved streets. So these points should be preserved. However this has two problems involved: on one hand a performance problem: the continous comparisons (even when working with comparisons against start/end points in the current latLonBox) would cause a significant performance overhead. and on the other hand the current implementation inside GeoDataLineString would override any such precautions.
So this second issue isn't easy to fix - and it probably doesn't occur frequently - so let's ignore this second problem for now (but keep it on the radar in case it becomes a real issue).

45

I guess right now resolutionForLevel() gets evaluated for each iteration. Instead we should probably store it in a const variable.

tandon updated this revision to Diff 4937.EditedJul 4 2016, 1:34 PM
tandon added a project: Marble.
tandon marked an inline comment as done.
tandon added a subscriber: Marble.

Fixes done in this diff

  • Fix for always including the starting and ending points.
  • Added more geometries like polygons and linear-rings.
  • The output now displays the total number of nodes reduced for a given OSM file and zoomLevel.

Fixes which are yet to be done

  • Reducing the complexity of reducing the nodes for a given linestring from O(n^2) to something reasonable.
  • Handling road-junctions.

@rahn @nienhueser This patch is dependent on @dkolozsvari 's https://phabricator.kde.org/D2007 patch and hence can only be pushed to the main branch once the work on the latter patch is complete.

tools/osm-simplify/NodeReducer.cpp
55

I have copied the resolutionForLevel() from GeoDataLineString class since it was private; should I make the GeoDataLineString method public and static and remove the one below ?

rahn added a comment.Jul 4 2016, 3:36 PM

Looks Good :)

tools/osm-simplify/NodeReducer.cpp
46

Can't we just rebuild and reassign the linestring? I guess that would be faster.

55

I don't think that this should be part of the public API. Right now it's just part of the GeoDataLineString for reasons of convenience. After all the level<->resolution mapping is not something that would be a natural property of a linestring. I think it should go elsewhere (possibly into the viewport/tile/projection classes.
BTW: There is also an "antagonist" levelForResolution as part of the AbstractProjectionPrivate API.

For now I think we can live with a copy until we have a clearer idea where to put this.

In D2074#38482, @tandon wrote:

@rahn @nienhueser This patch is dependent on @dkolozsvari 's https://phabricator.kde.org/D2007 patch and hence can only be pushed to the main branch once the work on the latter patch is complete.

The blocking patch is now pushed.

Building up a new linestring and swapping it with the original one sounds like a good approach to me to reduce complexity from O(n^2) to O(n).

tandon updated this revision to Diff 4956.Jul 5 2016, 10:51 AM
tandon marked 4 inline comments as done.

Fixes done
Modified the code so that a new LineString, consisting of reduced coordinates, gets constructed and assigned to the placemark.

nienhueser added inline comments.Jul 9 2016, 7:58 AM
tools/osm-simplify/NodeReducer.cpp
32

Imho having uninitialized variables at the start of the function is old-school and rather dangerous. Better just move them to where they are first used and initialize them there directly.

41

m_objects should either just store GeoDataPlacemark or you need a sanity check on nodeType() here before doing the static cast.

46

Is that check useful? To me it seems to make no difference except that it slows down execution (an equality check on equal linestrings has to compare every coordinate in each of them).

53

see above

tandon updated this revision to Diff 5125.Jul 13 2016, 3:18 PM
tandon marked 3 inline comments as done.

Fixes Done

  • Moved all the variable definitions to where they are used.
  • Removed equality check before changing the geometry of a placemark.
tools/osm-simplify/NodeReducer.cpp
41

I have made NodeReducer a sub-class of PlacemarkFilter which guarantees that m_object only contains GeoDataPlacemarks. Do I still need a check on nodeType() ?

46

The NodeReducer::reduce() method was returning the input pointer in case of line-strings having less than 2 points. When placemark->setGeometry(..) is called, it deletes the previous geometry which would have been harmful if both the previous geometry and the geometry which we are going to set are same. Hence I had included the check.
However now I have modified reduce() to always return pointer of a new object thus making the check useless.

Looks good, please push.

This revision was automatically updated to reflect the committed changes.