<div dir="ltr">Hi Stephen,<div><br></div><div style>About finding a route from a point close to the network that is not one of the nodes, here is how we are doing it.</div><div style>I don't think it is the most "clean" way of proceeding, because we did it when we started using PostGIS for the first time, so we were complete beginners. This procedure splits the closest way on the network to the starting point from which you want your route at the orthogonal projection of this starting point to the closest way.</div>
<div style>The programming language is Ruby, but I think you will understand it easily and adapt it to your programming language.</div><div style><br></div><div style>1. Construct Point: route starting point</div><div> -> start_pt = "ST_GeometryFromText('POINT(#{point.lon} #{point.lat})', 4326)"</div>
<div><br></div><div><div>2. Find closest road on the network to the starting point</div><div> closest_road = Map.connection.execute("WITH index_query AS (</div><div> SELECT ST_Distance(geom_way, #{start_pt}) AS distance, id, geom_way, x1, y1, x2, y2, source, target FROM #{self.table_name} ORDER BY geom_way <#> #{start_pt} limit 10) </div>
<div> SELECT id, ST_AsText(geom_way), x1, y1, x2, y2, source, target FROM index_query ORDER BY distance LIMIT 1")</div></div><div> closest_road_geom = "ST_GeometryFromText('#{closest_road.getvalue(0,1)}', 4326)"<br>
</div><div><br></div><div><div>3. Find closest point lying on closest way from starting point</div><div> closest_pt_on_closest_way = Map.connection.execute("SELECT ST_AsText(ST_ClosestPoint(#{closest_road_geom}, #{start_pt})) AS point;").getvalue(0,0) </div>
<div> closest_pt = "ST_GeometryFromText('#{closest_pt_on_closest_road}', 4326)"</div></div><div><div><br></div><div>4. Get points of the closest way to the starting point</div><div> points = Map.connection.execute("SELECT ST_AsText((point.gdump).geom) FROM (SELECT ST_DumpPoints(#{closest_road_geom}) AS gdump) AS point;").column_values(0)</div>
</div><div><br></div><div><div>5. Iterate through all the points of the closest way to find what 2 points of the closest way the orthogonal projection of the starting points is in between</div><div> points2 = points[1..-1]</div>
<div> index = 0</div><div><br></div><div> # Would be much better if we could calculate it directly here, not accessing the DB, but it is not an easy calculation...could not manage to find the correct formulas</div>
<div> points2.each_with_index do |pt2_raw, idx|</div><div> # Get distance</div><div> pt1 = "ST_GeometryFromText('#{points[idx]}', 4326)"</div><div> pt2 = "ST_GeometryFromText('#{points2[idx]}', 4326)"</div>
<div><br></div><div> dist = Map.connection.execute("SELECT ST_Distance(#{closest_pt},(SELECT ST_MakeLine(#{pt1}, #{pt2})));").getvalue(0,0)</div><div> if dist.to_f < 0.0000000001</div><div> index = idx</div>
<div> break</div><div> end</div><div> end</div></div><div><br></div><div style>6. Now we can split the road into 2</div><div style><div> # Split the road into 2</div><div> road1 = ""</div>
<div> points[0..index].each_with_index do |pt, idx|</div><div> if idx == 0</div><div> road1 = "ST_GeometryFromText('#{pt}', 4326)"</div><div> else</div><div> road1 = "#{road1}, ST_GeometryFromText('#{pt}', 4326)"</div>
<div> end</div><div> end</div><div> road1 = "#{road1}, #{closest_pt}"</div><div><br></div><div> road2 = closest_pt</div><div> points[index+1..-1].each do |pt|</div><div> road2 = "#{road2}, ST_GeometryFromText('#{pt}', 4326)"</div>
<div> end</div><div><br></div><div style>7. Finally, you have to insert "road1" and "road2" into your database, so that pgrouting uses them when finding the route (no need to delete the original way), and delete them when the routing calculations are over. Something like:</div>
<div style> # buffer variables</div><div> geom_buf = "road1 AS (SELECT ST_MakeLine(ARRAY[#{road}]) AS geom)"</div><div><div> # Insert road into network table</div><div> insert = Map.connection.execute("WITH #{geom_buf}, #{length} INSERT INTO #{self.table_name} VALUES (#{id_r1},0,0,0,0,#{clazz},1,#{source},#{target},#{km},1,#{cost},#{cost},#{x1},#{y1},#{x2},#{y2},#{geom_r1},#{cost_car});")</div>
</div><div><br></div><div style>Tao</div></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/4/13 Stephen V. Mather <span dir="ltr"><<a href="mailto:svm@clevelandmetroparks.com" target="_blank">svm@clevelandmetroparks.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div>
<div style="direction:ltr;font-size:10pt;font-family:Tahoma">Hi All,<br>
<br>
I'm curious about efficiency of A* vs Dijkstra in large networks. If A* tends to follow the straight line nodes until/unless it finds an obstacle, for really large networks, under what conditions is A* a better choice than Dijkstra?<br>
<br>
Also, regarding A* implementation, is it strict, or is there any way to relax the admissibility criterion as currently implemented?<br>
<br>
Finally, in using pgRouting for turn by turn, we have pre-chopped our network into short segments to ensure the nearest search node is close to the point we are searching so the directions start from a nearby point, not the nearest network intersection.<br>
<br>
For datasets as large as the one we are working with, this seems to result in a pretty high random IO tax. I wondered if anyone has some boilerplate modifying the returned route, slicing the nearest ways to the beginning and end points with ST_ClosestPoint
or similar?<br>
<br>
Thanks,<br>
Best,<br>
Steve<br>
<br>
<div><br>
<div style="font-family:Tahoma;font-size:13px">
<div style="font-family:Tahoma;font-size:13px">
<div>
<p class="MsoNormal"><img alt="http://sig.cmparks.net/cmp-ms-90x122.png" height="122" hspace="12" width="90" align="left">
<span style="font-size:14.0pt;font-family:"Arial","sans-serif";color:#006c56">Stephen V. Mather<br>
</span><span style="font-size:11.0pt;font-family:"Arial","sans-serif";color:#006c56">GIS Manager<br>
</span><span style="font-size:9.0pt;font-family:"Arial","sans-serif";color:#006c56"><a href="tel:%28216%29%20635-3243" value="+12166353243" target="_blank">(216) 635-3243</a> (Work)
</span><span style="font-size:11.0pt;font-family:"Calibri","sans-serif";color:#1f497d"><a href="http://www.clemetparks.com" target="_blank"><span><br>
clevelandmetroparks.com</span></a></span></p>
<p class="MsoNormal"></p>
<br>
</div>
</div>
<div></div>
</div>
</div>
</div>
</div>
<br>_______________________________________________<br>
Pgrouting-users mailing list<br>
<a href="mailto:Pgrouting-users@lists.osgeo.org">Pgrouting-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-users" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-users</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>Tao Romera Martínez<div><br></div><div>---------------------------------------------------------<br><div>Tel: 080-6805-0945<br></div><div>Address: Koganei-shi, Tokyo, Japan</div>
<div><br></div><div>Look for me on Facebook and LinkedIn </div></div><div>---------------------------------------------------------<br></div>
</div>