root/trunk/core/sql/matching.sql

Revision 248, 14.7 KB (checked in by anton, 2 years ago)

Matching functions added
Line 
1CREATE TYPE link_point AS (id integer, name varchar);
2
3-------------------------------------------------------------------
4-- This function finds nearest link to a given node
5-- point - text representation of point
6-- distance - function will search for a link within this distance
7-- tbl - table name
8-------------------------------------------------------------------
9CREATE OR REPLACE FUNCTION find_nearest_link_within_distance(point varchar,
10        distance double precision, tbl varchar)
11        RETURNS INT AS
12$$
13DECLARE
14    row record;
15    x float8;
16    y float8;
17   
18    srid integer;
19   
20BEGIN
21
22    FOR row IN EXECUTE 'select getsrid(the_geom) as srid from '||tbl||' where gid = (select min(gid) from '||tbl||')' LOOP
23    END LOOP;
24        srid:= row.srid;
25   
26    -- Getting x and y of the point
27   
28    FOR row in EXECUTE 'select x(GeometryFromText('''||point||''', '||srid||')) as x' LOOP
29    END LOOP;
30        x:=row.x;
31
32    FOR row in EXECUTE 'select y(GeometryFromText('''||point||''', '||srid||')) as y' LOOP
33    END LOOP;
34        y:=row.y;
35
36    -- Searching for a link within the distance
37
38    FOR row in EXECUTE 'select gid, distance(the_geom, GeometryFromText('''||point||''', '||srid||')) as dist from '||tbl||
39                            ' where setsrid(''BOX3D('||x-distance||' '||y-distance||', '||x+distance||' '||y+distance||')''::BOX3D, '||srid||')&&the_geom order by dist asc limit 1'
40    LOOP
41    END LOOP;
42
43    IF row.gid IS NULL THEN
44            --RAISE EXCEPTION 'Data cannot be matched';
45            RETURN NULL;
46    END IF;
47
48    RETURN row.gid;
49
50END;
51$$
52LANGUAGE 'plpgsql' VOLATILE STRICT;
53
54-------------------------------------------------------------------
55-- This function finds nearest node to a given node
56-- point - text representation of point
57-- distance - function will search for a link within this distance
58-- tbl - table name
59-------------------------------------------------------------------
60
61CREATE OR REPLACE FUNCTION find_nearest_node_within_distance(point varchar,
62        distance double precision, tbl varchar)
63        RETURNS INT AS
64$$
65DECLARE
66    row record;
67    x float8;
68    y float8;
69    d1 double precision;
70    d2 double precision;
71    d  double precision;
72    field varchar;
73
74    node integer;
75    source integer;
76    target integer;
77   
78    srid integer;
79   
80BEGIN
81
82    FOR row IN EXECUTE 'select getsrid(the_geom) as srid from '||tbl||' where gid = (select min(gid) from '||tbl||')' LOOP
83    END LOOP;
84        srid:= row.srid;
85
86    -- Getting x and y of the point
87
88    FOR row in EXECUTE 'select x(GeometryFromText('''||point||''', '||srid||')) as x' LOOP
89    END LOOP;
90        x:=row.x;
91
92    FOR row in EXECUTE 'select y(GeometryFromText('''||point||''', '||srid||')) as y' LOOP
93    END LOOP;
94        y:=row.y;
95
96    -- Getting nearest source
97
98    FOR row in EXECUTE 'select source, distance(StartPoint(the_geom), GeometryFromText('''||point||''', '||srid||')) as dist from '||tbl||
99                            ' where setsrid(''BOX3D('||x-distance||' '||y-distance||', '||x+distance||' '||y+distance||')''::BOX3D, '||srid||')&&the_geom order by dist asc limit 1'
100    LOOP
101    END LOOP;
102   
103    d1:=row.dist;
104    source:=row.source;
105
106    -- Getting nearest target
107
108    FOR row in EXECUTE 'select target, distance(EndPoint(the_geom), GeometryFromText('''||point||''', '||srid||')) as dist from '||tbl||
109                            ' where setsrid(''BOX3D('||x-distance||' '||y-distance||', '||x+distance||' '||y+distance||')''::BOX3D, '||srid||')&&the_geom order by dist asc limit 1'
110    LOOP
111    END LOOP;
112
113    -- Checking what is nearer - source or target
114   
115    d2:=row.dist;
116    target:=row.target;
117    IF d1<d2 THEN
118        node:=source;
119        d:=d1;
120    ELSE
121        node:=target;
122        d:=d2;
123    END IF;
124
125    IF d=NULL OR d>distance THEN
126        node:=NULL;
127    END IF;
128
129    RETURN node;
130
131END;
132$$
133LANGUAGE 'plpgsql' VOLATILE STRICT;
134
135-------------------------------------------------------------------
136-- This function finds nearest node as a source or target of the
137-- nearest link
138-- point - text representation of point
139-- distance - function will search for a link within this distance
140-- tbl - table name
141-------------------------------------------------------------------
142
143CREATE OR REPLACE FUNCTION find_node_by_nearest_link_within_distance(point varchar,
144        distance double precision, tbl varchar)
145        RETURNS link_point AS
146$$
147DECLARE
148    row record;
149    link integer;
150    d1 double precision;
151    d2 double precision;
152    field varchar;
153    res link_point;
154   
155    srid integer;
156BEGIN
157
158    FOR row IN EXECUTE 'select getsrid(the_geom) as srid from '||tbl||' where gid = (select min(gid) from '||tbl||')' LOOP
159    END LOOP;
160        srid:= row.srid;
161
162
163    -- Searching for a nearest link
164   
165    FOR row in EXECUTE 'select id from find_nearest_link_within_distance('''||point||''', '||distance||', '''||tbl||''') as id'
166    LOOP
167    END LOOP;
168    IF row.id is null THEN
169        res.id = -1;
170        RETURN res;
171    END IF;
172    link:=row.id;
173
174    -- Check what is nearer - source or target
175   
176    FOR row in EXECUTE 'select distance((select StartPoint(the_geom) from '||tbl||' where gid='||link||'), GeometryFromText('''||point||''', '||srid||')) as dist'
177    LOOP
178    END LOOP;
179    d1:=row.dist;
180
181    FOR row in EXECUTE 'select distance((select EndPoint(the_geom) from '||tbl||' where gid='||link||'), GeometryFromText('''||point||''', '||srid||')) as dist'
182    LOOP
183    END LOOP;
184    d2:=row.dist;
185
186    IF d1<d2 THEN
187        field:='source';
188    ELSE
189        field:='target';
190    END IF;
191   
192    FOR row in EXECUTE 'select '||field||' as id, '''||field||''' as f from '||tbl||' where gid='||link
193    LOOP
194    END LOOP;
195       
196    res.id:=row.id;
197    res.name:=row.f;
198   
199    RETURN res;
200
201
202END;
203$$
204LANGUAGE 'plpgsql' VOLATILE STRICT;
205
206-------------------------------------------------------------------
207-- This function matches given line to the existing network.
208-- Returns set of edges as geometry.
209-- tbl - table name
210-- line - line to match
211-- distance - distance for nearest node search
212-- distance2 - distance for shortest path search
213-- dir - true if your network graph is directed
214-- rc - true if you have a reverse_cost column
215-------------------------------------------------------------------
216
217CREATE OR REPLACE FUNCTION match_line_as_geometry(tbl varchar, line geometry, distance double precision,
218                                                distance2 double precision, dir boolean, rc boolean)
219        RETURNS SETOF GEOMS AS
220$$
221DECLARE
222    row record;
223    num integer;
224    i integer;
225    geom geoms;
226    points integer[];
227   
228    srid integer;
229   
230    query text;
231   
232BEGIN
233
234    FOR row IN EXECUTE 'select getsrid(the_geom) as srid from '||tbl||' where gid = (select min(gid) from '||tbl||')' LOOP
235    END LOOP;
236        srid:= row.srid;
237
238
239    FOR row IN EXECUTE 'select geometryType(GeometryFromText('''||astext(line)||''', '||srid||')) as type' LOOP
240    END LOOP;
241   
242    IF row.type <> 'LINESTRING' THEN
243        RAISE EXCEPTION 'Geometry should be a linestring.';
244    END IF;
245   
246    -- Searching through all points in given line
247   
248    num:=NumPoints(line);
249    i:= 0;
250   
251    LOOP
252        i:=i+1;
253
254        -- Getting nearest node to the current point
255       
256        FOR row in EXECUTE 'select * from find_nearest_node_within_distance(''POINT('
257                            ||x(PointN(line, i))||' '||y(PointN(line, i))||')'','||distance||', '''||tbl||''') as id'
258        LOOP
259        END LOOP;
260       
261        IF row.id IS NOT NULL THEN
262            points[i-1]:=row.id;
263
264        ELSE
265       
266            -- If there is no nearest node within given distance, let's try another algorithm
267       
268            FOR row in EXECUTE 'select * from find_node_by_nearest_link_within_distance(''POINT('
269                                ||x(PointN(line, i))||' '||y(PointN(line, i))||')'','||distance2||', '''||tbl||''') as id'
270            LOOP
271            END LOOP;
272
273            points[i-1]:=row.id;
274
275        END IF;
276
277        IF i>1 AND points[i-2] <> points[i-1] THEN
278       
279            -- We could find existing edge, so let's construct the main query now
280       
281            query := 'select gid, the_geom FROM shortest_path( ''select gid as id, source::integer,'||
282                                ' target::integer, length::double precision as cost,x1,x2,y1,y2';
283                               
284            IF rc THEN query := query || ', reverse_cost';
285            END IF;                             
286                               
287            query := query || ' from '||quote_ident(tbl)||' where setsrid(''''BOX3D('||x(PointN(line, i-1))-distance2*2||' '
288                                ||y(PointN(line, i-1))-distance2*2||', '||x(PointN(line, i))+distance2*2||' '
289                                ||y(PointN(line, i))+distance2*2||')''''::BOX3D, '||srid||')&&the_geom'', '
290                                || points[i-1] ||', '|| points[i-2] ||', '''||dir||''', '''||rc||'''), '
291                                ||quote_ident(tbl)||' where edge_id=gid';
292            FOR row IN EXECUTE query
293            LOOP
294
295                geom.gid := row.gid;
296                geom.the_geom := row.the_geom;
297               
298                RETURN NEXT geom;
299               
300            END LOOP;
301
302        END IF;                                                                                                                 
303
304
305        EXIT WHEN i=num;
306       
307       
308    END LOOP;   
309   
310    RETURN;
311
312END;
313$$
314
315LANGUAGE 'plpgsql' VOLATILE STRICT;
316
317-------------------------------------------------------------------
318-- This function matches given line to the existing network.
319-- Returns set of edges.
320-- tbl - table name
321-- line - line to match
322-- distance - distance for nearest node search
323-- distance2 - distance for shortest path search
324-- dir - true if your network graph is directed
325-- rc - true if you have a reverse_cost column
326-------------------------------------------------------------------
327
328CREATE OR REPLACE FUNCTION match_line(tbl varchar, line geometry, distance double precision,
329                                                distance2 double precision, dir boolean, rc boolean)
330        RETURNS SETOF PATH_RESULT AS
331$$
332DECLARE
333    row record;
334    num integer;
335   
336    i integer;
337    z integer;
338    t integer;
339   
340    prev integer;
341   
342    query text;
343   
344    path path_result;
345   
346    edges integer[];
347    vertices integer[];
348    costs double precision[];
349   
350    srid integer;
351   
352    points integer[];
353
354BEGIN
355
356    FOR row IN EXECUTE 'select getsrid(the_geom) as srid from '||tbl||' where gid = (select min(gid) from '||tbl||')' LOOP
357    END LOOP;
358        srid:= row.srid;
359
360    FOR row IN EXECUTE 'select geometryType(GeometryFromText('''||astext(line)||''', '||srid||')) as type' LOOP
361    END LOOP;
362   
363    IF row.type <> 'LINESTRING' THEN
364        RAISE EXCEPTION 'Geometry should be a linestring.';
365    END IF;
366
367    num:=NumPoints(line);
368    i:= 0;
369    z:= 0;
370    prev := -1;
371       
372    -- Searching through all points in given line
373
374    LOOP
375        i:=i+1;
376
377        -- Getting nearest node to the current point
378
379        FOR row in EXECUTE 'select * from find_nearest_node_within_distance(''POINT('
380                            ||x(PointN(line, i))||' '||y(PointN(line, i))||')'','||distance||', '''||tbl||''') as id'
381        LOOP
382        END LOOP;
383       
384
385        IF row.id IS NOT NULL THEN
386            points[i-1]:=row.id;
387
388        ELSE
389
390            -- If there is no nearest node within given distance, let's try another algorithm
391
392            FOR row in EXECUTE 'select * from find_node_by_nearest_link_within_distance(''POINT('
393                                ||x(PointN(line, i))||' '||y(PointN(line, i))||')'','||distance2||', '''||tbl||''') as id'
394            LOOP
395            END LOOP;
396
397            points[i-1]:=row.id;
398            IF row.id = -1 THEN
399                return;
400            END IF;
401
402        END IF;
403
404        IF i>1 AND points[i-2] <> points[i-1] THEN
405       
406            -- We could find existing edge, so let's construct the main query now
407
408            query := 'select edge_id, vertex_id, cost FROM shortest_path( ''select gid as id, source::integer,'||
409                                ' target::integer, length::double precision as cost,x1,x2,y1,y2 ';
410                               
411            IF rc THEN query := query || ', reverse_cost';
412            END IF;
413           
414            query := query || ' from '||quote_ident(tbl)||' where setsrid(''''BOX3D('||x(PointN(line, i-1))-distance2*2||' '
415                                ||y(PointN(line, i-1))-distance2*2||', '||x(PointN(line, i))+distance2*2||' '
416                                ||y(PointN(line, i))+distance2*2||')''''::BOX3D, '||srid||')&&the_geom'', '
417                                || points[i-1] ||', '|| points[i-2] ||', '''||dir||''', '''||rc||''')';
418
419           
420            BEGIN
421           
422            FOR row IN EXECUTE query
423            LOOP
424           
425           
426                IF row IS NULL THEN
427                    RAISE NOTICE 'Cannot find a path between % and %', points[i-1], points[i-2];
428                    RETURN;
429                END IF;
430
431                edges[z] := row.edge_id;
432                vertices[z] := row.vertex_id;
433                costs[z] := row.cost;
434               
435                IF edges[z] = -1 THEN
436               
437                    t := 0;
438                   
439                    -- Ordering edges
440                   
441                    FOR t IN (prev+1)..z-1 LOOP
442                   
443                        path.edge_id := edges[t];
444                        path.vertex_id := vertices[t];
445                        path.cost = costs[t];
446                       
447                        edges[t] := edges[z-t+prev+1];
448                        vertices[t] := vertices[z-t+prev+1];
449                        costs[t] := costs[z-t+prev+1];
450
451                        edges[z-t+prev+1] := path.edge_id;
452                        vertices[z-t+prev+1] := path.vertex_id;
453                        costs[z-t+prev+1] := path.cost;
454                       
455                                           
456                    END LOOP;
457                   
458                    prev := z;
459
460                END IF;
461               
462                z := z+1;
463               
464            END LOOP;
465           
466            EXCEPTION
467                WHEN containing_sql_not_permitted THEN RETURN;
468           
469            END;
470
471        END IF;                                                                                                                 
472
473        EXIT WHEN i=num;
474       
475    END LOOP;   
476
477    FOR t IN 0..array_upper(edges, 1) LOOP
478   
479        IF edges[array_upper(edges, 1)-t] > 0 OR (edges[array_upper(edges, 1)-t] < 0 AND t = array_upper(edges, 1)) THEN
480        path.edge_id := edges[array_upper(edges, 1)-t];
481        path.vertex_id := vertices[array_upper(edges, 1)-t];
482        path.cost = costs[array_upper(edges, 1)-t];
483        RETURN NEXT path;       
484        END IF;
485    END LOOP;
486   
487    RETURN;
488
489END;
490$$
491
492LANGUAGE 'plpgsql' VOLATILE STRICT;
493
494-------------------------------------------------------------------
495-- This function matches given line to the existing network.
496-- Returns single (multi)linestring.
497-- tbl - table name
498-- line - line to match
499-- distance - distance for nearest node search
500-- distance2 - distance for shortest path search
501-- dir - true if your network graph is directed
502-- rc - true if you have a reverse_cost column
503-------------------------------------------------------------------
504
505CREATE OR REPLACE FUNCTION match_line_as_linestring(tbl varchar, line geometry, distance double precision,
506                                                distance2 double precision, dir boolean, rc boolean)
507        RETURNS GEOMETRY AS
508$$
509DECLARE
510    row record;
511   
512    i integer;
513   
514    edges integer[];
515   
516    srid integer;
517   
518BEGIN
519
520    FOR row IN EXECUTE 'select getsrid(the_geom) as srid from '||tbl||' where gid = (select min(gid) from '||tbl||')' LOOP
521    END LOOP;
522        srid:= row.srid;
523
524    FOR row IN EXECUTE 'select geometryType(GeometryFromText('''||astext(line)||''', '||srid||')) as type' LOOP
525    END LOOP;
526   
527    IF row.type <> 'LINESTRING' THEN
528        RAISE EXCEPTION 'Geometry should be a linestring.';
529    END IF;
530
531    i := 0;
532   
533    FOR row IN EXECUTE 'select * from match_line('''||quote_ident(tbl)||''', GeometryFromText('''||astext(line)||''', '||srid||'), '
534                            ||distance||', '||distance2||', '''||dir||''', '''||rc||''')' LOOP
535        edges[i] := row.edge_id;
536        i := i + 1;
537    END LOOP;
538    IF i = 0 THEN
539        return NULL;
540    END IF;
541
542    -- Attempt to create a single linestring. It may return multilinestring as well.
543
544    FOR row IN EXECUTE 'select linemerge(geomunion(multi(the_geom))) as the_geom from '||tbl||' where gid in ('||array_to_string(edges, ', ')||') and gid > 0' LOOP
545    END LOOP;
546   
547    IF isvalid(row.the_geom) THEN
548        RETURN row.the_geom;
549    ELSE
550        RAISE EXCEPTION 'The result is not a valid geometry.';
551    END IF;
552
553END;
554$$
555
556LANGUAGE 'plpgsql' VOLATILE STRICT;
Note: See TracBrowser for help on using the browser.