Идентификация зараженных людей с помощью пересечения GPS-треков

В преддверии старта курса «PostgreSQL» подготовили перевод интересной статьи.

---

Во времена пандемии COVID-19 правительства предусматривают жесткие меры по выявлению и отслеживанию инфицированных людей. Эти меры включают использование данных мобильных телефонов для отслеживания зараженных людей и их контактов с целью обуздать эпидемию. Эта статья рассказывает, как функции PostGIS можно использовать для выявления пересекающихся участков путей зараженных и здоровых людей посредством пространственно-временного анализа треков.

На этот раз мы не концентрируемся на производительности и тюнинге, а скорее стремимся повысить уровень вашей креативности в отношении пространственного расширения PostgreSQL и его функциональных возможностей.

Структура статьи выглядит следующим образом:

1. Настройка структур данных в PostgreSQL.
2. Формирование выборки треков с помощью QGIS
3. Сегментация выборки треков для извлечения отдельных точек.
4. Нахождение пересечений зараженных и здоровых людей для определения возможных контактов.

Структуры данных

Начнем с определения таблиц, представляющих треки и их точки.

Таблица mobile_tracks является вспомогательной таблицей, хранящей смоделированные треки людей, которые были отобраны с помощью QGIS.

Таблица mobile_points хранит точки, которые являются результатом сегментирования треков. Они также были дополнены таймстампами, которые используются для определения временных пересечений на основе пространственных.

Тестовая зона находится в Вене/Австрия; поэтому я выбрал MGI/Austria 34 (EPSG равный 31286) в качестве подходящей проекции.

create table if not exists mobile_tracks
(
   gid serial not null
      constraint mobile_tracks_ok
         primary key,
   customer_id integer,
   geom geometry(LineString,31286),
   infected boolean default false
);
 
create index if not exists mobile_tracks_geom_idx
   on mobile_tracks using gist (geom);
 
create unique index if not exists mobile_tracks_customer_id_uindex
    on mobile_tracks (customer_id);
 
create table if not exists mobile_points
(
   gid serial not null
      constraint mobile_points_ok
         primary key,
   customer_id integer,
   geom geometry(Point,31286),
   infected boolean,
   recorded timestamp
);
 
create index if not exists mobile_points_geom_idx
   on mobile_points using gist (geom);

Треки и точки

Как уже упоминалось вначале, точки я решил сгенерировать на основе треков, которые ранее я преобразовал с помощью QGIS. На рисунке 1 изображены треки зараженных (красным ) и здоровых (зеленым) людей, которые мы взяли за основу.


Рисунок 1. GPS-треки здоровых и инфицированных людей.

Для нашего простого примера я сделал следующие допущения:

• Все люди движутся с одинаковой скоростью.
• Треки всех людей стартуют одновременно.

Для выделения отдельных точек для треков я использовал функцию PostGIS ST_Segmentize следующим образом:

with dumpedPoints as (
    select (st_dumppoints(st_segmentize(geom, 1))).geom,
           ((st_dumppoints(st_segmentize(geom, 1))).path[1]) as path,
           customer_id,
           infected,
           gid
    from mobile_tracks),
     aggreg as (
         select *, now() + interval '1 second' * row_number() over (partition by customer_id order by path) as tstamp
         from dumpedPoints)
insert
into mobile_points(geom, customer_id, infected, recorded)
select geom, customer_id, infected, tstamp
from aggreg;

Запрос генерирует точки каждый метр, последовательно увеличивая соответствующие таймстампы на 1000 миллисекунд.


Рисунок 2. Полученные GPS-точки.

Определение точек пересечения.

Теперь настало время начать анализ. Встречал ли наш инфицированный человек кого-нибудь?

Давайте начнем с простого подхода: выберем точки здоровых людей, которые находились в пределах 2 метров от зараженных с соответствующими временными интервалами в 2 секунды.

SELECT distinct on (m1.gid) m1.customer_id infectionSourceCust,
                            m2.customer_id infectionTargetCust,
                            m1.gid,
                            m1.recorded,
                            m2.gid,
                            m2.recorded
FROM mobile_points m1
         inner join
     mobile_points m2 on st_dwithin(m1.geom, m2.geom, 2)
where m1.infected = true
  and m2.infected = false
  and m1.gid < m2.gid AND (m2.recorded >= m1.recorded - interval '1seconds' and
       m2.recorded <= m1.recorded + interval '1seconds')
order by m1.gid, st_dwithin(m1.geom, m2.geom, 2) asc

На 3 и 4 рисунках показаны результаты данного запроса, где точки контактов наших индивидов выделены синим цветом. Как упоминалось ранее, этот запрос представляет самое простое решение для идентификации людей, которые встречались.

В качестве альтернативы, здесь также могут использоваться функции PostGIS ST_CPAWithin и ST_ClosestPointOfApproach для решения этой проблемы аналогичным образом. Для этого наши точки должны быть смоделированы как траектории.


Рисунок 3. Точки контактов.


Рисунок 4. Точки контактов в увеличении.

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

Шаг 1 — aggregStep1

На основе результатов нашего первого запроса мы вычисляем для каждой точки временной интервал до ее предшественницы. Учитывая наши первоначальные допущения, у некогерентных временных сегментов промежутки будут больше 1 секунды.


Рисунок 5. Временные промежутки между GPS-точками.

Шаг 2 — aggregStep2.

С помощью нашего нового столбца, указывающего временной промежуток между текущей и предыдущей точкой, мы кластеризируем сегменты.

Шаг 3 — aggregStep3.

Для каждого кластера мы отнимаем от максимального таймстампа минимальный, чтобы получить интервал совместного пути.


Рисунок 6. Когерентные сегменты + время совместного пути зараженного/здорового человека.

Шаг 4

Наконец, для каждой комбинации зараженного/здорового человека извлекается сегмент с максимальным временем совместного пути, и с помощью st_makeline генерируется lineString (см. Рисунок 7).


Рисунок 7. Максимальное время совместного пути зараженного/здорового человека.

Несмотря на то, что результаты уже могут служить основой для дальнейшего анализа, наш подход все еще ограничен нашими изначально принятыми допущениями.

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

with points as
         (
             SELECT distinct on (m1.gid) m1.customer_id infectionSourceCust,
 
                                         m2.customer_id infectionTargetCust,
                                         m1.gid,
                                         m1.geom,
                                         m1.recorded	m1rec,
                                         m2.gid,
                                         m2.recorded
             FROM mobile_points m1
                      inner join
                  mobile_points m2 on st_dwithin(m1.geom, m2.geom, 2)
             where m1.infected = true
               and m2.infected = false
               and m1.gid < m2.gid AND (m2.recorded >= m1.recorded - interval '1seconds' and
                    m2.recorded <= m1.recorded + interval '1seconds') order by m1.gid, m1.recorded), aggregStep1 as ( SELECT *, (m1rec - lag(m1rec, 1) OVER (partition by infectionSourceCust,infectionTargetCust ORDER by m1rec ASC)) as lag from points), aggregStep2 as (SELECT *, SUM(CASE WHEN extract('epoch' from lag) > 1 THEN 1 ELSE 0 END)
                 OVER (partition by infectionSourceCust,infectionTargetCust ORDER BY m1rec ASC) AS legSegment
          from aggregStep1),
     aggregStep3 as (
         select *,
                min(m1rec) OVER w   minRec,
                max(m1rec) OVER w   maxRec,
                (max(m1rec) over w) -
                (min(m1rec) OVER w) recDiff
         from aggregStep2
             window w as (partition by infectionSourceCust,infectionTargetCust,legSegment)
     )
select distinct on (infectionsourcecust, infectiontargetcust) infectionsourcecust,
                                                              infectiontargetcust,
                                                              (extract('epoch' from (recdiff))) passageTime,
                                                              st_makeline(geom) OVER (partition by infectionSourceCust,infectionTargetCust,legSegment)
from aggregStep3
order by infectionsourcecust, infectiontargetcust, passageTime desc

---

Успеть на курс.

---