Differential D2074 Diff 5132 tools/osm-simplify/NodeReducer.cpp

Changeset View

Standalone View

View Options

tools/osm-simplify/NodeReducer.cpp

  • This file was added.
1​//
2​// This file is part of the Marble Virtual Globe.
3​//
4​// This program is free software licensed under the GNU LGPL. You can
5​// find a copy of this license in LICENSE.txt in the top directory of
6​// the source code.
7​//
8​// Copyright 2016 Akshat Tandon <akshat.tandon@research.iiit.ac.in>
9​//
10​
11​#include "BaseClipper.h"
12​#include "GeoDataPlacemark.h"
13​#include "GeoDataTypes.h"
14​#include "GeoDataLineString.h"
15​#include "GeoDataCoordinates.h"
16​#include "MarbleMath.h"
17​#include "NodeReducer.h"
18​
19​#include <QDebug>
20​#include <QVector>
21​
22​NodeReducer::NodeReducer(GeoDataDocument* document, int zoomLevel) :
23​ PlacemarkFilter(document)
24​{
25​ m_resolution = resolutionForLevel(zoomLevel);
26​ m_count = 0;
27​}
28​
29​void NodeReducer::process()
30​{
31​ foreach (GeoDataObject* object, m_objects) {
32​
nienhueserUnsubmitted
Done

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.

nienhueser: Imho having uninitialized variables at the start of the function is old-school and rather…
33​ GeoDataPlacemark* placemark = static_cast<GeoDataPlacemark*>(object);
34​
35​ if(placemark->geometry()->nodeType() == GeoDataTypes::GeoDataLineStringType){
36​ GeoDataLineString* prevLine = static_cast<GeoDataLineString*>(placemark->geometry());
37​ GeoDataLineString* reducedLine = reduce(prevLine);
38​ placemark->setGeometry(reducedLine);
39​ }
40​
41​ else if(placemark->geometry()->nodeType() == GeoDataTypes::GeoDataLinearRingType){
nienhueserUnsubmitted
Not Done

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

nienhueser: m_objects should either just store GeoDataPlacemark or you need a sanity check on nodeType()…
tandonAuthorUnsubmitted
Not Done

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() ?

tandon: I have made NodeReducer a sub-class of PlacemarkFilter which guarantees that m_object only…
42​ GeoDataLinearRing* prevRing = static_cast<GeoDataLinearRing*>(placemark->geometry());
43​ GeoDataLinearRing* reducedRing = static_cast<GeoDataLinearRing*>(reduce(prevRing));
44​ placemark->setGeometry(reducedRing);
rahnUnsubmitted
Not Done

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).

rahn: There are two exceptions that we'd need to make here when it comes to erasing: 1. The most…
45​ }
rahnUnsubmitted
Done

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

rahn: I guess right now resolutionForLevel() gets evaluated for each iteration. Instead we should…
46​
nienhueserUnsubmitted
Done

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.

nienhueser: Erase will run in O(n), see http://doc.qt.io/qt-5/containers.html#algorithmic-complexity and…
rahnUnsubmitted
Done

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

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

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).

nienhueser: Is that check useful? To me it seems to make no difference except that it slows down execution…
tandonAuthorUnsubmitted
Not Done

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.

tandon: The NodeReducer::reduce() method was returning the input pointer in case of line-strings having…
47​ else if(placemark->geometry()->nodeType() == GeoDataTypes::GeoDataPolygonType){
48​ GeoDataPolygon* reducedPolygon = new GeoDataPolygon;
49​ GeoDataPolygon* prevPolygon = static_cast<GeoDataPolygon*>(placemark->geometry());
50​ GeoDataLinearRing* prevRing = &(prevPolygon->outerBoundary());
51​ GeoDataLinearRing* reducedRing = static_cast<GeoDataLinearRing*>(reduce(prevRing));
52​ reducedPolygon->setOuterBoundary(*reducedRing);
53​ QVector<GeoDataLinearRing>& innerBoundaries = prevPolygon->innerBoundaries();
nienhueserUnsubmitted
Done

see above

nienhueser: see above
54​ for(int i = 0; i < innerBoundaries.size(); i++){
55​ prevRing = &innerBoundaries[i];
tandonAuthorUnsubmitted
Done

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 ?

tandon: I have copied the resolutionForLevel() from GeoDataLineString class since it was private…
rahnUnsubmitted
Done

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.

rahn: I don't think that this should be part of the public API. Right now it's just part of the…
56​ reducedRing = static_cast<GeoDataLinearRing*>(reduce(prevRing));
57​ reducedPolygon->appendInnerBoundary(*reducedRing);
58​ }
59​ placemark->setGeometry(reducedPolygon);
60​ }
61​ }
62​ qDebug()<<"Total nodes reduced: "<<m_count<<endl;
63​}
64​
65​GeoDataLineString* NodeReducer::reduce(GeoDataLineString* lineString){
66​ qint64 prevSize = lineString->size();
67​
68​ GeoDataLineString* reducedLine;
69​ if(lineString->nodeType() == GeoDataTypes::GeoDataLineStringType){
70​ if(prevSize < 2){
71​ reducedLine = new GeoDataLineString(*lineString);
72​ return reducedLine;
73​ }
74​ else{
75​ reducedLine = new GeoDataLineString;
76​ }
77​ }
78​ else if(lineString->nodeType() == GeoDataTypes::GeoDataLinearRingType){
79​ if(prevSize < 2){
80​ reducedLine = new GeoDataLinearRing(*lineString);
81​ return reducedLine;
82​ }
83​ reducedLine = new GeoDataLinearRing;
84​ }
85​
86​
87​ QVector<GeoDataCoordinates>::iterator itCoords = lineString->begin();
88​ GeoDataCoordinates currentCoords = *itCoords;
89​ reducedLine->append(*itCoords);
90​ ++itCoords;
91​ for(; itCoords != (lineString->end() - 1); ++itCoords){
92​ if(distanceSphere( currentCoords, *itCoords ) >= m_resolution){
93​ currentCoords = *itCoords;
94​ reducedLine->append(*itCoords);
95​ }
96​ }
97​ reducedLine->append(*itCoords);
98​
99​ qint64 reducedSize = reducedLine->size();
100​ m_count += (prevSize - reducedSize);
101​ return reducedLine;
102​ //qDebug()<<"Nodes reduced "<<(prevSize - reducedSize)<<endl;
103​}
104​
105​qreal NodeReducer::resolutionForLevel(int level) {
106​ switch (level) {
107​ case 0:
108​ return 0.0655360;
109​ break;
110​ case 1:
111​ return 0.0327680;
112​ break;
113​ case 2:
114​ return 0.0163840;
115​ break;
116​ case 3:
117​ return 0.0081920;
118​ break;
119​ case 4:
120​ return 0.0040960;
121​ break;
122​ case 5:
123​ return 0.0020480;
124​ break;
125​ case 6:
126​ return 0.0010240;
127​ break;
128​ case 7:
129​ return 0.0005120;
130​ break;
131​ case 8:
132​ return 0.0002560;
133​ break;
134​ case 9:
135​ return 0.0001280;
136​ break;
137​ case 10:
138​ return 0.0000640;
139​ break;
140​ case 11:
141​ return 0.0000320;
142​ break;
143​ case 12:
144​ return 0.0000160;
145​ break;
146​ case 13:
147​ return 0.0000080;
148​ break;
149​ case 14:
150​ return 0.0000040;
151​ break;
152​ case 15:
153​ return 0.0000020;
154​ break;
155​ case 16:
156​ return 0.0000010;
157​ break;
158​ default:
159​ case 17:
160​ return 0.0000005;
161​ break;
162​ }
163​}
164​No newline at end of file