Relation:multipolygon/Algorithm
The following procedure is an attempt at describing a way to process OSM multipolygon relations into proper GIS multipolygons.
Prerequisites
- An OSM relation tagged "type=multipolygon" (or "type=boundary") with at least one way member.
Ring Assignment
The purpose of the ring assignment step is to make a number of closed rings out of all members of the relation. The ordering of members in the relation does not matter.
| Step | Description |
|---|---|
| RA-1 | Collect all ways that are members of the relation. Mark them as "unassigned", and reset the current ring count to 0. |
| RA-2 | Take one unassigned way and mark it assigned to the current ring. |
| RA-3 | If the current ring is closed (first node id == last node id):
|
| RA-4 | If the current ring is not closed:
|
Note: It is possible that in step RA-4 you find more than one candidate way to add to one open end of your current ring. In that case you might have to implement a backtracking algorithm - first try one, and if that doesn't yield a valid multipolygon, then try another.
Ring Grouping
The purpose of the ring grouping step is to find out which rings are nested into which other rings, and build polygons from them.
| Step | Description |
|---|---|
| RG-1 | For ease of access in the following steps, build a matrix of n x n boolean values, where n is the ring id; let mij be true if ring i contains ring j. |
| RG-2 | Reset the polygon counter to 0. |
| RG-3 | Find one unused ring that is not contained by any other ring. Mark it as being the outer ring of the current polygon.
Optionally, check the ways making up this ring and verify that they carry the role "outer". |
| RG-4 | Find all unused rings that are contained by the ring found in RG-3, but not contained by any other unused ring. Mark these rings as being the holes of the current polygon.
Optionally, check the ways making up these rings and verify that they carry the role "inner". |
| RG-5 | Optional
If any of these rings are tagged with anything different from the relation being processed, continue using the ring as a hole, but additionally issue an output polygon for this ring and its tags. |
| RG-6 | Optional
If any or more of the "hole" rings have a common border line (i.e. touching inner rings), combine them to form one hole. Depending on what kind of geometric library you use in step RG-7, this may be a necessary prerequisite to creating valid polygons. |
| RG-7 | Construct a polygon from the outer ring and the holes. Even though all rings are valid, the resulting polygon may be invalid (for example, if a hole touches the outer ring in a way that cuts the polygon in two parts). If the resulting polygon is invalid, ring grouping has failed. |
| RG-7 | If no more unused rings are left, ring grouping has succeeded.
If more rings are left, increment the polygon counter and go to RG-3. |
Note 1: After ring grouping has succeeded, if you have a "holes in holes" situation, the hole in the hole will make up a polygon of its own. If you have 10 concentric rings, then you have 5 polygons, with the odd nummbered rings being outer rings and the even numbered rings being inner rings.
Note 2: After ring grouping has succeeded, you have a number of valid polygons, but this does not say anything about their geographic relationship. You might e.g. have a geometric figure with two interlocking rings, yielding two polygons. This will only fall apart in the next step.
Note 3: You see that this algorithm doesn't actually use the "inner" or "outer" roles. Still it makes sense to use them, because a common error is that people create a relation for a forest area, and add a hole to it, but accidentally add a hole that lies in a completely different forest. Being tagged as "inner", but becoming an "outer" ring in this algorithm, can be used to raise an alarm.
Multipolygon Creation
| Step | Description |
|---|---|
| MC-1 | Check whether there are any intersections between any of the polygons assembled in the ring grouping step. (Do not include the extra polygons from RG-5.)
If there are intersections, multipolygon creation has failed. |
| MC-2 | Construct a multipolygon from all polygons assembled in the ring grouping step. (Do not include the extra polygons from RG-5.) |
That's it, you're done.
Weblinks
- PostGIS functions like ST_MakePolygon or ST_BuildArea can be used to start with.