Разбиение полигонов

На работе я постоянно сталкиваюсь со множеством интересных задач. Недавно мне понадобилось построить тепловую карту практически на чистом SQL. Не знаю оптимально ли моё решение или нет, но я поступил следующим образом:

  1. Разбил участок карты на множество маленьких полигонов;
  2. Для каждого полигона вычислил «теплоту»;
  3. При отображении на клиенте каждый маленький полигон закрашивается своим цветом, зависящим от вычисленной на втором шаге «теплоты».

В результате на клиенте можно наблюдать подобные картины:

Тепловая карта

Тепловая карта

Приведённый ниже участок кода на T-SQL выполняет первый шаг описанного алгоритма — разбивает участок карты на множество маленьких квадратных полигонов. В этом коде нет ничего особого сложного или выдающегося, тем не менее, я надеюсь, что если вы столкнётесь с подобной задачей, мой код послужит основой для вашего решения.

  1. SET QUOTED_IDENTIFIER ON
  2. SET ANSI_NULLS ON
  3. GO
  4. — =============================================
  5. — Author:          Горьков А.Г.
  6. — Description:     Разбивает заданный полигон на множество «квадратных» полигонов
  7. — =============================================
  8. CREATE FUNCTION dbo.fnT_PolygonToGrid
  9.     (
  10.       @Polygon GEOMETRY — Обрабатываемый полигон
  11.     , @CellCount INT— Количество «квадратов» в результате разбиения
  12.     , @PartitionType INT  — 0 — в результате разбиения и по ширине, и по высоте будет НЕ БОЛЕЕ чем @CellCount «квадратов» 1 —  в результате разбиения и по ширине, и по высоте будет НЕ МЕНЕЕ чем @CellCount «квадратов»
  13.     )
  14. RETURNS @Grid TABLE
  15.     (
  16.       Cell GEOMETRY NOT NULLa
  17.     )
  18. AS
  19. BEGIN
  20.        — Получаем описывающий прямоугольник для участка
  21.     DECLARE @EnvelopePolygon GEOMETRY = @Polygon.STEnvelope()
  22.     DECLARE @EnvelopeWidth FLOAT = @EnvelopePolygon.STPointN(3).STX  @EnvelopePolygon.STPointN(1).STX
  23.     DECLARE @EnvelopeHeight FLOAT = @EnvelopePolygon.STPointN(3).STY  @EnvelopePolygon.STPointN(2).STY
  24.        — Получаем левый нижний угол описывающего прямоугольника
  25.     DECLARE @xStart FLOAT = @EnvelopePolygon.STPointN(1).STX
  26.     DECLARE @yStart FLOAT = @EnvelopePolygon.STPointN(1).STY
  27.        — Вычисляем шаги по широте и долготе
  28.     DECLARE @CellWidth FLOAT = @EnvelopeWidth / @CellCount
  29.     DECLARE @CellHeight FLOAT = @EnvelopeHeight / @CellCount
  30.        — Таблица с результирующей сеткой
  31.     DECLARE @RAWGrid TABLE ( geom GEOMETRY )
  32.        — Отдельная таблица для мультиполигонов, получившихся при разбиении
  33.     DECLARE @MultiPolygons TABLE
  34.         (
  35.           MultiPolygon GEOMETRY
  36.         )
  37.     DECLARE @MultiPolygon GEOMETRY= NULL
  38.     DECLARE @i INT = NULL
  39.        /*
  40.        В зависимости от типа разбиения подбираем длину стороны ячейки
  41.        */
  42.     IF @PartitionType = 1
  43.     BEGIN
  44.         IF @CellHeight < @CellWidth
  45.             SET @CellWidth = @CellHeight
  46.         ELSE
  47.             SET @CellHeight = @CellWidth
  48.     END
  49.     ELSE
  50.     BEGIN
  51.         IF @CellHeight > @CellWidth
  52.             SET @CellWidth = @CellHeight
  53.         ELSE
  54.             SET @CellHeight = @CellWidth
  55.     END
  56.        /*
  57.        Заполняем таблицу равномерной сеткой
  58.        В результате такого разбиения в ячейках могут присутствовать не только
  59.        обычные полигоны, но и мультиполигоны, с которыми мы разберемся ниже
  60.     */
  61.     DECLARE
  62.         @x INT = 0
  63.       , @y INT = 0
  64.     WHILE @y * @CellHeight <= @EnvelopeHeight
  65.     BEGIN
  66.         WHILE @x * @CellWidth <= @EnvelopeWidth
  67.         BEGIN
  68.             INSERT  INTO @RAWGrid
  69.             VALUES
  70.                     ( Geometry::STPolyFromText(‘POLYGON((‘ + CAST(@xStart + ( @x * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( @y * @CellHeight ) AS VARCHAR(32)) + ‘,’ + CAST(@xStart + ( ( @x + 1 ) * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( @y * @CellHeight ) AS VARCHAR(32)) + ‘,’ + CAST(@xStart + ( ( @x + 1 ) * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( ( @y + 1 ) * @CellHeight ) AS VARCHAR(32)) + ‘,’ + CAST(@xStart + ( @x * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( ( @y + 1 ) * @CellHeight ) AS VARCHAR(32)) + ‘,’ + CAST(@xStart + ( @x * @CellWidth ) AS VARCHAR(32)) + ‘ ‘ + CAST(@yStart + ( @y * @CellHeight ) AS VARCHAR(32)) + ‘))’ , 4326) )
  71.             SET @x = @x + 1
  72.         END
  73.         SET @x = 0
  74.         SET @y = @y + 1
  75.     END
  76.        /*
  77.        Сохраняем обычные полигоны в итоговую таблицу
  78.     */
  79.     INSERT  INTO @Grid
  80.             SELECT
  81.                 geom.STIntersection(@Polygon)
  82.             FROM
  83.                 @RAWGrid
  84.             WHERE
  85.                 ( 1 = 1 )
  86.                 AND ( geom.STIntersection(@Polygon).STGeometryType() = ‘Polygon’ )
  87.        /*
  88.        Сохраняем мультиполигоны во временную таблицу
  89.     */
  90.     INSERT  INTO @MultiPolygons
  91.             SELECT
  92.                 geom.STIntersection(@Polygon)
  93.             FROM
  94.                 @RAWGrid
  95.             WHERE
  96.                 ( 1 = 1 )
  97.                 AND ( geom.STIntersection(@Polygon).STGeometryType() = ‘MultiPolygon’ )
  98.        /*
  99.        Разбиваем мультиполигоны на обычные полигоны и переносим их в итоговую тбалицу
  100.        */
  101.     DECLARE c CURSOR
  102.     FOR
  103.     SELECT
  104.         @MultiPolygon
  105.     FROM
  106.         @MultiPolygons
  107.     OPEN c
  108.     FETCH c INTO @MultiPolygon
  109.     WHILE @@FETCH_STATUS = 0
  110.     BEGIN
  111.         SET @i = 1
  112.         WHILE @i <= @MultiPolygon.STNumGeometries()
  113.         BEGIN
  114.             INSERT  INTO @Grid
  115.                     ( Cell )
  116.             VALUES
  117.                     ( @MultiPolygon.STGeometryN(@i) )
  118.             SET @i = @i + 1
  119.         END
  120.         FETCH NEXT FROM c INTO @MultiPolygon
  121.     END
  122.     CLOSE c
  123.     DEALLOCATE c
  124.     RETURN
  125. END
  126. GO

Пожалуй, наиболее интересный момент здесь, это параметр — @PartitionType. Он показывает, как именно надо разбивать исходный полигон на части: чтобы в результате разбиения по ширине и высоте было НЕ БОЛЕЕ или НЕ МЕНЕЕ, чем @CellCount полигонов. Проще всего разницу пояснить на конкретном примере:

Виды разбиения

Виды разбиения

В первом случае @PartitionType=0, а во втором @PartitionType=1.

Добавить комментарий