I'm trying to extract a Road Network from a large set of GPS point data gathered from vehicles.

I plan on representing the final network in terms of a NetworkX graph of G(V,E)

I have implemented step 1 which is to extract a list of "Trajectories" from the data (grouping the data into short logical trips) and these trajectories can be pretty nicely plotted, but obviously many of them overlap. A graph must be constructed where the overlaps collapse to form final paths.

Building the final network graph will be done in a incremental approach, starting with a completely empty graph as follows:

For each trip in trajectories: for each point in trip: find the (spatially) closest graph node to the given point if distance(closest_node, candidate_node) < node_threshold: merge_nodes(closest_node, candidate_node)

Obviously I need a fast indexed way to do spatial queries on the graph if this is going to be feasible.

Ideally I planned on storing custom Python objects at each node. The objects would be as follows:

class GeoPoint(object): def __init__(self, lat, lon): self.latitude = lat self.longitude = lon

and I was planning on adding nodes in the form:

graph.add_node(generate_uuid(), data=geo_point)

Im struggling to find much examples on doing this type of thing. Is there a built in way to efficiently query the NetworkX graph for nodes spatially close to some candidate node?

Or would a better approach be to keep an additional queryable structure to find node references that are spatially close to the candidate node and then use that reference to operate on the graph?

  • I often use concatenation of xy(rounded) as node id. No need to search for overlap. – FelixIP Aug 21 '18 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.