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

На работе я постоянно сталкиваюсь со множеством интересных задач. Недавно мне понадобилось построить тепловую карту практически на чистом 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.

Про нелогичные API

Не могу сказать, что у меня огромный опыт интеграции с внешними службами, но несколько геоинформационных сервисов и соцсетей за этот год я подключил. Мне даже начало казаться, что общедоступное API сначала хорошо продумывают и только потом открывают для всех. Я бы пребывал в счастливом неведении и дальше, но, к сожалению, сверху пришла задача подключиться к Яндекс.Деньгам.
Общая идея довольно простая: я на своей стороне формирую XML-запрос, отправляю его на указанный адрес, и получаю XML-ответ. Проблема в требованиях, которым этот XML-запрос должен удовлетворять:

  • Серия и номер паспорта должны передоваться как одно целое число(!). Возможно, сотрудники Яндекс.Денег видят от этого какую-то пользу (быстрые запросы, например), но как я по мне, это просто идеологически неверно. Но, что гораздо хуже, в России до сих пор можно встретить людей с паспортом СССР, а там в серии могут присутствовать буквы.
  • Дата выдачи паспорта разбита на три числовых поля docIssueYear, docIssueMonth и docIssueDay — год, месяц и день выдачи. Опять же оставим в стороне тот факт, что это идеологически неверно, лучше посмотрим на то, как передаются другие даты. День рождения должен передаться одним текстовым полем в формате ДД.ММ.ГГГГ, а время передачи запроса опять же текстом, но уже в формате ГГГГ-ММ-ДДTЧЧ:ММ:СС.000Z
  • Под место рождения (а там чаще всего указывается только город) отдаётся целых 100 символов, а вот под город проживания только 30. Жителям крупных городов повезло, а вот как быть тем, кому приходится указывать область или район и только потом название села?
  • Вместо названия страны надо передать код «643». Причём, если я правильно понимаю, других кодов просто нет.
  • Всего 100 символов на адрес регистрации. Большинство адресов в этот лимит попадают, но ведь живут же люди и по адресу: Ханты-Мансийский Автономный округ — Югра, Нефтеюганский р-н, пгт Пойковский, Центральная ул., д xx стр xx, кв. xx! Им-то как быть?

К чему я это всё? Не делайте так!
А к Яндекс.Деньгам мы всё же подключились.

Монография по цифровой обработке изображений

Возможно вы знаете, что я уже несколько лет работаю над цифровой обработкой изображений и видеопотоков, да и диссертация моя посвящена разработке алгоритмов сжатия видео.
Мы с научным руководителем останавливаться не планируем и перед поступлением в докторантуру решили выпустить монографию. Как говорится, скоро во всех магазинах страны:

День 16. Москва — Вена — Прага — Москва

Последний день в Праге надо было провести с пользой. Под пользой подразумевается осмотр оставшихся достопримечательностей. В первую очередь национального музея, который находится на Вацлавской площади. Я был уверен, что этот музей находится в красивом здании прямо за памятником святому Вацлаву:

Вацлавская площадь (Прага)

Вацлавская площадь (Прага)


Но оказлось, что экспозиции размещены (надеюсь временно) в современном здании чуть левее.
Музей этот мягко говоря очень странный. Если начало экспозиции более-менее традиционное — отпечатки морских звёзд в доисторических породах и черепа динозавров, то дальше начинается нечто странное. Зал с мумиями и комната от пола до потолка заполненная черепами -это ещё самые нормальные экспонаты первого этажа. Целый зал посвящён способам самоубийств. Таблетки, пузырьки с лекарствами, ножи и даже самодельная виселица. Просто удивительно, в России запрещают доступ к сайтам, где есть информация о способах самоубийств, а в Чехии для этих способов отдельный зал в крупнейшем музее выделяют. Следующий зал не лучше. Там выставлены абсолютно обычные предметы: утюги, молотки для отбивания мяса, опасные бритвы, ножи, ножницы, — объединяет эти предметы то, что все они были использованы для убийства. Жутковато, конечно, но после костехранилища в Седлеце меня напугать не так просто.
Другой этаж музея полностью заполнен чучелами животных. Помню, после посещения музея естествознания в Вене я утверждал, что чучела отвратительны и смотреть на них неприятно. В национальном музее я убедился, что был неправ. Чешские таксидермисты достигли высот в своей нелёгкой и странной профессии. Все чучела выглядят как живые, и на них по-настоящему интересно смотреть.
Чучело красной панды в национальном музее (Прага)

Чучело красной панды в национальном музее (Прага)


Последний этаж в национальном музее состоит всего из одного зала. Но зал этот очень необычный, но в необычный в хорошем смысле. Там можно не только потрогать различные материалы, но и понюхать их. Вот так выглядят «обонятельные» экспонаты:
Зал ароматов в национальном музее (Прага)

Зал ароматов в национальном музее (Прага)


По-моему, это просто гениальное изобретение. Очень простое в реализации, но невероятно интересное на практике. Думаю, не совру, если скажу, что больше всего времени я провёл именно у этого стенда, нюхая то липу, то ромашку.
После музея мы ещё раз зашли на Староместскую площадь, чтобы посмотреть на знаменитые средневековые часы, перекусили в ресторане с паровозиками и отправились в отель дожидаться трансфера. Машина за нами приехала существенно раньше, чем должна была, но мы, наученные опытом Вены, собрали вещи ещё вчера, а утром перенесли их в хранилище багажа. По пути к вокзалу мы подобрали ещё двоих туристов (женщину с сыном) из Курска. Эта женщина была настолько нервной, что за несколько минут умудрилась достать нас вопросами о том не опоздаем ли мы на поезд, а точно ли на один поезд мы должны сесть, а куда поезд прибывает и ещё десятком аналогичных вопросов. Больше всего мы опасались, что именно с ней нам придётся ехать в одном купе до Москвы. Но к счастью обошлось.
В купе с нами едет пожилая пара: мужчина семидесятичетырёх лет и его немолодая спутница. Мужчина этот для начала долго и обстоятельно рассказывал нам с Леной о том, как он не любит негров и почему не поедет во Францию. Потом он немного помолчал и начал просто бесконечный рассказ о пиве. В этом рассказе было всё: и октоберфест, и сравнительный анализ чешского, немецкого и российского пива, и рассуждения о том, что вобла не нужна, и воспоминания о том, как в его молодости разливали пиво в трёхлитровые банки. Короче я узнал о пиве намного больше, чем хотел. Рассказ прервался только на остановке в Богумине. Там этот мужик (семидесятичетырёх лет!) побежал(!) с проводником за пивом. Пока он бегал, его спутница обзывала его старым дураком и хваталась за сердце, переживая успеет ли он вернуться. Вернулся он за несколько минут до отправления с двумя бутылками. Высказав, всё, что накопилась, его спутница взяла валидол и легла спать. Через некоторое время мы последовали её примеру. Так и закончился последний шестнадцатый день нашего путешествия.