Is there any correlation between ways in OpenStreetMaps?

Hello All,

Currently I am working on finding all the intersecting nodes present in a region of OpenSteetMap. I wrote a program in python, which is working fine for small areas. But if I run the same program for the whole Niedersachsen, it takes many days to complete. My code is comparing each way with all other ways present in the map, to find intersecting nodes. This method is not efficient for very large data. I can optimize my code if somehow I just restrict the comparison of ways to small region only, not for the whole region. May be there is some correlation between way ids, which I need to know. Or maybe I somehow identify the smallest possible region, which may include all the correlated ways. Please advise.

asked 22 Apr '13, 10:01

tfarooqi
30●4●5●10
accept rate: 0%

edited 22 Apr '13, 10:27

One Answer:

active answers oldest answers newest answers popular answers

There is no correlation between node IDs and area.

Assuming that you really want to find intersecting nodes (as opposed to non-noded intersections), use the following algorithm:

Use a hash table to store "link counters"
Process all ways; each time a node is referenced by a way, increase the node's link counter in your hash table by one
when finished, look at your hash table - all node IDs with a link counter greater than one are junction or intersection nodes.
If you only want to find nodes where ways cross (and not those where one way ends on a node belonging to another way) then modify step 2 and only look at all inner nodes of the way (ignoring the end nodes).

Another option for solving your problem is computing a bounding box for every way (i.e. the minimum and maximum latitude and longitude), and then restrict comparison to ways whose bounding boxes intersect.

permanent link

answered 22 Apr '13, 10:35

Frederik Ramm ♦
82.5k●92●720●1273
accept rate: 23%

I was thinking on the same direction of creating a hash table.But I thought there must be a better way. Using the bounding box to restrict the way comparison is also a good idea but I think finding the intersection of bounding box will lead to the same issue which I am currently facing

(22 Apr '13, 11:06) tfarooqi

But I thank you Mr. Ramm for your valueable comments.

(22 Apr '13, 11:18) tfarooqi

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

*italic* or _italic_
**bold** or __bold__
link:[text](http://url.com/ "title")
image?![alt text](/path/img.jpg "title")
numbered list: 1. Foo 2. Bar
to add a line break simply add two spaces to where you would like the new line to be.
basic HTML tags are also supported

learn more about Markdown

Question tags:

openstreetmap ×362
ways ×167
python ×78
intersection ×49

question asked: 22 Apr '13, 10:01

question was seen: 3,058 times

last updated: 22 Apr '13, 11:18

Is there any correlation between ways in OpenStreetMaps?

Follow this question

Related questions