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
304510
accept rate: 0%

edited 22 Apr '13, 10:27


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

Frederik Ramm ♦
70.9k826431106
accept rate: 24%

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
Your answer
toggle preview

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

Question tags:

×270
×139
×44
×43

question asked: 22 Apr '13, 10:01

question was seen: 1,733 times

last updated: 22 Apr '13, 11:18

powered by OSQA