This is a static archive of our old OpenStreetMap Help Site. Please post any new questions and answers at community.osm.org.

Is there any correlation between ways in OpenStreetMaps?

0

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's gravatar image

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

edited 22 Apr '13, 10:27

One Answer:

2

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.

answered 22 Apr '13, 10:35

Frederik%20Ramm's gravatar image

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

Source code available on GitHub .