RU:Relation:multipolygon/Algorithm
Нижеприведённая процедура является попыткой описать способ преобразования мультиполигональных отношений OSM в правильные ГИС-мультиполигоны.
Определения
- Отношение (relation) OSM с хотя бы одним членом, имеющее в тегах type=multipolygon" (или "type=boundary").
Распределение замкнутых контуров
Целью данного шага является создание ряда замкнутых контуров из всех членов отношения. Порядок следования этих членов не имеет значения.
| Шаг | Описание |
|---|---|
| RA-1 | Собрать все линии (ways), входящие в отношение. Пометить их как «нераспределённые» (assigned[i]=false) и обнулить счётчик замкнутых контуров (n=0). |
| RA-2 | Взять одну из нераспределённых линий и пометить её как распределённую (assigned[i]=true) на текущий замкнутый контур. |
| RA-3 | Если текущий контур замкнут (идентификаторы первой и последней точки совпадают), то:
|
| RA-4 | Если текущий контур незамкнут:
|
Примечание. Есть вероятность, что на шаге RA-4 будет найдено несколько вариантов линий для добавления к конечной точке текущего незамкнутого контура. В этом случае можно попробовать использовать алгоритм поиска с возвратом, т.е сперва попытаться построить замкнутый контур с одной линией, а в случае неудачи, с другими вариантами.
Группировка замкнутых контуров
Определение вложенности контуров и построение мультиполигонов.
| Шаг | Описание |
|---|---|
| RG-1 | Для упрощения выполнения следующих шагов алгоритма построить двумерный массив m[1..n,1..n] типа boolean, где n – число контуров, а m[i,j]=true, если контур i содержит в себе контур j. |
| RG-2 | Установить счётчик полигонов p= 0. |
| RG-3 | Найти один незадействованный контур, который не содержится в любых других контурах. Пометить его как внешний (outer) контур текущего полигона (или пометить как внешние все линии этого контура). |
| RG-4 | Найти все неиспользованные контуры, содержащиеся в найденном на предыдущем шаге, но не содержащиеся в других незадействованных контурах. Пометить их как внутренние контуры (дырки) текущего полигона (или пометить все линии этих контуров как внутренние). |
| RG-5 | (опционально). Если какой-либо из внутренних контуров имеет тэги, отличные от тега отношения, продолжать использовать этот контур как внутренний, но дополнительно использовать его как самостоятельный полигон со своими тегами. |
| RG-6 | (опционально). Если несколько внутренних контуров имеют совпадающие линии (т.е. соприкасаются), предлагается сделать из них единый внутренний контур. В зависимости от того, какой тип геометрической библиотеки используется на шаге RG-7, это может стать обязательным условием для создания правильных полигонов. |
| RG-7 | Построить полигон из внешнего и внутренних контуров (дырок). Даже если все контуры правильные, получившийся полигон может быть неправильным (например, если внутренний контур так касается внешнего контура, что разбивает его на две части). Если получившийся полигон неправильный, группировка контуров считается неудачной. |
| RG-8 | Если больше не осталось незадействованных контуров, группировка считается удачной, иначе увеличить счётчик полигонов (p++) и перейти к шагу RG-3. |
Примечание 1. Если после успешной группировки контуров вы получили вложенные внутренние контуры, то внутренние контуры, находящиеся внутри другого внутреннего контура, могут образовывать самостоятельные полигоны. Если, например, имеется 10 концентрических замкнутых контуров, то из них можно построить 5 полигонов, используя чётные контура как внешние, а нечётные – как внутренние.
Примечание 2. Успешная группировка с образованием ряда правильных полигонов вовсе не говорит об их географической взаимосвязи. К примеру, может получиться геометрическая фигура с двумя пересекающимися кольцами, уступающими двум полигонам. Это разрешается на следующем шаге.
Примечание 3. Нужно понимать, что данный алгоритм не использует роли (inner, outer). Их можно использовать с осторожностью, потому что традиционной ошибкой при создании отношения для лесного массива с островком внутри является добавление этого островка к совсем другому лесу. Пометка внешнего контура внутренним в тегах (inner) является дополнительным сигналов тревоги.
Создание мультиполигона
| Шаг | Описание |
|---|---|
| MC-1 | Проверить полигоны, созданные на этапе группировки, на пересечения (не считая вложенных полигонов, описанных в шаге RG-5).
Если такие пересечения находятся, создание мультиполигона считается неудачным. |
| MC-2 | Составить мультиполигон из всех полигонов, полученных на этапе группировки контуров, опять же не включая вложенные полигоны шага RG-5. |
Это всё.
Для составления тегов:
- Если имеются теги самого отношения, необходимо использовать именно их, игнорируя все теги входящих в него линий. Следует помнить, что лесной массив может быть огранен линиями электропередач, дорогами или железными дорогами!
- Если у отношения отсутствуют теги, необходимо проверить наличие тегов у линий, образующих внешние контуры (см. шаг RG-3).
- Если все линии внешнего контура имеют одинаковый набор тегов, то полагается использовать именно эти теги.
- В противном случае можно либо попытаться скомбинировать эти теги, либо вообще отказаться от анализа этого отношения.
- На шаге RG-5 можно пометить объединённый внутренний полигон тегами, если образующие его внутренние контуры имеют теги, отличающиеся от тегов отношения или внешних контуров.
Вероятно, имеются некоторые теги, которые могут быть проигнорированы при выполнении указанных сравнений, такие как “source”, “created_by”, “note” и, возможно, “name”.
Ссылки
- Можно использовать функции PostGIS, такие как ST_MakePolygon или ST_BuildArea.