Differential D2128

Added way concatenating module to osm-simplify
ClosedPublic
Actions

Authored by tandon on Jul 10 2016, 2:42 AM.

Details

Reviewers
nienhueser
rahn
Commits
R34:9c6b3d0e42da: Added way-concatenating module to osm-simplify.
Summary

To address the problem of discontinuous streets/roads which appear on level 11-12, this module was added.
One of the primary reasons for this discontinuity, as told by @rahn , is that Marble omits rendering objects which are too small to be drawn. Hence if a street is composed of lots of OSM way chunks which are smaller than 2 pixels, those chunks don't get rendered and hence the street appears as discontinuous.
To address this problem, all these OSM way chunks need to be concatenated so that the streets are rendered faster and fully.

The given WayConcatenator, concatenates the OSM ways on the basis of end-points and name.
Although the above method resulted in the concatenation of many ways, visually this way of concatenating did not prove to be fruitful as still almost all the previously discontinuous streets still appeared discontinuous.

As previously discussed with @rahn , the way forward will now be to concatenate ways based on a fuzzy-compare and not just end-points. To accomplish this I will have to move from a Hash based approach to a tiling-map based approach.

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 updated this revision to Diff 5054.Jul 10 2016, 2:42 AM
tandon retitled this revision from to Added way concatenating module to osm-simplify.
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, rahn.
tandon added a comment.Jul 10 2016, 2:57 AM

Usage
./osm-simplify -t highway=primary,highway=motorway,highway=trunk,highway=secondary,highway=tertiary,highway=residential -w karl.osm
or
./osm-simplify -t highway=* -w karl.osm

Level 11 Karlsruhe region after way concatenation

Level 11 tiles for the above region after performing way concatenation

11.tar.gz232 KBDownload

nienhueser edited edge metadata.EditedJul 10 2016, 5:54 AM

Wait, I think a fuzzy compare is wrong. The problem of gaps is likely caused by streets that change their level (e.g from primary to secondary) when in some zoom level we only render primary streets. Let us first look into some example data closer to see the reason for the gaps.

Update: From the code it seems an equal street name is required to merge ways. I think this is not enough, we need additional considerations. Here are some problems that come to my mind:

  • streets can change their name at some point
  • streets change their level (primary => secondary, or interrupted by some network link)
  • streets use ref instead of name
  • streets mix usage of ref and name

I do think however that relying on the node id (not coordinate!) to be the same in ways to merge is safe. Going for fuzzy comparisons seems wrong to me both from the pov of creating correct results and having a not too complicated solution.

nienhueser added inline comments.Jul 10 2016, 6:19 AM
tools/osm-simplify/WayConcatenator.cpp
78

I think it would be better (more accurate and faster) to put node IDs into the hash map and compare those instead of coordinates.

128

Street names often change in between.

nienhueser added inline comments.Jul 10 2016, 7:27 AM
tools/osm-simplify/WayChunk.cpp
29

Some streets are not tagged with a name, but instead using ref. See e.g. https://www.openstreetmap.org/edit#map=17/48.92478/8.27570 which corresponds to the highway rendered in orange near Durmersheim.

nienhueser added inline comments.Jul 10 2016, 7:38 AM
tools/osm-simplify/WayChunk.cpp
111

This seems pretty inefficient. The standard approach for reversing strings works in place by swapping all elements from start/end towards the middle.

I'd go for adding a reverse() method to GeoDataLineString which internally calls std::reverse on d->m_vector like shown in http://stackoverflow.com/a/1340291/1802551 and also clears/adjusts the other private members.

tools/osm-simplify/WayConcatenator.cpp
37

This method seems too long. Usually code is a lot easier to read and maintain when splitting long methods into several smaller ones.

nienhueser added inline comments.Jul 10 2016, 7:55 AM
tools/osm-simplify/TagsFilter.cpp
40

andFlag = flag seems simpler here.

tools/osm-simplify/WayConcatenator.cpp
40

Please move all these variables into the scope of the loops/if clauses where they are actually used. There is no performance drawback or anything with that approach, even not when having variables in multiple scopes. At the same time code readability improves a lot.

167

Memory leak here.

tandon added a comment.Jul 12 2016, 12:19 AM
In D2128#39268, @tandon wrote:

Usage
./osm-simplify -t highway=primary,highway=motorway,highway=trunk,highway=secondary,highway=tertiary,highway=residential -w karl.osm
or
./osm-simplify -t highway=* -w karl.osm

Level 11 Karlsruhe region after way concatenation

Level 11 tiles for the above region after performing way concatenation

11.tar.gz232 KBDownload

The above given screenshot is wrong and is actually of the default tiles. I made this mistake since while checking the concatenator I was not deleting the cache resulting in default tiles and not the tiles generated via WayConcatenator.

Also, the WayConcatenator of the diff 5054 skips few of the OSM ways resulting in an incomplete output.

tandon added a comment.Jul 12 2016, 12:58 AM

I corrected the WayConcatenator (of diff 5054) so that it does not skip any OSM ways while writing the output. I had forgot to update the hash-table in one of the conditions which caused the above bug.
I tried the corrected code on a small highway stretch. However the output was wrong and still some of the ways were missing.

Original highway

Highway produced by tiles constructed via WayConcatenator

On closer inspection I found that this wrong behavior was due to the way in which osmconvert was cutting tiles and not due to WayConcatenator. If I directly loaded the OSM file produced by WayConcatenator the highway appeared correctly however on loading tiles of the above output, highway appeared incomplete.

Actually the bounded-regions/tiles produced by osmconvert did not include the OSM node data for many of the nodes specified in OSM ways of the given highway resulting in incomplete/broken OSM tiles.

On creating the tiles, it used to give wrong-sequence errors
osmconvert Warning: wrong sequence at node 2118357061
osmconvert Warning: next object is node 1589377417

Now I guess that this is most probably due to the way in which OSM files are written in Marble.
How do I rectify this error?

Original OSM file
https://paste.kde.org/p1bu7gpi9/6cnpci (Password: kde)

motorway_karly.osm64 KBDownload

File reduced using WayConcatenator
https://paste.kde.org/pnujrh754/iuylfs (Password: kde)

s_motorway_karly.osm16 KBDownload

tandon updated this revision to Diff 5222.EditedJul 16 2016, 1:40 AM
tandon edited edge metadata.
tandon marked 7 inline comments as done.

Compared to last time, results were quite according to expectations. All the streets, which were previously rendered as broken now appear continuous. Also there were good savings in terms of file size.( I have presented a few memory related statistics in the next comment)

Fixes Done

  • Using OSM node ID's instead of lon-lat coordinates as key values for the multi-hash-map
  • Added multi-hash-map to handle intersections, hence now corresponding to a node-id there can be 2 or more WayChunks
  • Using visual categories for concatenating/(differentiating among WayChunks)
  • Added reverse() method in GeoDataLineString
  • Refactored code to more modular units.
  • All the variable definitions are now near to where they are used.
  • Fix bugs related to improper reversal of WayChunks, concatenation of WayChunks having the same first and last IDs, proper insertion/deletion of key-value pairs in multi-hash-map during the execution of the tool.

Fixes Left

  • Proper memory management.
  • Performing timing related tests.
  • Running the output file through the tile creation tool chain.

Doubts
There is a case in which a Way under consideration is inserted between 2 way chunks.
Example: Suppose Way under consideration is <4,5> and there exists WayChunks <1,2,3,4>; <5,6,7> then the program will construct a WayChunk <1,2,3,4,5,6,7>
Now consider the following scenario:
Way under consideration is <1,8,9,10,7> and there exists a WayChunk <1,2,3,4,5,6,7> then the program generates nonsensical WayChunks. For now I am detecting such scenarios and directly adding the way under consideration to the output file hence removing this way from any future considerations.
However due to this abrupt removal of such wayswe are getting a small variance in the final number of ways reduced ,every time we run the program on the same input file. Though this variance is not affecting rendering , this thing does result in a smaller total number of ways reduced.

tandon added a comment.Jul 16 2016, 2:02 AM

Statistics

  • Before concatenation(original OSM file)
    • Size: 4.7Mb
    • Placemark count: 3485
  • After concatenation(way concatenated OSM file)
    • Size: 2.9Mb
    • Placemark count: 812
    • (2704 OSM Ways were reduced to 407 OSM Ways)
  • After node reducing the way concatenated file(way concatenated + node reduced OSM file)
    • Size:2.5Mb
    • Total nodes reduced: 15146
nienhueser added a comment.Jul 16 2016, 6:34 AM

Thanks for the update. Sounds great!

The patch has grown rather large now and I'd like to get it into master soon to avoid merge conflicts and similar problems. However I'm running into some code style nitpicks that make reading the code a bit hard. Can you please go over it and ensure the following (some also mentioned in inline comments):

  • use nullptr instead of NULL (reason: type safety)
  • initialize variables where they are first used, not before. Do not move them out of loops/if clauses if they are only used inside (reason: code readability, refactoring safety)
  • avoid larger blocks of commented code
  • do not use abbreviations in variable or method names (reason: code readability, see also https://community.kde.org/Policies/Kdelibs_Coding_Style#Variable_declaration ). Use QtCreator's rename command (Ctrl+Shift+R) to change this painlessly.
  • do not omit curly braces for one-liners (reason: refactoring safety, see also https://community.kde.org/Policies/Kdelibs_Coding_Style#Braces )
  • prefer prefix increment to postfix increment (e.g. use ++iter instead of iter++, reason: describes intent better and is faster for user defined types)
  • Use Q_ASSERT(...) instead of qDebug() with error messages if you consider something not to be possible (reason: don't rely on the user to detect errors in shell output)
src/lib/marble/geodata/data/GeoDataLineString.cpp
527

We also need

delete d->m_rangeCorrected;
d->m_rangeCorrected = 0;
d->m_dirtyRange = true;

Or could we reverse d->m_rangeCorrected as well if it is not a nullptr? @rahn ?

tools/osm-simplify/BaseFilter.h
31

No abbreviations please, so objectsBegin() and objectsEnd().

tools/osm-simplify/TagsFilter.cpp
27

temp shouldn't be part of a variable name. Please also move to the scope where it is used. Same below.

tools/osm-simplify/TagsFilter.h
31

Objs => Objects like above

tools/osm-simplify/WayChunk.cpp
58

Would this implementation work as well?

m_wayList << chunk->m_wayList;
m_last = last;

Sparing the last parameter seems reasoanble also, i.e. just do

void WayChunk::append(WayChunk* chunk)
{
  m_wayList << chunk->m_wayList;
  m_last = chunk->last();
}
66

Is this method used anywhere?

79

nullptr

102

Please move into the loop, same below. Same for a couple more places in the code.

109

Please replace with

qSwap(m_first, m_last);
142

Should return just int, no? QList cannot hold more.

tools/osm-simplify/WayConcatenator.cpp
41

No abbreviations, please, use speaking variable names.

42

No abbreviations.

tandon updated this revision to Diff 5248.Jul 17 2016, 11:23 PM
tandon marked 12 inline comments as done.

Changed the code style based on above recommendations.

tools/osm-simplify/WayChunk.cpp
66

I anticipated that I might need such a method in the future but eventually it was not required, hence I have removed it for now.

nienhueser added inline comments.Jul 18 2016, 6:54 PM
tools/osm-simplify/WayChunk.cpp
71

I think a

Q_ASSERT(!m_wayList.isEmpty());

is fine also because you pass a placemark in the ctor that ends up in m_wayList. id() below also assumes that m_wayList cannot be empty.

78

Here you return a placemark from m_wayList, while below you'd return a newly created. Doesn't that result in an unsolvable (or annoying to solve) memory management problem which results in either memory leaks or double deletions?

132

should be const

tools/osm-simplify/WayConcatenator.cpp
179

Seems like a memory leak to me.

tools/osm-simplify/main.cpp
417

I'd avoid pointer management here:

WayConcatenator concatenator(map, tagsList, parser.isSet("tags-and"));
concatenator.process();
tandon updated this revision to Diff 5289.Jul 19 2016, 3:21 AM
tandon marked 6 inline comments as done.

Fixed memory issues and leakages.

tools/osm-simplify/WayChunk.cpp
78

I have rectified this issue by always creating a new placemark object.
Also, I googled a bit and found that the correct way of returning a new object from a member function is to return via a smart pointer (ex QSharedPointer), however , as of now, this method is called from only one place and also since using a shared pointer gives a very little performance hit, I decided on using only a regular pointer.

nienhueser accepted this revision.Jul 19 2016, 5:54 AM
nienhueser edited edge metadata.

Looks good :-)

This revision is now accepted and ready to land.Jul 19 2016, 5:54 AM
Closed by commit R34:9c6b3d0e42da: Added way-concatenating module to osm-simplify. (authored by tandon). · Explain WhyJul 19 2016, 2:37 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 5313

View Options

src/lib/marble/geodata/data/GeoDataLineString.h

Loading...
View Options

src/lib/marble/geodata/data/GeoDataLineString.cpp

Loading...
View Options

tools/osm-simplify/BaseFilter.h

Loading...
View Options

tools/osm-simplify/BaseFilter.cpp

Loading...
View Options

tools/osm-simplify/CMakeLists.txt

Loading...
View Options

tools/osm-simplify/TagsFilter.h

Loading...
View Options

tools/osm-simplify/TagsFilter.cpp

Loading...
View Options

tools/osm-simplify/WayChunk.h

Loading...
View Options

tools/osm-simplify/WayChunk.cpp

Loading...
View Options

tools/osm-simplify/WayConcatenator.h

Loading...
View Options

tools/osm-simplify/WayConcatenator.cpp

Loading...
View Options

tools/osm-simplify/main.cpp

Loading...