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)
nienhueser | |
rahn |
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)
Lint Skipped |
Unit Tests Skipped |
Looks great!
tools/osm-simplify/NodeReducer.cpp | ||
---|---|---|
45 | 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. |
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:
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 | ||
---|---|---|
43 | There are two exceptions that we'd need to make here when it comes to erasing:
Your current implementation doesn't necessarily keep the end-point which needs to be changed.
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. | |
44 | I guess right now resolutionForLevel() gets evaluated for each iteration. Instead we should probably store it in a const variable. |
Fixes done in this diff
Fixes which are yet to be done
@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 | ||
---|---|---|
54 | 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 ? |
Looks Good :)
tools/osm-simplify/NodeReducer.cpp | ||
---|---|---|
45 | Can't we just rebuild and reassign the linestring? I guess that would be faster. | |
54 | 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. For now I think we can live with a copy until we have a clearer idea where to put this. |
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).
Fixes done
Modified the code so that a new LineString, consisting of reduced coordinates, gets constructed and assigned to the placemark.
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 |
Fixes Done
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. |