CODEWITHSUNDEEP
oopgraphgpsdijkstra
Jon
Jon

Reputation: 678

GPS finding neighboring roads

So I'm building a GPS application. I have a collection of Road objects each containing a start and end point (plus other in-between points where the road curves). I've implemented dijkstra's algorithm for finding the shortest path (where roads are nodes in the graph) but before I can run it I need to determine which roads neighbor (connect to) one another so to create edges.

The easy(?) way would be to iterate through each road and in a nested loop see if any other roads too start/end at the same point. But this seems inefficient being O(N^2). One idea was to pre segregate roads into regions (i.e. in the UK there'd be NW, NE, E, SE, SW etc...) then only look for neighbors in the same region reducing the search space.

Looking for advice from more experience programmers, how would you tackle the problem?

This is not a homework, having recently graduated I am working on this as a pet project to gain some practical experience and pad out the CV a bit.

Edit: I should add roads only ever connect at start/end points

Upvotes: 2

Views: 159

Answers (1)

mitchus
mitchus

Reputation: 4877

You could sort all the (x,y) points you have, by x first and then by y. For n points this should be O(nlogn) or even linear if you use radix sort. Then you just need to go through the list; whenever two adjacent entries are equal, their corresponding roads intersect.

Upvotes: 1

Related Questions