#
root/sandbox/orkney/astar.h

Revision 84, 4.4 KB (checked in by anton, 3 years ago) |
---|

Line | |
---|---|

1 | /* |

2 | * A* Shortest path algorithm for PostgreSQL |

3 | * |

4 | * Copyright (c) 2007 Anton A. Patrushev, Orkney, Inc. |

5 | * |

6 | * This program is free software; you can redistribute it and/or modify |

7 | * it under the terms of the GNU General Public License as published by |

8 | * the Free Software Foundation; either version 2 of the License, or |

9 | * (at your option) any later version. |

10 | * |

11 | * This program is distributed in the hope that it will be useful, |

12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |

13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |

14 | * GNU General Public License for more details. |

15 | * |

16 | * You should have received a copy of the GNU General Public License |

17 | * along with this program; if not, write to the Free Software |

18 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |

19 | * |

20 | */ |

21 | |

22 | #ifndef _ASTAR_H_INCLUDED |

23 | #define _ASTAR_H_INCLUDED |

24 | |

25 | #include "ogr_core.h" |

26 | #include "ogr_feature.h" |

27 | #include "ogr_geometry.h" |

28 | |

29 | #include <boost/config.hpp> |

30 | #include <boost/graph/graph_traits.hpp> |

31 | #include <boost/graph/adjacency_list.hpp> |

32 | #include <boost/graph/astar_search.hpp> |

33 | |

34 | #include <math.h> // for sqrt |

35 | |

36 | #include "dijkstra.h" |

37 | |

38 | |

39 | using namespace std; |

40 | using namespace boost; |

41 | |

42 | // visitor that terminates when we find the goal |

43 | template <class Vertex> |

44 | class astar_goal_visitor : public boost::default_astar_visitor |

45 | { |

46 | public: |

47 | astar_goal_visitor(Vertex goal) : m_goal(goal) {} |

48 | template <class Graph> |

49 | void examine_vertex(Vertex u, Graph& g) { |

50 | if(u == m_goal) |

51 | throw found_goal(); |

52 | } |

53 | private: |

54 | Vertex m_goal; |

55 | }; |

56 | |

57 | template <class Graph, class CostType> |

58 | class distance_heuristic : public astar_heuristic<Graph, CostType> |

59 | { |

60 | public: |

61 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; |

62 | distance_heuristic(Graph& g, Vertex goal):m_g(g), m_goal(goal){} |

63 | CostType operator()(Vertex u) |

64 | { |

65 | CostType dx = m_g[m_goal].x - m_g[u].x; |

66 | CostType dy = m_g[m_goal].y - m_g[u].y; |

67 | //You can choose any heuristical function from below |

68 | //return ::max(dx, dy); |

69 | //return ::sqrt(dx * dx + dy * dy)/4; |

70 | //return 0; |

71 | return (::fabs(dx)+::fabs(dy))/2; |

72 | } |

73 | private: |

74 | Graph& m_g; |

75 | Vertex m_goal; |

76 | }; |

77 | |

78 | class AStar : public Dijkstra |

79 | { |

80 | public: |

81 | AStar(){} |

82 | AStar( char *nameIn, bool directedIn, bool weightedIn, bool reverseCostIn ) |

83 | : Dijkstra( nameIn, directedIn, weightedIn, reverseCostIn ){} |

84 | virtual ~AStar(){} |

85 | |

86 | bool addEdge(edge_descriptor *e, OGRFeature *edge, graph_t &graph) |

87 | { |

88 | bool inserted; |

89 | |

90 | if (edge->GetFieldAsDouble(COST_FIELD) < 0) // edges are not inserted in the graph if cost is negative |

91 | return false; |

92 | |

93 | tie(*e, inserted) = add_edge(edge->GetFieldAsInteger(SOURCE_FIELD), |

94 | edge->GetFieldAsInteger(TARGET_FIELD), graph); |

95 | |

96 | graph[*e].cost = edge->GetFieldAsDouble(COST_FIELD); |

97 | graph[*e].id = edge->GetFieldAsInteger(ID_FIELD); |

98 | |

99 | OGRLineString *geom = static_cast<OGRLineString*>(edge->GetGeometryRef()); |

100 | |

101 | vertex_descriptor s = vertex(edge->GetFieldAsInteger(SOURCE_FIELD), graph); |

102 | vertex_descriptor t = vertex(edge->GetFieldAsInteger(TARGET_FIELD), graph); |

103 | |

104 | graph[s].x=geom->getX(0); |

105 | graph[s].y=geom->getY(0); |

106 | graph[t].x=geom->getX(geom->getNumPoints()-1); |

107 | graph[t].y=geom->getY(geom->getNumPoints()-1); |

108 | |

109 | return inserted; |

110 | } |

111 | |

112 | |

113 | int getRoute(int start, int end, OGRFeature **edges, OGRFeature **result, int *resultCount, graph_t &graph) |

114 | { |

115 | std::vector<vertex_descriptor> predecessors(num_vertices(graph)); |

116 | |

117 | vertex_descriptor source = vertex(start, graph); |

118 | |

119 | if (source < 0) |

120 | { |

121 | return NO_SOURCE_FOUND; |

122 | } |

123 | |

124 | vertex_descriptor target = vertex(end, graph); |

125 | if (target < 0) |

126 | { |

127 | return NO_TARGET_FOUND; |

128 | } |

129 | |

130 | std::vector<double> distances(num_vertices(graph)); |

131 | |

132 | try |

133 | { |

134 | // call astar named parameter interface |

135 | astar_search |

136 | (graph, source, |

137 | distance_heuristic<graph_t, float>(graph, target), |

138 | predecessor_map(&predecessors[0]). |

139 | weight_map(get(&Edge::cost, graph)). |

140 | distance_map(&distances[0]). |

141 | visitor(astar_goal_visitor<vertex_descriptor>(target))); |

142 | } |

143 | catch(found_goal fg) |

144 | { |

145 | return makeResult(target, source, edges, predecessors, result, resultCount, graph); |

146 | } |

147 | return NO_PATH_FOUND; |

148 | } |

149 | }; |

150 | |

151 | #endif |

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