#
root/trunk/core/sql/matching.sql

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

Line | |
---|---|

1 | CREATE 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 | ------------------------------------------------------------------- |

9 | CREATE OR REPLACE FUNCTION find_nearest_link_within_distance(point varchar, |

10 | distance double precision, tbl varchar) |

11 | RETURNS INT AS |

12 | $$ |

13 | DECLARE |

14 | row record; |

15 | x float8; |

16 | y float8; |

17 | |

18 | srid integer; |

19 | |

20 | BEGIN |

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

50 | END; |

51 | $$ |

52 | LANGUAGE '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 | |

61 | CREATE OR REPLACE FUNCTION find_nearest_node_within_distance(point varchar, |

62 | distance double precision, tbl varchar) |

63 | RETURNS INT AS |

64 | $$ |

65 | DECLARE |

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

80 | BEGIN |

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

131 | END; |

132 | $$ |

133 | LANGUAGE '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 | |

143 | CREATE OR REPLACE FUNCTION find_node_by_nearest_link_within_distance(point varchar, |

144 | distance double precision, tbl varchar) |

145 | RETURNS link_point AS |

146 | $$ |

147 | DECLARE |

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; |

156 | BEGIN |

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

202 | END; |

203 | $$ |

204 | LANGUAGE '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 | |

217 | CREATE 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 | $$ |

221 | DECLARE |

222 | row record; |

223 | num integer; |

224 | i integer; |

225 | geom geoms; |

226 | points integer[]; |

227 | |

228 | srid integer; |

229 | |

230 | query text; |

231 | |

232 | BEGIN |

233 | |

234 | |

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

312 | END; |

313 | $$ |

314 | |

315 | LANGUAGE '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 | |

328 | CREATE 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 | $$ |

332 | DECLARE |

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

354 | BEGIN |

355 | |

356 | |

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

489 | END; |

490 | $$ |

491 | |

492 | LANGUAGE '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 | |

505 | CREATE 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 | $$ |

509 | DECLARE |

510 | row record; |

511 | |

512 | i integer; |

513 | |

514 | edges integer[]; |

515 | |

516 | srid integer; |

517 | |

518 | BEGIN |

519 | |

520 | |

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

553 | END; |

554 | $$ |

555 | |

556 | LANGUAGE 'plpgsql' VOLATILE STRICT; |

**Note:**See TracBrowser for help on using the browser.