網(wǎng)站首頁(yè) 編程語(yǔ)言 正文
對(duì)于GIS業(yè)務(wù)來(lái)說(shuō)，路徑規(guī)劃是非常基礎(chǔ)的一個(gè)業(yè)務(wù)，一般公司如果處理，都會(huì)直接選擇調(diào)用已經(jīng)成熟的第三方的接口，比如高德、百度等。當(dāng)然其實(shí)路徑規(guī)劃的算法非常多，像比較著名的Dijkstra、A*算法等。當(dāng)然本篇文章不是介紹算法的，本文作者會(huì)根據(jù)pgrouting已經(jīng)集成的Dijkstra算法來(lái)，結(jié)合postgresql數(shù)據(jù)庫(kù)來(lái)處理最短路徑。
一、數(shù)據(jù)處理
路徑規(guī)劃的核心是數(shù)據(jù)，數(shù)據(jù)是一般的路網(wǎng)數(shù)據(jù)，但是我們拿到路網(wǎng)數(shù)據(jù)之后，需要對(duì)數(shù)據(jù)進(jìn)行處理，由于算法的思想是基于有向圖的原理，因此首先需要對(duì)數(shù)據(jù)做topo處理，通過(guò)topo我們其實(shí)就建立了路網(wǎng)中各條道路的頂點(diǎn)關(guān)系，下面是主要命令：
--開(kāi)啟執(zhí)行路網(wǎng)topo的插件
create extension postgis;
create extension postgis_topology;
--數(shù)據(jù)創(chuàng)建拓?fù)?
ALTER TABLE test_road ADD COLUMN source integer;
ALTER TABLE test_road ADD COLUMN target integer;
SELECT pgr_createTopology('test_road',0.00001, 'geom', 'gid');其中test_road是將路網(wǎng)數(shù)據(jù)導(dǎo)入到postgresql中的表名。
處理完topo之后，基本就夠用了，我們就可以借助pgrouting自帶的函數(shù)，其實(shí)有很多，我們選擇pgr_dijkstra
CREATE OR REPLACE FUNCTION public.pgr_dijkstra(
IN edges_sql text,
IN start_vid bigint,
IN end_vid bigint,
IN directed boolean,
OUT seq integer,
OUT path_seq integer,
OUT node bigint,
OUT edge bigint,
OUT cost double precision,
OUT agg_cost double precision)
RETURNS SETOF record AS
$BODY$
DECLARE
BEGIN
RETURN query SELECT *
FROM _pgr_dijkstra(_pgr_get_statement($1), start_vid, end_vid, directed, false);
END
$BODY$
LANGUAGE plpgsql VOLATILE
COST 100
ROWS 1000;
ALTER FUNCTION public.pgr_dijkstra(text, bigint, bigint, boolean)
OWNER TO postgres;從函數(shù)輸入?yún)?shù)可以看到，我們需要一個(gè)查詢(xún)sql,一個(gè)起始點(diǎn)、一個(gè)結(jié)束點(diǎn)、以及是否考慮方向，好了了解到調(diào)用函數(shù)輸入?yún)?shù)，我們就來(lái)寫(xiě)這個(gè)函數(shù)。
二、原理分析
一般路徑規(guī)劃，基本都是輸入一個(gè)起點(diǎn)位置、一個(gè)終點(diǎn)位置然后直接規(guī)劃，那么對(duì)于我們來(lái)說(shuō)，要想套用上面的函數(shù)，必須找出起點(diǎn)位置target ，以及終點(diǎn)位置的source，然后規(guī)劃根據(jù)找出的這兩個(gè)topo點(diǎn)，調(diào)用上面的函數(shù)，來(lái)返回自己所需要的結(jié)果。
如何根據(jù)起始點(diǎn)找到對(duì)應(yīng)的target呢，其實(shí)就是找離起點(diǎn)最近線的target，同理終點(diǎn)的source，其實(shí)就是找離終點(diǎn)最近線的source,當(dāng)然將這兩個(gè)點(diǎn)規(guī)劃規(guī)劃好之后，基本就可以了，但是最后還需要將起點(diǎn)到起點(diǎn)最近先的target連接起來(lái)，終點(diǎn)到終點(diǎn)最近線的source連接起來(lái)，這樣整個(gè)路徑規(guī)劃就算完成了。
下面我們來(lái)看具體的實(shí)現(xiàn)存儲(chǔ)過(guò)程：
CREATE OR REPLACE FUNCTION public.pgr_shortest_road(
IN startx double precision,
IN starty double precision,
IN endx double precision,
IN endy double precision,
OUT road_name character varying,
OUT v_shpath character varying,
OUT cost double precision)
RETURNS SETOF record AS
$BODY$
declare
v_startLine geometry;--離起點(diǎn)最近的線
v_endLine geometry;--離終點(diǎn)最近的線
v_startTarget integer;--距離起點(diǎn)最近線的終點(diǎn)
v_endSource integer;--距離終點(diǎn)最近線的起點(diǎn)
v_statpoint geometry;--在v_startLine上距離起點(diǎn)最近的點(diǎn)
v_endpoint geometry;--在v_endLine上距離終點(diǎn)最近的點(diǎn)
v_res geometry;--最短路徑分析結(jié)果
v_perStart float;--v_statpoint在v_res上的百分比
v_perEnd float;--v_endpoint在v_res上的百分比
v_rec record;
first_name varchar;
end_name varchar;
first_cost double precision;
end_cost double precision;
begin
--查詢(xún)離起點(diǎn)最近的線
execute 'select geom,target,name from china_road where
ST_DWithin(geom,ST_Geometryfromtext(''point('|| startx ||' ' || starty||')''),0.01)
order by ST_Distance(geom,ST_GeometryFromText(''point('|| startx ||' '|| starty ||')'')) limit 1'
into v_startLine ,v_startTarget,first_name;
--查詢(xún)離終點(diǎn)最近的線
execute 'select geom,source,name from china_road
where ST_DWithin(geom,ST_Geometryfromtext(''point('|| endx || ' ' || endy ||')''),0.01)
order by ST_Distance(geom,ST_GeometryFromText(''point('|| endx ||' ' || endy ||')'')) limit 1'
into v_endLine,v_endSource,end_name;
--如果沒(méi)找到最近的線，就返回null
if (v_startLine is null) or (v_endLine is null) then
return;
end if ;
select ST_ClosestPoint(v_startLine, ST_Geometryfromtext('point('|| startx ||' ' || starty ||')')) into v_statpoint;
select ST_ClosestPoint(v_endLine, ST_GeometryFromText('point('|| endx ||' ' || endy ||')')) into v_endpoint;
--計(jì)算距離起點(diǎn)最近線上的點(diǎn)在該線中的位置
select ST_Line_Locate_Point(st_linemerge(v_startLine), v_statpoint) into v_perStart;
select ST_Line_Locate_Point(st_linemerge(v_endLine), v_endpoint) into v_perEnd;
select ST_Distance_Sphere(v_statpoint,ST_PointN(ST_GeometryN(v_startLine,1), ST_NumPoints(ST_GeometryN(v_startLine,1)))) into first_cost;
select ST_Distance_Sphere(ST_PointN(ST_GeometryN(v_endLine,1),1),v_endpoint) into end_cost;
if (ST_Intersects(st_geomfromtext('point('|| startx ||' '|| starty ||') '), v_startLine) and ST_Intersects(st_geomfromtext('point('|| endx ||' '|| endy ||') '), v_startLine)) then
select ST_Distance_Sphere(v_statpoint, v_endpoint) into first_cost;
select ST_Line_Locate_Point(st_linemerge(v_startLine), v_endpoint) into v_perEnd;
for v_rec in
select ST_Line_SubString(st_linemerge(v_startLine), v_perStart,v_perEnd) as point,COALESCE(end_name,'無(wú)名路') as name,end_cost as cost loop
v_shPath:= ST_AsGeoJSON(v_rec.point);
cost:= v_rec.cost;
road_name:= v_rec.name;
return next;
end loop;
return;
end if;
--最短路徑
for v_rec in
(select ST_Line_SubString(st_linemerge(v_startLine),v_perStart,1) as point,COALESCE(first_name,'無(wú)名路') as name,first_cost as cost
union all
SELECT st_linemerge(b.geom) as point,COALESCE(b.name,'無(wú)名路') as name,b.length as cost
FROM pgr_dijkstra(
'SELECT gid as id, source, target, length as cost FROM china_road
where st_intersects(geom,st_buffer(st_linefromtext(''linestring('||startx||' ' || starty ||','|| endx ||' ' || endy ||')''),0.05))',
v_startTarget, v_endSource , false
) a, china_road b
WHERE a.edge = b.gid
union all
select ST_Line_SubString(st_linemerge(v_endLine),0,v_perEnd) as point,COALESCE(end_name,'無(wú)名路') as name,end_cost as cost)
loop
v_shPath:= ST_AsGeoJSON(v_rec.point);
cost:= v_rec.cost;
road_name:= v_rec.name;
return next;
end loop;
end;
$BODY$
LANGUAGE plpgsql VOLATILE STRICT;上面這種實(shí)現(xiàn)，是將所有查詢(xún)道路返回一個(gè)集合，然后客戶(hù)端來(lái)將各個(gè)線路進(jìn)行合并，這種方式對(duì)最終效率影響比較大，所以一般會(huì)在函數(shù)中將道路何合并為一條道路，我們可以使用postgis的st_union函數(shù)來(lái)處理，小編經(jīng)過(guò)長(zhǎng)時(shí)間的試驗(yàn)，在保證效率和準(zhǔn)確性的情況下，對(duì)上面的存儲(chǔ)過(guò)程做了很多優(yōu)化，最終得出了如下：
CREATE OR REPLACE FUNCTION public.pgr_shortest_road(
startx double precision,
starty double precision,
endx double precision,
endy double precision)
RETURNS geometry AS
$BODY$
declare
v_startLine geometry;--離起點(diǎn)最近的線
v_endLine geometry;--離終點(diǎn)最近的線
v_perStart float;--v_statpoint在v_res上的百分比
v_perEnd float;--v_endpoint在v_res上的百分比
v_shpath geometry;
distance double precision;
bufferInstance double precision;
bufferArray double precision[];
begin
execute 'select geom,
case china_road.direction
when ''3'' then
source
else
target
end
from china_road where
ST_DWithin(geom,ST_Geometryfromtext(''point('|| startx ||' ' || starty||')'',4326),0.05)
AND width::double precision >= '||roadWidth||'
order by ST_Distance(geom,ST_GeometryFromText(''point('|| startx ||' '|| starty ||')'',4326)) limit 1'
into v_startLine;
execute 'select geom,
case china_road.direction
when ''3'' then
target
else
source
end
from china_road
where ST_DWithin(geom,ST_Geometryfromtext(''point('|| endx || ' ' || endy ||')'',4326),0.05)
AND width::double precision >= '||roadWidth||'
order by ST_Distance(geom,ST_GeometryFromText(''point('|| endx ||' ' || endy ||')'',4326)) limit 1'
into v_endLine;
if (v_startLine is null) or (v_endLine is null) then
return null;
end if;
if (ST_equals(v_startLine,v_endLine)) then
select ST_LineLocatePoint(st_linemerge(v_startLine), ST_Geometryfromtext('point('|| startx ||' ' || starty ||')',4326)) into v_perStart;
select ST_LineLocatePoint(st_linemerge(v_endLine), ST_Geometryfromtext('point('|| endx ||' ' || endy ||')',4326)) into v_perEnd;
select ST_LineSubstring(st_linemerge(v_startLine),v_perStart,v_perEnd) into v_shPath;
return v_shPath;
end if;
select ST_DistanceSphere(st_geomfromtext('point('|| startx ||' ' || starty ||')',4326),st_geomfromtext('point('|| endx ||' ' || endy ||')',4326)) into distance;
if ((distance / 1000) > 50) then
bufferArray := ARRAY[0.1,0.2,0.3,0.5,0.8];
else
bufferArray := ARRAY[0.02,0.05,0.08,0.1];
end if;
forEACH bufferInstance IN ARRAY bufferArray
LOOP
select _pgr_shortest_road(startx,starty,endx,endy,bufferInstance) into v_shPath;
if (v_shPath is not null) then
return v_shPath;
end if;
end loop;
end;
$BODY$
LANGUAGE plpgsql VOLATILE STRICT
COST 100;
ALTER FUNCTION public.pgr_shortest_road(double precision, double precision, double precision, double precision )
OWNER TO postgres;
DROP FUNCTION public._pgr_shortest_road(double precision, double precision, double precision, double precision, double precision);上面的函數(shù)，其實(shí)對(duì)于大部分情況下的操作，基本可以滿(mǎn)足了。
三、效率優(yōu)化
其實(shí)在數(shù)據(jù)查詢(xún)方面，我們使用的是起點(diǎn)和終點(diǎn)之間的線性緩沖來(lái)提高效率，如下：
SELECT gid as id, source, target, cost,rev_cost as reverse_cost FROM china_road
where geom && st_buffer(st_linefromtext(''linestring('||startx||' ' || starty ||','|| endx ||' ' || endy ||')'',4326),'||bufferDistance||')當(dāng)然這在大部分情況下，依舊是不錯(cuò)的，然后在有些情況下，并不能起到很好的作用，因?yàn)槿绻瘘c(diǎn)和終點(diǎn)之間道路偏移較大（比如直線上的山脈較多的時(shí)候，路就會(huì)比較繞），這個(gè)時(shí)候，可能會(huì)增大緩沖距離，而增加緩沖距離就會(huì)導(dǎo)致，部分區(qū)域的查詢(xún)量增大，繼而影響效率，因此其實(shí)我們可以考慮使用mapid這個(gè)參數(shù)，這個(gè)參數(shù)從哪來(lái)呢，一般我們拿到的路網(wǎng)數(shù)據(jù)都會(huì)這個(gè)字段，我們只需要生成一個(gè)區(qū)域表，而這個(gè)區(qū)域表就倆個(gè)字段，一個(gè)是mapid，一個(gè)是這個(gè)mapid的polygon范圍，這樣子，上面的查詢(xún)條件，就可以換成如下：
SELECT gid as id, source, target, cost,rev_cost as reverse_cost FROM china_road
where mapid in (select mapid from maps where geom && st_buffer(st_linefromtext(''linestring('||startx||' ' || starty ||','|| endx ||' ' || endy ||')''),'||bufferDistance||'))這樣就可以在很大程度上提高效率。
四、數(shù)據(jù)bug處理
其實(shí)有時(shí)候我們拿到的路網(wǎng)數(shù)據(jù)，并不是非常的準(zhǔn)確，或者說(shuō)是錄入的有瑕疵，我自己遇到的就是生成的topo數(shù)據(jù)，本來(lái)一條路的target應(yīng)該和它相鄰路的source的點(diǎn)重合，然后實(shí)際卻是不一樣，這就導(dǎo)致最終規(guī)劃處的有問(wèn)題，因此，簡(jiǎn)單寫(xiě)了一個(gè)處理這種問(wèn)題的函數(shù)
CREATE OR REPLACE FUNCTION public.modity_road_data()
RETURNS void AS
$BODY$
declare
n integer;
begin
for n IN (select distinct(source) from china_road ) loop
update china_road
set geom = st_multi(st_addpoint(ST_geometryN(geom,1),
(select st_pointn(ST_geometryN(geom,1),1) from china_road where source = n
limit 1),
st_numpoints(ST_geometryN(geom,1))))
where target = n;
end loop;
end;
$BODY$
LANGUAGE plpgsql VOLATILE STRICT
COST 100;
ALTER FUNCTION public.modity_road_data()
OWNER TO postgres;
五、后續(xù)規(guī)劃
上面的函數(shù)已在百萬(wàn)數(shù)據(jù)中做過(guò)驗(yàn)證，后續(xù)還會(huì)驗(yàn)證千萬(wàn)級(jí)別的路網(wǎng)數(shù)據(jù)，當(dāng)然這種級(jí)別，肯定要在策略上做一些調(diào)整了，比如最近測(cè)試的全國(guó)路網(wǎng)中，先規(guī)劃起點(diǎn)至起點(diǎn)最近的高速入口，在規(guī)劃終點(diǎn)至終點(diǎn)最近的高速出口，然后再高速路網(wǎng)上規(guī)劃高速入口到高速出口的路徑，這樣發(fā)現(xiàn)效率提升不少，當(dāng)然，這里面還有很多邏輯和業(yè)務(wù)，等所有東西都驗(yàn)證完畢，會(huì)再出一版，千萬(wàn)級(jí)別路徑規(guī)劃的文章。
原文鏈接：https://www.cnblogs.com/share-gis/p/16148019.html
相關(guān)推薦
- 2022-07-07 Python實(shí)現(xiàn)8個(gè)概率分布公式的方法詳解_python
- 2022-06-12 C語(yǔ)言sizeof和strlen的指針和數(shù)組面試題詳解_C 語(yǔ)言
- 2022-02-26 Uncaught RangeError: Maximum call stack size excee
- 2022-10-11 主從同步中斷(sql_thread)問(wèn)題一例
- 2022-04-10 C#實(shí)現(xiàn)簡(jiǎn)單的計(jì)算器小功能_C#教程
- 2023-02-05 c++?梅森數(shù)源碼示例解析_C 語(yǔ)言
- 2022-09-07 Redis?sentinel哨兵集群的實(shí)現(xiàn)步驟_Redis
- 2022-04-18 python全面解析接口返回?cái)?shù)據(jù)_python
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細(xì)win安裝深度學(xué)習(xí)環(huán)境2025年最新版（
- Linux 中運(yùn)行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲(chǔ)小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運(yùn)算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認(rèn)證信息的處理
- Spring Security之認(rèn)證過(guò)濾器
- Spring Security概述快速入門(mén)
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯(cuò)誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實(shí)現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡(jiǎn)單動(dòng)態(tài)字符串（SD
- arthas操作spring被代理目標(biāo)對(duì)象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊(duì)列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠(yuǎn)程分支
提供CDN加速