Find nearest edge in graph

20
votes

I want to find the nearest edge in a graph. Consider the following example: yellow: vertices, black: edges, blue: query-point

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?

5
algorithmgeometrycomputational-geometrygraph-algorithm
I assume all your edges are straight lines? – amit
Yes, they are straight. – user2033412
... vertex has coordinates ..., like cartesian coordinates lat/long on a square grid? or some other domain specific coordinate system? polar coordinates? – inquisitive
Latitude/Longitude coordinates. The Graph is a country-sized road-network. Edges are probably shorter than 1000 meters. – user2033412
Hey, did you figure out how to solve this problem? – SLearner

5 Answers

4
votes

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.

3
votes

There are spatial query structures which are appropriate for other types of data than points. The most general is the "R-tree" structure (and its many, many variants), which will allow you to store the bounding rectangles of your line segments. You can then search outward from your query points, examining the segments in the bounding rectangles and stopping when the nearest remaining rectangle is further than the closest line encountered so far. This could have poor performance when there are many long line segments overlapping, but for a PSLG such as you seem to have here, that shouldn't happen.

Another option is to use the segments to define a BSP tree, and scan outwards from your point to find all the "visible" lines. This in turn will be problematic if your point can see many edges.

1
votes

Without proof:
You start with a constrained Delaunay Triangulation, that is a triangulation that takes the existing edges into account. E.g. CGAL or Triangle can do this. For each query point you determine which triangle it belongs to. Then you you only have to check the edges touching a corner of that triangle.
I think this should work in most cases, but there are certainly corner cases where it fails, e.g. when there are many vertices without any edge at all, so at least you have to remove those empty vertices.

1
votes

You can compute the voronoi diagram and run a query on each voronoi cell. You can subdivide the voronoi diagram to get a better result. You can combine metric and voronoi diagram:http://www.cc.gatech.edu/~phlosoft/voronoi/

1
votes

you could insert extra vertices in long edges to get some approximation based on closest vertices ..