Python wechat ordering applet course video

https://blog.csdn.net/m0_56069948/article/details/122285951

Python actual combat quantitative transaction financial management system

https://blog.csdn.net/m0_56069948/article/details/122285941
For GIS business, path planning is A very basic business. Generally, if companies deal with it, they will directly choose to call the mature third-party interfaces, such as Gaode, Baidu, etc. Of course, there are many path planning algorithms, such as the famous Dijkstra and A * algorithms. Of course, this article does not introduce the algorithm. The author will deal with the shortest path according to the Dijkstra algorithm integrated by pgrouting and combined with the postgresql database.

1, Data processing

The core of path planning is data, which is the general road network data. However, after we get the road network data, we need to process the data. Because the idea of the algorithm is based on the principle of directed graph, we first need to topo the data. Through topo, we actually establish the vertex relationship of each road in the road network. The following are the main commands:

--Open the executive road network topo Plug in for
create extension postgis;
create extension postgis\_topology;
--Data creation topology
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');

Where test_road is the table name that imports road network data into postgresql.

After processing topo, it's basically enough. We can use pgrouting's own functions. In fact, there are many. We choose 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;

From the function input parameters, we can see that we need a query sql, a starting point, an ending point, and whether to consider the direction. Well, after knowing the input parameters of the calling function, we'll write this function.

2, Principle analysis

In general, path planning is basically to input a starting point and an ending point, and then directly plan. For us, if we want to apply the above functions, we must find out the starting point target and the source of the ending point, and then plan to call the above functions to return the results we need according to the two topo points found.

How to find the corresponding target according to the starting point? In fact, it is to find the target of the nearest line from the starting point. Similarly, the source of the ending point is to find the source of the nearest line from the ending point. Of course, after planning these two points, it is basically OK, but finally, it is necessary to connect the target closest to the starting point and the source closest to the ending point. In this way, the whole path planning is completed.

Let's look at the specific implementation stored procedure:

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;--The line closest to the starting point 
v\_endLine geometry;--The line closest to the end point 
v\_startTarget integer;--The end of the line closest to the starting point 
v\_endSource integer;--Starting point of the line closest to the end point 
v\_statpoint geometry;--stay v\_startLine The point on the that is closest to the starting point 
v\_endpoint geometry;--stay v\_endLine The point on the that is closest to the end point 
v\_res geometry;--Shortest path analysis results 
v\_perStart float;--v\_statpoint stay v\_res Percentage on 
v\_perEnd float;--v\_endpoint stay v\_res Percentage on 
v\_rec record; 
first\_name varchar;
end\_name varchar;
first\_cost double precision;
end\_cost double precision;
begin 
--Query the line closest to the starting point 
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; 
--Query the line closest to the end point 
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; 
--If the nearest line is not found, return 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; 

--Calculates the position of the point on the line closest to the starting point in the line
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,'Nameless Road') 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;
--Shortest path 
for v\_rec in 
(select ST\_Line\_SubString(st\_linemerge(v\_startLine),v\_perStart,1) as point,COALESCE(first\_name,'Nameless Road') as name,first\_cost as cost
union all
SELECT st\_linemerge(b.geom) as point,COALESCE(b.name,'Nameless Road') 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,'Nameless Road') 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;

The above implementation is to return all query roads to a set, and then the client will merge all lines. This method has a great impact on the final efficiency, so we generally merge the roads into one road in the function. We can use the st of postgis_ After a long time of experiments, the Xiaobian optimized the above stored procedures under the condition of ensuring efficiency and accuracy, and finally came to the following conclusions:

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;--The line closest to the starting point 
 v\_endLine geometry;--The line closest to the end point 
 v\_perStart float;--v\_statpoint stay v\_res Percentage on 
 v\_perEnd float;--v\_endpoint stay v\_res Percentage on 
 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);

In fact, the above functions can basically meet the operation in most cases.

3, Efficiency optimization

In fact, in terms of data query, we use the linear buffer between the starting point and the end point to improve the efficiency, as follows:

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||')

Of course, this is still good in most cases, and in some cases, it does not play a good role, because if the road offset between the starting point and the end point is large (for example, when there are many mountains on the straight line, the road will be more winding), at this time, the buffer distance may be increased, and increasing the buffer distance will increase the query volume in some areas, which will affect the efficiency, Therefore, in fact, we can consider using the parameter mapid. Where does this parameter come from? Generally, the road network data we get will use this field. We only need to generate an area table, and this area table has two fields, one is mapid and the other is the polygon range of mapid. In this way, the above query conditions can be changed into the following:

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||'))

This can greatly improve efficiency.

4, Data bug handling

In fact, sometimes the road network data we get is not very accurate, or the input is flawed. What I encounter is the generated topo data. Originally, the target of a road should coincide with the source point of its adjacent road, but it is actually different, which leads to problems in the final planning. Therefore, I simply wrote a function to deal with this problem

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;

5, Follow up planning

The above functions have been verified in millions of data, and tens of millions of levels of road network data will be verified later. Of course, this level must be adjusted in strategy. For example, in the recently tested national road network, first plan the expressway entrance from the starting point to the nearest starting point, plan the expressway exit from the ending point to the nearest ending point, and then plan the route from the expressway entrance to the expressway exit on the expressway network. In this way, it is found that the efficiency is improved a lot, Of course, there are a lot of logic and business here. When everything is verified, another version of the article on tens of millions of level path planning will be published.