Find nearest edge in graph

Question

I want to find the nearest edge in a graph. Consider the following example:

Figure 1: yellow: vertices, black: edges, blue: query-point

General Information: The graph contains about 10million vertices and about 15million edges. Every vertex has coordinates. Edges are defined by the two adjacent vertices.

Simplest solution: I could simply calculate the distance from the query-point to every other edge in the graph, but that would be horribly slow.

Idea and difficulties: My idea was to use some spatial index to accelerate the query. I already implemented a kd-tree to find the nearest vertex. But as Figure 1 shows the edges incident to the nearest vertex are not necessarily the nearest to the query-point. I would get the edge 3-4 instead of the nearer edge 7-8.

Question: Is there an algorithm to find the nearest edge in a graph?

Answer 1

A very simple solution (but maybe not the one with lowest complexity) would be to use a quad tree for all your edges based on their bounding box. Then you simply extract the set of edges closest to your query point and iterate over them to find the closest edge.

The extracted set of edges returned by the quad tree should be many factors smaller than your original 15 million edges and therefore a lot less expensive to iterate through.

A quad tree is a simpler data structure than the R-tree. It is fairly common and should be readily available in many environments. For example, in Java the JTS Topology Suite has a structure QuadTree that can easily be wrapped to perform this task.