Здесь будет рассмотрен способ деления сферической поверхности процедурно-генерируемой планеты нерегулярными тайлами, и, как его следствие, подразделение океана и континентов на отдельные участки (сектора). Мы предполагаем, что на поверхности планеты уже задана структура участков суши с помощью какой-либо GIS и возможен экспорт векторных данных в ESRI shapefiles или непосредственно в PostgreSQL базу данных с расширением PostGIS. Сам процесс создания секторов осуществляется средствами PostGIS.
Ссылку на скрипт с SQL кодом смотрите внизу поста, здесь же объяснение будет больше на-пальцах. В объяснении приводятся основные функции из скрипта, а также предполагается наличие данных для континентов и рек процедурно-генерируемых планет взятых с forgedmaps.com.
Выбор именно нерегулярных тайлов позволяет нам точно подразделять поверхность планеты
на сектора, вообще нигде не смешивая территории океана и суши. Озера и внутренние моря
мы здесь считаем частью суши. Так же мы увидим как можно использовать реки в качестве естественных границ секторов. Сами сектора будем строить на основе некоторого базового деления сферы полигонами.
Когда речь идет о делении плоской области, обыкновенно, для получения нерегулярных тайлов прибегают к диаграмме Вороного. Применяя, также, алгоритм Ллойда, можно прийти к визуально привлекательному виду выпуклых полигонов не сильно отличающих по размеру (Centroidal Voronoi tessellation). Суть алгоритма Ллойда состоит в том, чтобы повторять построение диаграммы Вороного, на каждой следующей итерации беря в качестве порождающих точек центры полигонов, полученных на предыдущей итерации.
На базовое деление полигонами сферы мы будем налагать определенные требования:
выпуклость сферических полигонов и не очень большие отклонения их от заданного среднего размера.
Название сектор используется вместо тайл из-за того, что тайл обыкновенно имеет элементарный смысл, например, как единичная часть тайловых карт стратегических игр, или как единичная часть некоторой поверхности. Внутри же сектора имеется внутренняя структура: рельеф и различные географические объекты в нем. Сектора, в свою очередь, тоже могут служить элементарными тайлами: этой цели служит построение графа возможных переходов между секторами.
Базовое деление сферы и сегменты океанов.
В PostGIS существует функция ST_VoronoiPolygons, которая строит диаграмму Вороного в квадратной области. Посмотрим, как мы можем ее использовать для наших целей.
Что получится, если попытаться использовать прямолинейный подход? Какую-либо прямоугольную проекцию планеты можно преобразованием координат привести к квадрату, построить там полигоны и совершить обратное преобразование координат. Но, построенные таким образом прямоугольники будут вытянуты в одном направлении, что было бы нежелательно. А, если пытаться применить алгоритм Ллойда, то прямоугольники близкие к полюсам сферы окажутся существенно меньше по площади (на сфере), чем близкие к экватору.
Попробуем адаптировать этот способ с устранением недостатков. Случайные исходные точки диаграммы Вороного выбираем так, чтобы они равномерно распределялись на сфере. В проекции Меркатора это означает, что к полюсам они должны появляться реже с вероятностью пропорциональной косинусу от широты. Диаграмму Вороного строим в «мировом» полигоне, — это или вся прямоугольная проекция планеты или только ее часть. Функция ST_VoronoiPolygons сама достраивает прямоугольник до квадрата, мы должны только обрезать полученную диаграмму по «мировому» полигону.
Смотрим картину полученных адаптированным способом полигонов Вороного. Здесь показана часть карты тестовой планеты от экватора на верхнем крае до 73 градусов южной широты на нижнем крае. (Здесь территория суши уже вырезана из полигонов.)
Как видно на проекции Меркатора полигоны, как правило, больше при приближении к полюсам, но на сфере они будут приблизительно одинаково распределены по величине площади. Это то, что нам нужно. Но, так же видно, что полигоны имеют очень большой разброс площадей и общая картина довольно неприглядна.
Попробуем применить несколько итераций алгоритма Ллойда. В качестве новых точек
для последующих итераций диаграммы Вороного будем выбирать центры уже обрезанных
«мировым» полигоном полигонов Вороного. И, чтобы предотвратить слишком большое уменьшение площадей полигонов вблизи полюсов, мы делаем только небольшое количество итераций (3 или около того).
Для получения сегментов океана из полученных полигонов исключается площадь занятая сушей. В результате могут образовываться полигоны маленького размера, которые желательно присоединить к соседним. Также маленькие полигоны могут оказаться вблизи границы «мирового» полигона. Присоединение полигонов делаем так, чтобы выбрать «ближайшего» соседа и не сильно испортить общую картину.
После применения такого модифицированного алгоритма получаем следующую картину, которая уже может быть приемлема. Красными отрезками на рисунке обозначены желательные слияния полигонов.
Выбор полигонов для слияния можно делать по-разному. В упомянутом скрипте реализованы 2 способа: по самой длинной границе и по ближайшему центру. На следующем рисунке приведен результат слияния по второму способу.
В целом мы добились того, чего можно желать от океанских секторов. Их площадь примерно одинакова (на сфере), и они или выпуклы, или с небольшими отклонениями от выпуклости.
Основная функция для генерации океанских секторов:
map.makeOceanSectors(
world Geometry,
avg_vp_areaKM Double Precision,
merging_ratio Double Precision,
merging_method Int
) RETURNS Void
world — «мировой» полигон, служащий границами мира.
avg_vp_areaKM — средняя площадь (km2) полигонов, из которых делаются океанские сектора.
merging_ratio — доля avg_vp_areaKM, такая, что если площадь сектора меньше нее, то он будет присоединен к соседнему.
merging_method — метод слияния ('1' или '2').
Пример. Строим сектора в заданном «мировом» полигоне со средней площадью базовых полигонов в 1000000 км2. Сектора, площадь которых окажется мешьше чем половина от этой величины, будут присоединены к другим. Используется второй метод слияния — по ближайшему центру.
SELECT * FROM map.makeOceanSectors( ST_GeomFromText(
'POLYGON((-75 -85, 75 -85, 75 85, -75 85, -75 -85))', 4326 ),
1000000, 0.5, 2
);
Сегменты континентов.
На материках можно ввести, более интересное подразделение, основываясь, с одной стороны, на совокупности маленьких базовых полигонов, а с другой, на естественные природные объекты, такие как реки и водоразделы. Полученная, таким образом, структура очень похожа на карту государств и провинций в них. То есть это процесс процедурной генерации политической карты мира.
В отличии от сегментов океанов, выпуклость становится совсем необязательной.
Водоразделы на forgedmaps.com пока не создаются, но реки уже есть. Использование рек в скрипте требует их представления в MultiLineString. Такое представление они имеют в шейпфайле riversz. При импорте в базу данных можно сразу избавиться от лишней в данном процессе z-координаты. Другие требуемые данные, а именно, границы участков суши, находятся в шейпфайле lands. Каждый участок суши имеет идентификатор aid (area Id) и может состоять из континента и ближайших островов или только из небольших островов расположенных близко.
Для нашего примера выберем средний размер сектора в 40000 km2 и средний размер базового полигона в 5000 km2. Это довольно большой размер, выбранный таким только для наглядности. Меньшие размеры тоже допустимы (вплоть до считанных m2), но следите за временем вычислений и используйте подходящую конфигурацию базы данных.
На этой картинке пример того, как выглядят базовые полигоны внутри участка суши.
Следующим шагом делаем объединение базовых полигонов в сектора. Для этого случайным образом выбираем из базовых полигонов столько сколько хотим сделать секторов и присоединяем постепенно соседние полигоны к накапливающимся секторам.
Теперь настало время принять во внимание реки. Используем их для деления секторов на
отдельные части функцией ST_Split. Такое деление можем выполнять в зависимости от некоторых условий: финальный сток реки или площадь отделяемой части.
Теперь мы можем увидеть как некоторые границы идут по рекам.
Мелкие части секторов присоединяем к большим секторам. Но при этом мы должны стараться
не присоединять части к тем же самым секторам, от которых они были отрезаны.
С большими участками суши мы управились, но остаются еще мелкие острова. Те из них, которые имеют площадь близкую к средней площади сектора делаем отдельным секторами сразу. А вот с теми, площадь которых много меньше среднего сектора, мы поступаем двояко.
1. Если такие острова располагаются сравнительно далеко от уже имеющихся секторов, то делаем их отдельными секторами. «Далекость» здесь зависит от заданной средней площади сектора: чем меньше эта площадь тем более вероятно, что остров станет отдельным сектором.
2. Если остров находится вблизи от других уже созданных секторов, то он объединяется с одним из них. А именно, с тем, который имеет наибольшую площадь в некотором полигоне полученном с помощью ST_Buffer из этого острова.
Здесь четыре острова попали в два разных сектора. Если увеличивать заданную среднюю площадь сектора, то рано или поздно все острова попадут в один единственный сектор.
Основная функция для генерации секторов на суше:
map.makeLandSectors(
aid BigInt,
avg_vp_areaKM Double Precision,
avg_sector_areaKM Double Precision,
max_sector_cut_area_ratio Float,
pref_min_island_area_ratio Float,
min_streamflow Int
) RETURNS Void
aid — идентификатор участка суши.
avg_vp_areaKM — средняя площадь (km2) базовых полигонов.
avg_sector_areaKM — средняя площадь (km2) секторов.
max_sector_cut_area_ratio — доля avg_sector_areaKM, которая определяет максимальную область, что может быть отрезана рекой.
pref_min_island_area_ratio — доля avg_sector_areaKM, которая определяет минимальную площадь, имея которую остров сразу становится отдельным сектором.
streamflow — если река имеет финальный сток не меньше этого значения, то она участвует в разрезании секторов.
В следующем примере использование функции создаст сектора на участке земли с aid=5. При этом будут использоваться базовые полигоны со средней площадью в 5000 km2 для создания секторов со средней площадью в 40000 km2. Также, при этом, максимальная территория отсекаемая реками будет 0.125*40000 km2, а 0.25*40000 km2 является минимальной площадью, при которой острова сразу становятся секторами. Для разрезания секторов реками используются реки с минимальным финальным стоком 2.
SELECT * FROM map.makeLandSectors(5, 5000, 40000, 0.125, 0.25, 2);
Ссылки
Доступен код SQL скрипта, который выполняет всю работу, включая создание секторов и построение графов переходов между соседними секторами. GIS данные процедурно-генерируемых планет можно взять с forgedmaps.com. Можно воспользоваться GIS данными Земли, приведя их к схожей структуре. Можно также, пользуясь любой современной GIS, сделать данные вручную с нуля или получить новые данные путем преобразования данных полученных из любого другого источника. Более полную инструкцию к скрипту можно найти в мануале.
Автор: igor720
