How do I connect ways to form a polygon?

Help and support
1

Does anyone know the best algorithm for joining the ways returned by OSM into a polygon? I have 330 entities that I retrieve using overpass. These entities are sometimes countries, sometimes states within countries, sometimes just isolated islands. There are all just a list of ways that represent an entity. Some have holes (inner ring).

I wish to programatically rejoin all the ways to form polygons. I don’t wish to use an offline tool. My code is in VB.NET and I am using ESRI ArcGIS Runtime. It correctly converts the ways for 320 of the 330 entities to credible polygons. There are 10 however where I’m not getting the right result. There is one example (Qatar) below. It seems to have lost the land mass, but retained the littoral boundary. This is odd because Qatar is far from the most complex entity I can correctly convert to polygon. The query I use to get Qatar is rel["ISO3166-1"=QA]

I’m on about my 5th experimental version of the algorithm, and I think it might be quicker if I just ask. I have multiple unresolved issues.

  • I see a few end to end joins of ways and start to start joins. I’m not sure what this really means.

  • I don’t know how to handle a situation where 3 ways join.

I expect it’s horrendously difficult, but I prepared to give it a go, I just don’t know a robust algorithm. Can anyone offer a robust algorithm in pseudo code ?

// Pseudo code describing reduction of list of ways to a polygon
INPUT: an overpass QL query OSM for relations/ways
loop until no new connections made
	loop for each way
	 try to connect end of way to beginning of another
	   if fail then try to connect beginning of way to end of another
		  if fail then try to connect beginning of way to beginning of another
			 if fail then try to connect end of way to end of another
	 // if a connection is made, then the two ways are joined into one, and one way is deleted
	end loop
end loop
convert list of ways to polygon
simplify polygon
generalize polygon
OUTPUT: result is (usually) a nicely formed polygon with a handful of rings

image
image944×759 89.8 KB

2

The OSM wiki documents an algorithm for processing OSM multipolygon relations. The relation you’re giving as an example is a type=boundary relation rather than a type=multipolygon relation, but the algorithm should still be useful as boundary relations have the same general structure as multipolygons.

3

Rather than implenting an algorithm yourself, is it perhaps worth looking at calling existing code that already does what you want?

I’d expect that something like osmium should be callable indirectly from vb.net (with caveats - I’ve done similar things with C# code calling native objects**).

Of course, this may be a case of “implementing it yourself is half the fun”, in which case, great - but it might not be the quickest way.

** of C and, er, Cobol :slight_smile:

4

Here is the funciton in the shapely Python library:
https://shapely.readthedocs.io/en/stable/reference/shapely.polygonize.html#shapely.polygonize

Shapely is based on the GEOS library.
https://libgeos.org/

5

I have implemented an algorithm myself. It was fun, but only when I eventually got it working. It’s very simple.

  1. Remove all ways that are a shared way, i.e. they duplicate each other. These are the internal boundaries.
  2. Connect all the remaining ways end-to-end, where they only touch one other way. (They should all be like this)
  3. Close any ways that are still open. These are rare, but I still get a few. Don’t know why.
  4. Load the connected ways into a polylinebuilder, and then create a polygon from the polylinebuilder.

It seems to be working reliably, but that might be luck.