# What's an efficient way of detecting road junctions on a map?

I may receive maps from any source for my project, and for the C++ algorithm I'm making, it's imperative for the algorithm to know where road junctions (nodes where more than two road segments meet) are. Besides, in many of the maps I get, there are roads overshooting and undershooting (ie: roads aren't properly connected). One way to correct the problem is by 'cleaning' the road network using Autocad. The questions I have are:

1. Is there an efficient way (any software which can do it?) to get my map in a GML format, which contains information about road junctions in the map? (maybe have a GML tag which says that a particular node is a junction)
2. Is there any other way to 'clean' the road network?

Colleagues have suggested FME, but that involves writing scripts and we're not sure about whether the script would be flexible enough to cater to all maps. The only other way to detect junctions is to use brute force and find which road segments have common nodes. Would ArcGIS help? (haven't used it, but have heard of it) I'm sure there should be a better way...

-
Does it need to find self intersecting roads? How should it handle degenerate geometries (polylines where all vertices coincide thus having zero length). How should it handle coinciding lines where the intersection is a linear segment and not just a point? – Kirk Kuykendall Dec 8 '10 at 16:36
@Kirk: I'm a bit shocked at the situations you've mentioned. I'm new to GIS, and didn't even know that such possibilities existed. 1.Self intersection requires multiple segments. Unless it's a flyover, I would consider those intersections as junctions. 2. I'm not even able to visualize what degenerate geometry is, so I don't know what to answer. 3.Coinciding lines should be treated as two separate roads because that's how I assume they would be in real life too. – Nav Dec 9 '10 at 4:56

If you have the roads in a spatial form, such as a Shapefile, you can load them into PostGIS and have it automatically find those using an SQL query. I've done this before - the SQL statement is designed to find for each road those that intersect geographically and create a nodal point for each crossing.

I will try to clean this up later, but here is the basic flow you can take...

``````for line in road_layer_lines:
ilines = get_intersecting_objects(line)
for iline in ilines:
``````

The ST_* functions are what makes this work within PostGIS

• ST_Envelope: Grabs the bounding box of a given geometry - this is used to speed up the algorithm. One can narrow down a geographical search with the bounding boxes in a quick-but-less-accurate pass and then scan the results with the actual geometries.
• ST_Intersects: Determines if two geometries intersect
• ST_Intersection: Returns the intersection of two geometries

The following are only snippets since I don't have time to finish, perhaps someone can edit it before I get back here...

``````SELECT id, the_geom FROM road_lines
``````
-
Just sharing: Another database I've come across is this - <oracle.com/technetwork/database/berkeleydb/overview/…;. Apparently the queries are very fast because the queries are available as libraries which can be embedded in the application. – Nav Dec 10 '10 at 10:20
@dmsnell- Maybe you could provide an example of the type of SQL query used to accomplish this task? – RyanDalton Nov 29 '11 at 22:16

You can analyze polylines in amazing ways by using buffers. This is usually inefficient--buffers create many additional vertices--but (a) it is a technique available in many GISes (vector or raster based) and (b) it sometimes can produce information that is otherwise hard to get.

In this case, buffering the road by a small amount and then buffering by the negative of the same amount leaves little "islands" around all bends and around all intersections. This is easy to prove geometrically.

Here is an example of a 10 m polyline buffer (gray) and its -10 m buffer (light red) in a map that is 650 m wide:

Now intersect the original polyline layer with these island polygons, merge the segments by island identifier, and count the pieces:

The light yellow segments designate the high-count pieces and the dark cyan segments designate the low-count ones. In this fashion we have (a) found all bends and intersections (including self-intersections) and near junctions (see the extreme left, where the two segments do not quite meet)) and (b) differentiated the bends from the intersections. We can find the almost-junctions by selecting the islands that contain two or more connected segments: the bends contain only connected segments.

Due to the symmetry of buffering, the centroids of the intersection islands are the points of intersection.

One beautiful aspect of this style of analysis is that it does not care how the underlying polyline is represented: it could be a single feature, it could be one feature for each line segment, or anything in between.

-

Yes, you could do this with FME for sure. There are many "transformers" that handle cleanup, intersections, and topology; I would try the TopologyBuilder transformer in this case.

Any scripting is all done in a graphic environment, so it is very simple to do.

You can always get a trial version from www.safe.com

(Disclosure: Mark Ireland, aka FME Evangelist, Safe Software Inc.)

-
I second this. FME is great for this particular problem, both the transformation from AutoCAD to GML and the topological cleanup. It can be astoundingly universal in its application. – blord-castillo Nov 30 '11 at 16:47

The GRASS GIS has very efficient tools for cleaning polygons the way you want, take a look at: http://grass.fbk.eu/grass62/manuals/html62_user/v.clean.html

-

Arcgis network analyst, which you can get with a free trial, does this in less than 10 seconds and with just a few clicks.

-

We're looking for long answers that provide some explanation and context. Don't just give a one-line answer; explain why your answer is right, ideally with citations. Answers that don't include explanations may be removed.

The process can be done in ArcGIS with network analyst.

There is also another way in ArcGIS: you can go through the folliwing steps: "Arctoolbox" → "Data management tools" → "features" → "feature vertices to points" and there you can do what you need.

-