задний план

При обработке данных GPS часто бывает много данных с одинаковыми временными метками и расстояниями в записях.С одной стороны, много места для хранения тратится впустую, а с другой стороны, графики, которые должны быть выражены, не являются гладкими или не соответствуют стандартам. Следовательно, необходимо использовать определенное правило для минимизации количества точек данных при условии, что форма векторной кривой остается неизменной.Этот процесс называетсятонкий.

Часто используемые алгоритмы прореживания, включая, но не ограничиваясь (эта часть контента взята из Интернета)

Алгоритм пошагового сжатия: извлечение точки на каждом определенном шаге непрерывной кривой, сжатие всех оставшихся точек, а затем аппроксимация соседних извлеченных точек прямой линией или кривой.
Алгоритм фильтрации линейного сегмента: когда длина сегмента меньше определенного значения фильтра, средняя точка сегмента используется для замены сегмента, так же как два конца сегмента вырождаются в среднюю точку.
Алгоритм Дугласа-Пейкера (также известный как алгоритм Ламера-Дугласа-Пейкера, итеративный адаптивный точечный алгоритм, алгоритм разделения и слияния) — это метод приблизительного представления кривой в виде последовательности точек и уменьшения количества точек. алгоритм.

В PostGIS встроены некоторые распространенные алгоритмы, давайте проведем простой тест.

Использование функций PostGIS

Используемые функции PostGIS следующие:

ST_Simplify
ST_SimplifyVW
ST_SimplifyPreserveTopology

прореживание колеи

Функция ST_Simplify() основана наDouglas-PeuckerАлгоритм утончает траекторию, и конкретный принцип здесь не объясняется. Но одно замечание состоит в том, что,При использовании WGS84 параметр допуска алгоритма указывается в градусах..

Долгота и широта различны в разных регионах, и разница расстояний на градус различна.Если считать землю идеальной сферой (это предполагает, что ошибка не очень велика), область с широтой B:

Широта изменяется на один градус, а расстояние изменяется в направлении север-юг сферы: πR/180 ........111,7 км.
Долгота меняется на один градус, а расстояние в направлении восток-запад сферы меняется: πR/180cosB ....111.7cosB

Например, Пекин B = 40, Cosb = 0,766 и многообразие меняется на 1 градус, то расстояние в восточном западе на 85,567 км.

Для удобства расчета,Мы предполагаем, что в пределах Китая 1 градус составляет около 100 километров..

Алгоритм Дугласа-Пекера

После прореживания траекторное расстояние будет потеряно из-за изменения топологической формы. Мы надеемся, что в результате космический масштаб будет как можно меньше, а масштаб расстояний — как можно больше.

Тест, когда допустимое расстояние составляет 1000 метров, 100 метров, 10 метров, сравнение результатов прореживания.

with simplified_trajectory as 
(
	-- 1 degree = 100 km
	select 
		tr.tid, tr.dt,
		st_npoints(traj) as np_orgin,
		(st_length(traj::geography)/1000) ::int as km_orgin,
		-- 0.01 degree = 1000 m
		st_npoints( ST_Simplify(traj,0.01,true) ) as np_01,
		(st_length(ST_Simplify(traj,0.01,true)::geography)/1000) ::int as km_01,
		-- 0.001 degree = 100 m
		st_npoints( ST_Simplify(traj,0.001,true) ) as np_001,
		(st_length(ST_Simplify(traj,0.001,true)::geography)/1000) ::int as km_001,
		-- 0.0001 degree = 10 m
		st_npoints( ST_Simplify(traj,0.0001,true) ) as np_0001,
		(st_length(ST_Simplify(traj,0.0001,true)::geography)/1000) ::int as km_0001,
		1 as endflag
	from demo.t_taxi_trajectory tr
)
select st.tid, st.dt, st.np_orgin, st.km_orgin,
	(st.np_01 / st.np_orgin::float)::decimal(4,2) as np_01_pct,
	(st.km_01 / st.km_orgin::float)::decimal(4,2) as km_01_pct,
	(st.np_001 / st.np_orgin::float)::decimal(4,2) as np_001_pct,
	(st.km_001 / st.km_orgin::float)::decimal(4,2) as km_001_pct,
	(st.np_0001 / st.np_orgin::float)::decimal(4,2) as np_0001_pct,
	(st.km_0001 / st.km_orgin::float)::decimal(4,2) as km_0001_pct
from simplified_trajectory st
where 1=1	
	and st.dt = '2008-02-06'
	and st.tid  in (28,10012)
	order by st.tid, st.dt
;

Алгоритм Висвалингама-Уайатта

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

При тестировании было обнаружено, что допуск в алгоритме VW не такой, как у DP, и причина этого неизвестна.

Пошаговый алгоритм сжатия

Алгоритм размера шага каждые десять используется для исходных точек траектории, то есть рисуется одна из каждых 10 исходных точек.

-- 常规做法应该从原始GPS点数据开始，但是为了演示和测试，选择把轨迹还原成GPS然后再抽稀
with dump_pt as
(
	select tid, 
		(st_dumppoints(tr.traj)).path[1] as sn, 
		(st_dumppoints(tr.traj)).geom as pt 
	from demo.t_taxi_trajectory tr
),
-- 每10个原始点划分为一个组
rank_pt as
(
	select 
		tid, to_char(to_timestamp(st_m(pt)), 'yyyy-mm-dd') as ts ,
		st_setsrid( st_makepointm( st_x(pt), st_y(pt), st_m(pt) ), 4326) pt,
		row_number() over (partition by tid, sn/10 order by sn) as rn
	from dump_pt 
)
select rpt.tid, rpt.ts,
	st_makeline( array_agg(rpt.pt order by rpt.ts )::geometry[] ) as traj
from rank_pt rpt
where rpt.rn = 1
group by rpt.tid, rpt.ts
;

Влияние порога допуска на алгоритм DP

  tid  |     dt     | np_orgin | km_orgin | np_01_pct | km_01_pct | np_001_pct | km_001_pct | np_0001_pct | km_0001_pct
-------+------------+----------+----------+-----------+-----------+------------+------------+-------------+-------------
    28 | 2008-02-06 |      947 |      180 |      0.01 |      0.94 |       0.03 |       0.97 |        0.15 |        0.98
 10012 | 2008-02-06 |      687 |        5 |      0.00 |      0.00 |       0.00 |       0.00 |        0.14 |        0.40
(2 rows)

Из этого примера данных

Большое исходное расстояние (947 км)
- При допуске 1000 метров количество точек координат уменьшается на 1%, а расстояние уменьшается на 94%;
- При допуске 100 метров количество точек координат уменьшается на 3%, а расстояние уменьшается на 97%;
- При допуске 10 метров количество точек координат уменьшается на 15%, а расстояние уменьшается на 98%;
Короткая исходная дистанция (5 км)
- Когда допуск составляет 1000 метров, количество точек координат уменьшается до 0%, а расстояние уменьшается до 0% (сильное отклонение);
- 100 м-толерантность, уменьшение количества координатных точек 0%, 0%, чтобы уменьшить расстояние (отклонение тяжело);
- При допуске 10 метров количество точек координат уменьшается на 15%, а расстояние уменьшается на 40%;

Поэтому, когда исходное расстояние траектории относительно велико, хорошо работает допуск в 100 метров. Если исходное расстояние короткое, требуется меньший допуск.

Сравнение эффекта утончения траектории

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

drop table if exists demo.t_02;
create table if not exists demo.t_02 (id text, traj geometry(linestringm, 4326));


insert into demo.t_02 
select 'src', traj from demo.t_taxi_trajectory where tid=28 and dt='2008-02-02'
union all
select 'dp', ST_Simplify(traj,0.001,true)  from demo.t_taxi_trajectory where tid=28 and dt='2008-02-02'
union all
select 'vw', ST_SimplifyVW(traj,0.00001)  from demo.t_taxi_trajectory where tid=28 and dt='2008-02-02'
;

--
with dump_pt as
(
	select tid, 
		(st_dumppoints(tr.traj)).path[1] as sn, 
		(st_dumppoints(tr.traj)).geom as pt 
	from demo.t_taxi_trajectory tr
	where tr.tid in (28) 
		and tr.dt = '2008-02-02' 
),
--
rank_pt as
(
	select 
		tid, to_char(to_timestamp(st_m(pt)), 'yyyy-mm-dd') as ts ,
		st_setsrid( st_makepointm( st_x(pt), st_y(pt), st_m(pt) ), 4326) pt,
		row_number() over (partition by tid, sn/10 order by sn) as rn
	from dump_pt 
)
--
insert into demo.t_02 
select '10-1',
	st_makeline( array_agg(rpt.pt order by rpt.ts )::geometry[] ) as traj
from rank_pt rpt
where rpt.rn = 1
group by rpt.tid, rpt.ts
;

алгоритм	Количество точек трека	Отслеживать километры
Оригинальный трек	387	190
DP 0.001	130	188
VW 0.00001	107	174
Шаг 10 рисуем 1	39	140

График сравнения эффектов выглядит следующим образом (вывод справедлив только для этих данных), видно, что точность ДП наилучшая, а размер шага 10 – наихудший.

Топологическое истончение

Алгоритм Дугласа-Пекера

Подобно ST_Simplify, функция ST_SimplifyPreserveTopology также использует алгоритм DP для прореживания. Но ST_SimplifyPreserveTopology может гарантировать, что прореженные данные являются допустимой топологией.

Я не особо понимаю, но мое понимание

Значение M не поддерживается, поэтому его нельзя использовать для прореживания данных траектории на основе LinestringM.
Истончается ли полигональный объект, лучше всего использовать эту функцию. (не спрашивайте почему, потому что я тоже не понимаю)

-- 容差0.001的DP拓扑抽稀
select 
	st_multi(st_simplifypreservetopology(fence_polygon, 0.001)) as fence_polygon
from demo.t_area_fence where id = 510107;

Сравнение эффекта топологического прореживания

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

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

drop table if exists demo.t_03;
create table if not exists demo.t_03 (id text, fence_polygon geometry(multipolygon, 4326));


insert into demo.t_03 
select 'src', fence_polygon from demo.t_area_fence where id = 510107
union all
select 'dp', st_multi(ST_Simplify(fence_polygon,0.001,true)) from demo.t_area_fence where id = 510107
union all
select 'dppt', st_multi(st_simplifypreservetopology(fence_polygon, 0.001)) as fence_polygon from demo.t_area_fence where id = 510107
;

алгоритм	Количество точек забора
оригинальный забор	830
DP 0.001	126
Топология DP 0,001	127

Таблица сравнения эффектов выглядит следующим образом (вывод справедлив только для этих данных), в красном прямоугольнике есть небольшие отличия, которые можно учитывать в бизнес-сценариях ГИС технического исследовательского характера.