others (#15) - pgrouting - ssd - performance (#292) - Message List

Hey Anton,

see the wrapper function below - hopefully it will answer you question. I have to apologize many important parameters are hard coded - i will change that soon.

CREATE OR REPLACE FUNCTION routing_smart_calc2(geometry, geometry)
  RETURNS SETOF geometry AS
	$BODY$
	DECLARE
		start_vertex_id INTEGER;
		end_vertex_id INTEGER;
		start_point ALIAS FOR $1;
		end_point ALIAS FOR $2;
		query TEXT;
		start_bbox TEXT;
		end_bbox TEXT;
		h_bbox	TEXT;
		tmp_rec RECORD;
		x_delta float;
		y_delta float;
		h_delta float;
			h_delta_x_adapted float;
			h_delta_y_adapted float;
			x_y_ratio float;
		X_1 float;
		x_2 float;
		y_1 float;
		y_2 float;
	BEGIN
		x_delta := 0.07;
		y_delta := 0.07;
		h_delta := 0.14;
		--> Find nearest edge for StartPoint
		SELECT INTO start_vertex_id * FROM (
					SELECT target FROM
					(SELECT target,source,the_geom,ST_Distance(ST_SetSRID(ST_AsText(start_point),4326),the_geom) as distance FROM route_table
						WHERE ST_DWithin(ST_SetSRID(ST_AsText(start_point),4326), the_geom, 0.04)
						ORDER BY distance  LIMIT 1) base)t;
		x_1 := ST_X(start_point);
		y_1 := ST_Y(start_point);
		--RAISE NOTICE '%',  start_vertex;
		--> Compute BBOX f. Start Vertex
		start_bbox := 'ST_SetSRID(''''BOX3D( ' || x_1 - x_delta || ' ' || y_1 - y_delta || ',' ||
					 x_1 + x_delta || ' ' || y_1 + y_delta ||')''''::box3d,4326)';
		--> Find near Vertex for EndPoint
		SELECT INTO end_vertex_id * FROM (
					SELECT target FROM
					(SELECT target,source,the_geom,ST_Distance(ST_SetSRID(ST_AsText(end_point),4326),the_geom) as distance FROM route_table
						WHERE ST_DWithin(ST_SetSRID(ST_AsText(end_point),4326), the_geom, 0.04)
						ORDER BY distance  LIMIT 1) base)t;
		x_2 := ST_X(end_point);
		y_2 := ST_Y(end_point);
		--RAISE NOTICE '%',  end_vertex;
		end_bbox := 'ST_SetSRID(''''BOX3D( ' || x_2 - x_delta || ' ' || y_2 - y_delta || ',' ||
					 x_2 + x_delta || ' ' || y_2 + y_delta ||')''''::box3d,4326)';
		/* Calculate BBOX for HighwayNetwork */
		IF x_1 > x_2 THEN /* Swap horizontal to provide in correct BBOX Format (LL/UR) */
			x_2 = ST_X(start_point);
			x_1 = ST_X(end_point);
		END IF;
		IF y_1 > y_2 THEN /* Swap vertical to provide in correct BBOX Format (LL/UR) */
			y_2= ST_Y(start_point);
			y_1= ST_Y(end_point);
		END IF;
		/* Adapt BBOX depending on the x-Width, y-Width ratio */
		--RAISE NOTICE '% % % %', x_1,y_1,x_2,y_2;
		x_y_ratio = (x_1-x_2)/(y_1-y_2);
		h_delta_x_adapted := h_delta;
		h_delta_y_adapted := h_delta;
		if x_y_ratio <= 1.0 THEN
		 h_delta_x_adapted  = h_delta * (1-((x_1-x_2)/(y_1-y_2)));
		ELSE
		 h_delta_y_adapted  := h_delta * (1-((y_1-y_2)/(x_1-x_2)));
		END IF;
		--RAISE NOTICE 'X: %, Y: %', h_delta_x_adapted,h_delta_y_adapted;
		h_bbox	:= 'ST_SetSRID(''''BOX3D( ' || x_1 - h_delta_x_adapted  || ' ' || y_1 - h_delta_y_adapted  || ',' ||
					 x_2 + h_delta_x_adapted || ' ' || y_2 + h_delta_y_adapted  ||')''''::box3d,4326)';
		--RAISE NOTICE '%', start_bbox;
		--RAISE NOTICE '%', end_bbox;
		--RAISE NOTICE '%', h_bbox;
		query := 'SELECT * FROM shortest_path_astar ' ||
				'(''SELECT gid as id,source,target,to_cost as cost,reverse_cost,x1,x2,y1,y2 FROM route_table ' ||
				'WHERE (class_id < 108 AND the_geom && ' || h_bbox || ') OR (the_geom && ' || start_bbox || ')OR(the_geom && '|| end_bbox ||')'',' ||
				 start_vertex_id || ' , ' || end_vertex_id || ', true,true),route_table WHERE edge_id = gid;';
		--RAISE NOTICE '%',query;
		FOR tmp_rec IN EXECUTE query
		LOOP
		RETURN NEXT tmp_rec.the_geom;
		END LOOP;
	END;
	$BODY$
  LANGUAGE 'plpgsql' VOLATILE STRICT
  COST 100
  ROWS 100;
ALTER FUNCTION routing_smart_calc2(geometry, geometry) OWNER TO postgres;

Just some words to the code. The first two queries are really stupid - the select always the target node of the closest edge. (of course i will improve that)

		SELECT INTO end_vertex_id * FROM (
					SELECT target FROM
					(SELECT target,source,the_geom,ST_Distance(ST_SetSRID(ST_AsText(end_point),4326),the_geom) as distance FROM route_table
						WHERE ST_DWithin(ST_SetSRID(ST_AsText(end_point),4326), the_geom, 0.04)
						ORDER BY distance  LIMIT 1) base)t;

In the next step the bounding box for the start and end node are computed by applying a fixed buffer (x_delta,y_delta). Changing this number has a great impact on performance and the possibility that a route can be found.

end_bbox := 'ST_SetSRID(''''BOX3D( ' || x_2 - x_delta || ' ' || y_2 - y_delta || ',' ||
					 x_2 + x_delta || ' ' || y_2 + y_delta ||')''''::box3d,4326)';

Next the bbox for the line connecting the start and endnode is computed by applying a buffer, but before some minor intelligence is needed: if the end and start have either the same or close lat or lon values (in other words both points lie either on a horizontal or vertical line) the bbox usually gets to thin. So i implemented a small function (just the ratio of the differences between the start and endpoint) to adapt the bbox

		x_y_ratio = (x_1-x_2)/(y_1-y_2);
		h_delta_x_adapted := h_delta;
		h_delta_y_adapted := h_delta;
		if x_y_ratio <= 1.0 THEN
		 h_delta_x_adapted  = h_delta * (1-((x_1-x_2)/(y_1-y_2)));
		ELSE
		 h_delta_y_adapted  := h_delta * (1-((y_1-y_2)/(x_1-x_2)));
		END IF;

After all three bounding boxes have been successfully computed, they are used to generate the query:

		query := 'SELECT * FROM shortest_path_astar ' ||
				'(''SELECT gid as id,source,target,to_cost as cost,reverse_cost,x1,x2,y1,y2 FROM route_table ' ||
				'WHERE (class_id < 108 AND the_geom && ' || h_bbox || ') OR (the_geom && ' || start_bbox || ')OR(the_geom && '|| end_bbox ||')'',' ||
				 start_vertex_id || ' , ' || end_vertex_id || ', true,true),route_table WHERE edge_id = gid;'

Most important is the WHERE - Clause in the Select Statement for the shortest_path_astar function. It consists out of three elements:

'WHERE (class_id < 108 AND the_geom && ' || h_bbox || ') OR (the_geom && ' || start_bbox || ')OR(the_geom && '|| end_bbox ||')'

The first part selects all roads with small class_ids (in my case this are highways, trunks, primary) which are inside the large h_bbox bounding box

(class_id < 108 AND the_geom && ' || h_bbox || ')

The second and third element select the edges which are around the computed bounding box for the start and end node

(the_geom && '|| end_bbox ||')

Anton, I think you will be disappointed because this function is really stupid - but it worked for me very well. Of course there is a lot of room for improvements, i've already got a lot of ideas. I will report more soon.