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

Question

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...

Answer 1

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:
        road_junctions.extend(get_intersection(line, iline))

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
SELECT roads.id FROM road_lines roads WHERE ST_Intersects(roads.the_geom, my_geom)
SELECT ST_Intersection(roads.the_geom, my_geom) FROM road_lines roads WHERE roads.id = my_id

Answer 2

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.

Answer 3

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.)

Answer 4

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

Answer 5

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

Answer 6

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.