A.I.M.S algorithms


geodesic_algorithm_dijkstra.h
Go to the documentation of this file.
1 //Copyright (C) 2008 Danil Kirsanov, MIT License
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  {
105  vertex_pointer v = e->adjacent_vertices()[i];
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 
124  for(unsigned i=0; i<v->adjacent_edges().size(); ++i)
125  {
126  edge_pointer e = v->adjacent_edges()[i];
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
vertex_pointer_vector & adjacent_vertices()
void list_nodes_visible_from_source(MeshElementBase *p, std::vector< node_pointer > &storage)
edge_pointer_vector & adjacent_edges()
std::vector< Vertex > & vertices()
Definition: geodesic_mesh.h:43
void list_nodes_visible_from_node(node_pointer node, std::vector< node_pointer > &storage, std::vector< double > &distances, double threshold_distance)
double distance(SurfacePoint *p)
bool operator()(node_pointer const s1, node_pointer const s2) const
double distance(double *v)
vertex_pointer opposite_vertex(vertex_pointer v)