Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Complex multipolygon relation takes forever to compute #278

Closed
lonvia opened this issue Mar 27, 2019 · 3 comments
Closed

Complex multipolygon relation takes forever to compute #278

lonvia opened this issue Mar 27, 2019 · 3 comments

Comments

@lonvia
Copy link
Member

lonvia commented Mar 27, 2019

The rather complex relation 9436485(now deleted) cannot be assembled by the libosmium's multipolygon code. The algorithm seems to be stuck in osmium::area::detail::BasicAssembler::find_candidates(). I gave up after 2 hours.

joto added a commit that referenced this issue Mar 28, 2019
Places where rings touch are unusual for normal multipolygons and the
algorithm in libosmium that assembles multipolygons does not handle
them well. If there are too many touching points it becomes very slow.
This is not a problem for almost all multipolygons. As I am writing
this there are only three relations in the OSM database with more than
100 touching points, all of them rather weird boundaries in the US.

With this commit libosmium will simply ignore those areas to keep the
processing speed within reasonable bounds.

See #278.
@joto
Copy link
Member

joto commented Mar 28, 2019

Places where rings touch are unusual for normal multipolygons and the algorithm in libosmium that assembles multipolygons does not handle them well. If there are too many touching points it becomes very slow. This is not a problem for almost all multipolygons. As I am writing this there are only three relations in the OSM database with more than 100 touching points, all of them rather weird boundaries in the US. The mentioned relation 9436485 had more than 300 of those points.

I have added a commit to libosmium to simply ignore areas with more than 100 touching points to keep the processing speed within reasonable bounds. This is not an ideal solution, of course. It would be better to find an algorithm that handles this case in a better way, but this will not happen quickly.

@joto
Copy link
Member

joto commented Sep 16, 2019

Is in version 2.15.2.

@joto joto closed this as completed Sep 16, 2019
@woodpeck
Copy link

woodpeck commented Apr 21, 2020

For information, another relation that triggered this bug (on systems not yet running the fixed osmium library) was https://www.openstreetmap.org/relation/163124 in its version of 17 April, 2020.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

No branches or pull requests

3 participants