Loading...
Searching...
No Matches
Manifold_tracing.h
1/* This file is part of the Gudhi Library - https://gudhi.inria.fr/ - which is released under MIT.
2 * See file LICENSE or go to https://gudhi.inria.fr/licensing/ for full license details.
3 * Author(s): Siargey Kachanovich
4 *
5 * Copyright (C) 2019 Inria
6 *
7 * Modification(s):
8 * - YYYY/MM Author: Description of the modification
9 */
10
11#ifndef MANIFOLD_TRACING_H_
12#define MANIFOLD_TRACING_H_
13
14#include <gudhi/IO/output_debug_traces_to_html.h> // for DEBUG_TRACES
15#include <gudhi/Coxeter_triangulation/Query_result.h>
16
17#include <boost/functional/hash.hpp>
18
19#include <Eigen/Dense>
20
21#include <queue>
22#include <unordered_map>
23
24namespace Gudhi {
25
26namespace coxeter_triangulation {
27
38template <class Triangulation_>
40 public:
41 using Simplex_handle = typename Triangulation_::Simplex_handle;
42
43 struct Simplex_hash {
44 typedef Simplex_handle argument_type;
45 typedef std::size_t result_type;
46 result_type operator()(const argument_type& s) const noexcept {
47 return boost::hash<typename Simplex_handle::Vertex>()(s.vertex());
48 }
49 };
50
51 public:
56 typedef std::unordered_map<Simplex_handle, Eigen::VectorXd, Simplex_hash> Out_simplex_map;
57
79 template <class Point_range, class Intersection_oracle>
80 void manifold_tracing_algorithm(const Point_range& seed_points, const Triangulation_& triangulation,
81 const Intersection_oracle& oracle, Out_simplex_map& out_simplex_map) {
82 std::size_t cod_d = oracle.cod_d();
83 std::queue<Simplex_handle> queue;
84
85 for (const auto& p : seed_points) {
86 Simplex_handle full_simplex = triangulation.locate_point(p);
87 for (Simplex_handle face : full_simplex.face_range(cod_d)) {
88 Query_result<Simplex_handle> qr = oracle.intersects(face, triangulation);
89 if (qr.success && out_simplex_map.emplace(face, qr.intersection).second) {
90#ifdef DEBUG_TRACES
91 mt_seed_inserted_list.push_back(MT_inserted_info(qr, face, false));
92#endif
93 queue.emplace(face);
94 break;
95 }
96 }
97 }
98
99 while (!queue.empty()) {
100 Simplex_handle s = queue.front();
101 queue.pop();
102 for (auto cof : s.coface_range(cod_d + 1)) {
103 for (auto face : cof.face_range(cod_d)) {
104 Query_result<Simplex_handle> qr = oracle.intersects(face, triangulation);
105 if (qr.success && out_simplex_map.emplace(face, qr.intersection).second) queue.emplace(face);
106 }
107 }
108 }
109 }
110
135 template <class Point_range, class Intersection_oracle>
136 void manifold_tracing_algorithm(const Point_range& seed_points, const Triangulation_& triangulation,
137 const Intersection_oracle& oracle, Out_simplex_map& interior_simplex_map,
138 Out_simplex_map& boundary_simplex_map) {
139 std::size_t cod_d = oracle.cod_d();
140 std::queue<Simplex_handle> queue;
141
142 for (const auto& p : seed_points) {
143 Simplex_handle full_simplex = triangulation.locate_point(p);
144 for (Simplex_handle face : full_simplex.face_range(cod_d)) {
145 auto qr = oracle.intersects(face, triangulation);
146#ifdef DEBUG_TRACES
147 mt_seed_inserted_list.push_back(MT_inserted_info(qr, face, false));
148#endif
149 if (qr.success) {
150 if (oracle.lies_in_domain(qr.intersection, triangulation)) {
151 if (interior_simplex_map.emplace(face, qr.intersection).second) queue.emplace(face);
152 } else {
153 for (Simplex_handle cof : face.coface_range(cod_d + 1)) {
154 auto qrb = oracle.intersects_boundary(cof, triangulation);
155#ifdef DEBUG_TRACES
156 mt_seed_inserted_list.push_back(MT_inserted_info(qrb, cof, true));
157#endif
158 if (qrb.success) boundary_simplex_map.emplace(cof, qrb.intersection);
159 }
160 }
161 // break;
162 }
163 }
164 }
165
166 while (!queue.empty()) {
167 Simplex_handle s = queue.front();
168 queue.pop();
169 for (auto cof : s.coface_range(cod_d + 1)) {
170 for (auto face : cof.face_range(cod_d)) {
171 auto qr = oracle.intersects(face, triangulation);
172#ifdef DEBUG_TRACES
173 mt_inserted_list.push_back(MT_inserted_info(qr, face, false));
174#endif
175 if (qr.success) {
176 if (oracle.lies_in_domain(qr.intersection, triangulation)) {
177 if (interior_simplex_map.emplace(face, qr.intersection).second) queue.emplace(face);
178 } else {
179 auto qrb = oracle.intersects_boundary(cof, triangulation);
180#ifdef DEBUG_TRACES
181 mt_inserted_list.push_back(MT_inserted_info(qrb, cof, true));
182#endif
183 if (qrb.success) boundary_simplex_map.emplace(cof, qrb.intersection);
184 }
185 }
186 }
187 }
188 }
189 }
190
193};
194
222template <class Point_range, class Triangulation, class Intersection_oracle, class Out_simplex_map>
223void manifold_tracing_algorithm(const Point_range& seed_points, const Triangulation& triangulation,
224 const Intersection_oracle& oracle, Out_simplex_map& out_simplex_map) {
226 mt.manifold_tracing_algorithm(seed_points, triangulation, oracle, out_simplex_map);
227}
228
258template <class Point_range, class Triangulation, class Intersection_oracle, class Out_simplex_map>
259void manifold_tracing_algorithm(const Point_range& seed_points, const Triangulation& triangulation,
260 const Intersection_oracle& oracle, Out_simplex_map& interior_simplex_map,
261 Out_simplex_map& boundary_simplex_map) {
263 mt.manifold_tracing_algorithm(seed_points, triangulation, oracle, interior_simplex_map, boundary_simplex_map);
264}
265
266} // namespace coxeter_triangulation
267
268} // namespace Gudhi
269
270#endif
A class that assembles methods for manifold tracing algorithm.
Definition: Manifold_tracing.h:39
void manifold_tracing_algorithm(const Point_range &seed_points, const Triangulation_ &triangulation, const Intersection_oracle &oracle, Out_simplex_map &interior_simplex_map, Out_simplex_map &boundary_simplex_map)
Computes the set of k-simplices that intersect the dimensional manifold given by an intersection orac...
Definition: Manifold_tracing.h:136
Manifold_tracing()
Empty constructor.
Definition: Manifold_tracing.h:192
std::unordered_map< Simplex_handle, Eigen::VectorXd, Simplex_hash > Out_simplex_map
Type of the output simplex map with keys of type Triangulation_::Simplex_handle and values of type Ei...
Definition: Manifold_tracing.h:56
void manifold_tracing_algorithm(const Point_range &seed_points, const Triangulation_ &triangulation, const Intersection_oracle &oracle, Out_simplex_map &out_simplex_map)
Computes the set of k-simplices that intersect a boundaryless implicit manifold given by an intersect...
Definition: Manifold_tracing.h:80
void manifold_tracing_algorithm(const Point_range &seed_points, const Triangulation &triangulation, const Intersection_oracle &oracle, Out_simplex_map &out_simplex_map)
Static method for Manifold_tracing<Triangulation_>::manifold_tracing_algorithm that computes the set ...
Definition: Manifold_tracing.h:223
The result of a query by an oracle such as Implicit_manifold_intersection_oracle.
Definition: Query_result.h:26
bool success
True if the query simplex intersects the manifold.
Definition: Query_result.h:33
Eigen::VectorXd intersection
The potentially lower-dimensional face of the query simplex that contains the intersection point....
Definition: Query_result.h:31