How to identify admin relations that border each other

Hi, I want to know how I can programatically identify which relations representing administrative areas border each other. For example, France borders Spain, Belgium, switzerland etc. Or similarly for different admin levels.
I am writing a desktop mapping application which is audio only for the visually impaired and I want to be able to provide the user with information about what areas border the current area they are in.

The algorithm I have worked out seems ridiculously complicated and I would like to know if I am missing a trick and there is actually quite an easy way.
My algorithm goes something like this:

  • Load all the boundary=administrative for an area e.g. ISO3166-1:GB.
  • Take the first relation and read down the list of member ways.
  • For every member way, ask every other relation if it also uses this way. Mark the two relations as potential neighbours.

There is then a second part once those steps are done to guard against one relation being inside another relation rather than bordering it.

  • For each relation, loop through all the candidate border relations.
  • Check that none of the polygons described by the two relations completely enclose any of the other polygons.
  • If they do not then they border each other.

When I am finished I will be able to do the following:

  • Track the current relation my user has navigated to
  • Read the list of relations stored against the current relation representing neighbors.
  • Announce the list of bordering admin relations, of all levels, to the user.

I have written about three quarters of the code to do this and it is going okay but am I missing a trick and there is a much simpler way?
Any thoughts most welcome,

On which platform are you writing your application? If you’re using Java (or another JVM language), you could store your OSM data as a compact Geographic Object Library, and then perform a touches query using the GeoDesk library:

for(Relation area : world.relations("a[boundary=administrative][admin_level=2]")
    String areaName = area.stringValue("name");
    // print/announce the name

touches() selects all admin areas that share a boundary with this_area, but only those located outside of it.

If you actually don’t have an abstraction that lets you look up the relations memberships of a way (having a geometry library could save you much time), you should mark the ways yourself first, (m each for n relations, m*n), reducing the cost to m*n for your loop later (or just update neighbours while marking), instead of your current m*n*n which is slow when the number of relations get big.

But you are already doing the most important part, storing the neighbours for later, so the processing is only done once.

Does your current approach catch glued boundary polygons too, not just relations?

Hi. I don’t currently tell all my ways which relations use them but I can see that might help. Thanks.

And what is a glued boundary polygon? At the moment I stitch all the ways in a relation together into one or more polygons.

To address the other reply. I’m writing this on Windows in C++ so can’t take advantage of the library quoted.

But the big takeaway for me is that it sounds like I am doing the right thing and there isn’t a shortcut I am missing.

If you’re only interested in administrative boundaries, you can generally depend on the fact that a subarea would have a numerically higher admin_level=* tag, so you don’t need to comprehensively analyze candidate relations’ geometries.

Algorithmically, you’re on the right track. However, if you’re asking if there’s a way to avoid having to write this functionality in the first place, then yes, there are some alternatives. OSM data is commonly loaded into a PostGIS database. If you load the boundaries as multipolygons, then PostGIS functions like ST_Touches or ST_Overlaps would tell you the answer directly. @GeoDeskTeam’s answer is another option along these lines.

If you’re open to an off-the-shelf service, the Overpass API lets you walk the relation hierarchy. This query implements part of your algorithm, taking advantage of an admin_level=* filter. I think it should be possible to also filter out anything contained inside the original boundary, regardless of admin_level=*, but I didn’t get very far.

QLever has already indexed every feature by the features that contain or intersect with it or vice versa, so you can query for countries that border France. You can remove some of the statements to see even more granular results, like parks or land use areas that abut the French boundary.

Thanks. I think I do need to check the geometry of the polygons to test if one is inside another as the alternative is they border each other and the admin level value isn’t going to tell me this.

Setting up a PostGIS database is a massive learning curve for me at the moment so I’ll keep that one filed under “look at when I really get stuck”. It sounds very powerful though.

QLever also looks interesting. I am a little familiar with sparql as I’ve queried Wikidata a bit. I’ll take a look. And interested that one of the examples is “Get roads in the Alps” because OSM doesn’t define something as nebulous as the boundary of the Alps.