Loading [MathJax]/extensions/tex2jax.js
IMP logo
IMP Reference Guide  2.22.0
The Integrative Modeling Platform
PathMapTile.h
Go to the documentation of this file.
1 /**
2  * \file IMP/bff/PathMapTile.h
3  * \brief Tile used in path search by PathMap
4  *
5  * \authors Thomas-Otavio Peulen
6  * Copyright 2007-2022 IMP Inventors. All rights reserved.
7  *
8  */
9 #ifndef IMPBFF_PATHMAPTILE_H
10 #define IMPBFF_PATHMAPTILE_H
11 
12 #include <IMP/bff/bff_config.h>
13 
14 #include <cmath> /* std::sqrt */
15 #include <vector>
16 #include <utility> /* std::pair */
17 #include <algorithm>
18 
20 
21 IMPBFF_BEGIN_NAMESPACE
22 
23 const bool TILE_VISITED_DEFAULT = false;
24 const float TILE_PENALTY_DEFAULT = 100000.0f;
25 const float TILE_COST_DEFAULT = 100000.0f;
26 const float TILE_EDGE_COST_DEFAULT = 100000.0f;
27 
28 const float TILE_PENALTY_THRESHOLD = 100000.0f;
29 const float TILE_OBSTACLE_THRESHOLD = 0.000001f;
30 const float TILE_OBSTACLE_PENALTY = 100000.0f;
31 
32 
33 /// Value types that can be read from a PathMapTile
34 typedef enum{
35  PM_TILE_PENALTY, /// Write path penalty
36  PM_TILE_COST, /// Write cost
37  PM_TILE_DENSITY, /// Density of tile
38  PM_TILE_COST_DENSITY, /// Threshold path length and write tile weights
39  PM_TILE_PATH_LENGTH, /// Write path length
40  PM_TILE_PATH_LENGTH_DENSITY, /// Threshold path length and write tile weights
41  PM_TILE_FEATURE, /// Threshold path length and write tile weights
42  PM_TILE_ACCESSIBLE_DENSITY, /// Density that is accessible (Path length in bounds)
43  PM_TILE_ACCESSIBLE_FEATURE /// Feature that is accessible (Path length in bounds)
45 
46 
47 class PathMap;
48 
49 //!* Tile used in path search by PathMap
50 class IMPBFFEXPORT PathMapTile{
51 
52 friend class PathMap;
53 
54 private:
55 
56  //! Compute edges of tiles.
57  /*! Fill the edges tiles that correspond to voxels
58  * in an AccessibleVolume.
59  *
60  * A edge is a neighboring tile. The neighborhood is
61  * defined by a 3D box around a Tile. A tile that has
62  * a visit penalty that exceeds a threshold value is
63  * not added to the neighbor / edge list.
64  *
65  * @param av AccessibleVolume
66  * @param tiles List of tiles with empty edges
67  * @param neighbor_radius neighboring tiles closer than neighbor_radius
68  * are connected by edges.
69  * @param tile_penalty_threshold Tiles with a visit penalty
70  * larger than this threshold are not added to the edge list
71  */
72  void update_edges(
74  std::vector<PathMapTile> &tiles,
75  double neighbor_radius,
76  float tile_penalty_threshold = TILE_PENALTY_THRESHOLD
77  );
78 
79  /**
80  * @brief Updates the edges of the tile.
81  * @param nx The x-coordinate of the tile.
82  * @param ny The y-coordinate of the tile.
83  * @param nz The z-coordinate of the tile.
84  * @param tiles The vector of PathMapTile objects.
85  * @param neighbor_idxs The vector of neighbor indices.
86  * @param tile_penalty_threshold The tile penalty threshold.
87  */
88  void update_edges_2(
89  int nx, int ny, int nz,
90  std::vector<PathMapTile>& tiles,
91  std::vector<int> neighbor_idxs,
92  float tile_penalty_threshold =TILE_PENALTY_THRESHOLD
93  );
94 
95 
96 protected:
97 
98  long idx; // tile index: corresponds to voxel index
99 
100  // Variable for path search
101  float penalty; // penalty for visiting tile in a path search
102  float cost; // total cost for visiting tile in a path search (integrated cost)
103  PathMapTile* previous; // tile previously visited in path search
104 
105  // Additional tile feature (e.g. av density)
106  std::map<std::string, float> features;
107 
108  // Edges leaving tile and going to neighboring tiles
109  std::vector<PathMapTileEdge> edges;
110 
111 public:
112 
113  /// AV density
114  float density;
115 
116  //! Construct an accessible volume tile
117  /*!
118  * An accessible volume (AV) tile relates to a voxel in
119  * an AV. A set of interconnected tiles (neighboring tiles)
120  * is used to compute an optimal path from the labeling site
121  * to all other positions the the AV. A path is a sequence of
122  * tiles. The cost of a path the the sum of all costs (associated
123  * to tiles and edges connecting tiles). Visiting a tile in
124  * a path adds to the cost of a path. The visiting penalty is
125  * defined when constructing a tile.
126  *
127  * @param index Identifier of the tile (corresponds to index of voxel)
128  * @param visit_penalty Penalty for visiting (used for implementing
129  * obstacles)
130  * @param tile_density Additional information of tile (can be used to
131  * implement weighted AVs)
132  */
133  explicit PathMapTile(
134  long index=-1,
135  float visit_penalty = 0.0,
136  float tile_density = 1.0
137  ) :
138  idx(index),
139  penalty(visit_penalty),
140  cost(std::numeric_limits<float>::max()),
141  previous(nullptr),
142  density(tile_density)
143  {}
144 
145 
146  /**
147  * @brief Computes the path from a tile to the origin.
148  * @return A vector of long integers representing the path.
149  */
150  std::vector<long> backtrack_to_path();
151 
152  /**
153  * @brief Get the value of a tile.
154  *
155  * A tile in an accessible volume contains information on the penalty for visiting a tile,
156  * the cost of a path from the origin of a path search to the tile, the density of the tile,
157  * and other user-defined information.
158  *
159  * When getting information from a tile, the returned values can be cropped to a range.
160  *
161  * @param value_type Specifies the type of the returned information (see: PathMapTileOutputs).
162  * Depending on the value type, the output can be the penalty for visiting the tile,
163  * the total cost of a path to the tile, or the density of the tile.
164  * Additionally, user-defined content can be accessed.
165  * @param bounds Bound for cropping the output values.
166  * @param feature_name Name of a feature (when accessing additional information).
167  * @param grid_spacing Spacing between the tiles (important to specify when accessing path length).
168  * @return Value of the tile for the specified parameters.
169  */
170  float get_value(
171  int value_type,
172  std::pair<float, float> bounds = std::pair<float, float>(
173  {std::numeric_limits<float>::min(),
174  std::numeric_limits<float>::max()}),
175  const std::string &feature_name="",
176  float grid_spacing = 1.0
177  );
178 
179  //! Set the value of a tile
180  /*!
181  * Sets the value of a tile.
182  * @param value_type Type of the value
183  * @param value value that will be written
184  * @param name name of the value (only used for user-defined tile features)
185  */
186  void set_value(int value_type, float value, const std::string &name="");
187 
188 };
189 
190 
191 IMPBFF_END_NAMESPACE
192 
193 #endif //IMPBFF_PATHMAPTILE_H
Threshold path length and write tile weights.
Definition: PathMapTile.h:42
Threshold path length and write tile weights.
Definition: PathMapTile.h:39
Class to search path on grids.
Definition: PathMap.h:45
Tile edges used in path search by PathMap.
Write path penalty.
Definition: PathMapTile.h:36
Density that is accessible (Path length in bounds)
Definition: PathMapTile.h:43
PathMapTileOutputs
Value types that can be read from a PathMapTile.
Definition: PathMapTile.h:34
PathMapTile(long index=-1, float visit_penalty=0.0, float tile_density=1.0)
Construct an accessible volume tile.
Definition: PathMapTile.h:133
Threshold path length and write tile weights.
Definition: PathMapTile.h:41
float density
AV density.
Definition: PathMapTile.h:114