JA:Relation:multipolygon/Algorithm
この記事は OSM のマルチポリゴンタイプのリレーションを GIS のマルチポリゴンとして適切に処理する方法の記述です。 The following procedure is an attempt at describing a way to process OSM multipolygon relations into proper GIS multipolygons.
前提条件
- タグ "type=multipolygon" (or "type=boundary") を持つOSMリレーションで、1つ以上の way メンバーを持っている。
リングの割り当て（RA）
リング割り当てステップの目的は、リレーションのすべてのメンバーのうち閉じたリングを作ることです。リレーションのメンバーの順序は目的ではありません。
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 | リレーションのメンバーであるすべてのウェイを集めます。各ウェイを "unassigned "としてマークし、現在のリングカウントを0にリセットします。 |
| RA-2 | 割り当てられていないウェイを1つ選び、現在のリングに割り当てられていることをマークします。 |
| RA-3 | 選択しているリングが閉じている場合(first node id == last node id):
|
| RA-4 | 選択しているリングが閉じていない場合:
|
注意: ステップ RA-4 で、現在のリングのオープンエンドに追加する方法が複数見つかる可能性があります。その場合、バックトラックアルゴリズムを実装しなければならないかもしれません。 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.
リングのグルーピング（RG）
リンググルーピングのステップの目的は、どのリングが他のリングのどのリングに入れ子になっているかを見つけ出し、そこからポリゴンを作成することです。 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 | 次のステップでアクセスしやすいように、n x n のブール値の行列 m を作成します。n はリング ID です。リング "i" がリング "j" を含む場合 mij は true となります。 |
| RG-2 | ポリゴンカウンターを 0 にリセットします。 |
| RG-3 | 他のリングに含まれていない未使用のリングを1つ見つけてください。それを現在のポリゴンの外側のリングとしてマークしてください。
Optionally, check the ways making up this ring and verify that they carry the role "outer". |
| RG-4 | RG-3 で見つかったリングには含まれているが、他の未使用のリングには含まれていない未使用のリングをすべて見つけてください。これらのリングを現在のポリゴンの穴としてマークしてください。
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 | 外側のリングと穴から多角形を作成します。すべてのリングが有効であっても、結果のポリゴンが無効な場合があります (例えば、穴が外側のリングに触れてポリゴンを2つに分割した場合など)。結果として得られるポリゴンが無効な場合、リングのグルーピングは"失敗"したことになります。 |
| RG-7 | 使用されていないリングがなくなると、リングのグルーピングは"成功"したことになります。
リングが残っている場合は、ポリゴンカウンタをインクリメントして 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.
マルチポリゴンの作成（MC）
| Step | Description |
|---|---|
| MC-1 | リングのグルーピングステップで組み立てたポリゴン同士の交点があるかどうかを確認してください。RG-5からの余分なポリゴンは含まないでください。
交差がある場合は、マルチポリゴンの作成に失敗したことになります。 |
| MC-2 | リングのグルーピングステップで組み立てたすべてのポリゴンからマルチポリゴンを作成します。RG-5からの余分なポリゴンは含まないでください。 |
完了です。
Weblinks
- PostGIS functions like ST_MakePolygon or ST_BuildArea can be used to start with.