# A.I.M.S algorithms

geodesic_algorithm_dijkstra.h
Go to the documentation of this file.
2 #ifndef GEODESIC_ALGORITHM_DIJKSTRA_010506
3 #define GEODESIC_ALGORITHM_DIJKSTRA_010506
4
7 #include <vector>
8 #include <set>
9 #include <assert.h>
10
11 namespace geodesic{
12
14 {
15  typedef DijkstraNode* node_pointer;
16 public:
19
20  double& distance_from_source(){return m_distance;};
21  node_pointer& previous(){return m_previous;};
22  unsigned& source_index(){return m_source_index;};
23  vertex_pointer& vertex(){return m_vertex;};
24
25  void clear()
26  {
27  m_distance = GEODESIC_INF;
28  m_previous = NULL;
29  }
30
31  bool operator()(node_pointer const s1, node_pointer const s2) const
32  {
33  return s1->distance_from_source() != s2->distance_from_source() ?
35  s1->vertex()->id() < s2->vertex()->id();
36  };
37
39  {
40  return m_vertex->distance(p);
41  }
42
44  {
45  return SurfacePoint(m_vertex);
46  }
47
48 private:
49  double m_distance; //distance to the closest source
50  unsigned m_source_index; //closest source index
51  node_pointer m_previous; //previous node in the geodesic path
52  vertex_pointer m_vertex; //correspoding vertex
53 };
54
56 {
57 public:
58  typedef DijkstraNode Node;
59  typedef Node* node_pointer;
60
63  {
64  m_type = DIJKSTRA;
65
66  m_nodes.resize(mesh->vertices().size());
67  for(unsigned i=0; i<m_nodes.size(); ++i)
68  {
69  m_nodes[i].vertex() = &m_mesh->vertices()[i];
70  }
71  };
72
74
75 protected:
76
78  std::vector<node_pointer>& storage); //list all nodes that belong to this mesh element
79
80  void list_nodes_visible_from_node(node_pointer node, //list all nodes that belong to this mesh element
81  std::vector<node_pointer>& storage,
82  std::vector<double>& distances,
83  double threshold_distance); //list only the nodes whose current distance is larger than the threshold
84 };
85
87  std::vector<node_pointer>& storage)
88 {
89  assert(p->type() != UNDEFINED_POINT);
90
91  if(p->type() == FACE)
92  {
93  face_pointer f = static_cast<face_pointer>(p);
94  for(unsigned i=0; i<3; ++i)
95  {
97  storage.push_back(&m_nodes[node_index(v)]);
98  }
99  }
100  else if(p->type() == EDGE)
101  {
102  edge_pointer e = static_cast<edge_pointer>(p);
103  for(unsigned i=0; i<2; ++i)
104  {
106  storage.push_back(&m_nodes[node_index(v)]);
107  }
108  }
109  else //VERTEX
110  {
111  vertex_pointer v = static_cast<vertex_pointer>(p);
112  storage.push_back(&m_nodes[node_index(v)]);
113  }
114 }
115
116 inline void GeodesicAlgorithmDijkstra::list_nodes_visible_from_node(node_pointer node, //list all nodes that belong to this mesh element
117  std::vector<node_pointer>& storage,
118  std::vector<double>& distances,
119  double threshold_distance)
120 {
121  vertex_pointer v = node->vertex();
122  assert(storage.size() == distances.size());
123
125  {
127  vertex_pointer new_v = e->opposite_vertex(v);
128  node_pointer new_node = &m_nodes[node_index(new_v)];
129
130  if(new_node->distance_from_source() > threshold_distance + e->length())
131  {
132  storage.push_back(new_node);
133  distances.push_back(e->length());
134  }
135  }
136 }
137
138 } //geodesic
139
140 #endif //GEODESIC_ALGORITHM_DIJKSTRA_010506