[pgrouting-users] A* vs. Dijkstra and the nature of the A* implementation

[Tao Romera Martinez]

Hi Stephen,

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.
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.
The programming language is Ruby, but I think you will understand it easily
and adapt it to your programming language.

1. Construct Point: route starting point
    ->  start_pt = "ST_GeometryFromText('POINT(#{point.lon} #{point.lat})',
4326)"

2. Find closest road on the network to the starting point
      closest_road = Map.connection.execute("WITH index_query AS (
      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)
      SELECT id, ST_AsText(geom_way), x1, y1, x2, y2, source, target FROM
index_query ORDER BY distance LIMIT 1")
      closest_road_geom =
"ST_GeometryFromText('#{closest_road.getvalue(0,1)}', 4326)"

3. Find closest point lying on closest way from starting point
      closest_pt_on_closest_way = Map.connection.execute("SELECT
ST_AsText(ST_ClosestPoint(#{closest_road_geom}, #{start_pt})) AS
point;").getvalue(0,0)
      closest_pt = "ST_GeometryFromText('#{closest_pt_on_closest_road}',
4326)"

4. Get points of the closest way to the starting point
      points = Map.connection.execute("SELECT ST_AsText((point.gdump).geom)
FROM (SELECT ST_DumpPoints(#{closest_road_geom}) AS gdump) AS
point;").column_values(0)

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
      points2 = points[1..-1]
      index = 0

      # 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
      points2.each_with_index do |pt2_raw, idx|
        # Get distance
        pt1 = "ST_GeometryFromText('#{points[idx]}', 4326)"
        pt2 = "ST_GeometryFromText('#{points2[idx]}', 4326)"

        dist = Map.connection.execute("SELECT
ST_Distance(#{closest_pt},(SELECT ST_MakeLine(#{pt1},
#{pt2})));").getvalue(0,0)
        if dist.to_f < 0.0000000001
          index = idx
          break
        end
      end

6. Now we can split the road into 2
      # Split the road into 2
      road1 = ""
      points[0..index].each_with_index do |pt, idx|
        if idx == 0
          road1 = "ST_GeometryFromText('#{pt}', 4326)"
        else
          road1 = "#{road1}, ST_GeometryFromText('#{pt}', 4326)"
        end
      end
      road1 = "#{road1}, #{closest_pt}"

      road2 = closest_pt
      points[index+1..-1].each do |pt|
        road2 = "#{road2}, ST_GeometryFromText('#{pt}', 4326)"
      end

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:
  # buffer variables
    geom_buf = "road1 AS (SELECT ST_MakeLine(ARRAY[#{road}]) AS geom)"
  # Insert road into network table
    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});")

Tao


2013/4/13 Stephen V. Mather <svm at clevelandmetroparks.com>

>  Hi All,
>
> 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?
>
> Also, regarding A* implementation, is it strict, or is there any way to
> relax the admissibility criterion as currently implemented?
>
> 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.
>
> 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?
>
> Thanks,
> Best,
> Steve
>
>
>   [image: http://sig.cmparks.net/cmp-ms-90x122.png] Stephen V. Mather
> GIS Manager
> (216) 635-3243 (Work)
> clevelandmetroparks.com <http://www.clemetparks.com>
>
>
>
> _______________________________________________
> Pgrouting-users mailing list
> Pgrouting-users at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
>


-- 
Tao Romera Martínez

---------------------------------------------------------
Tel: 080-6805-0945
Address: Koganei-shi, Tokyo, Japan

Look for me on Facebook and LinkedIn
---------------------------------------------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20130413/2554acf6/attachment.html>