TTK
Loading...
Searching...
No Matches
ConnectedComponents.h
Go to the documentation of this file.
1
16
17#pragma once
18
19// base code includes
20#include <Debug.h>
21#include <Triangulation.h>
22
23#include <stack>
24
25namespace ttk {
26 class ConnectedComponents : virtual public Debug {
27
28 using TID = ttk::SimplexId;
29
30 private:
31 const int UNLABELED{-2};
32 const int IGNORE{-1};
33
34 public:
35 struct Component {
36 int id = -1;
37 float center[3]{0, 0, 0};
38 float size{0};
39 };
40
42 this->setDebugMsgPrefix("ConnectedComponents");
43 };
44 ~ConnectedComponents() override = default;
45
47 ttk::AbstractTriangulation *triangulation) const {
48 return triangulation->preconditionVertexNeighbors();
49 };
50
51 template <typename TT = ttk::AbstractTriangulation>
52 int computeFloodFill(int *labels,
53 std::vector<Component> &components,
54
55 const TT *triangulation,
56 const TID seed) const {
57 // get component id
58 const TID componentId = components.size();
59
60 std::stack<TID> stack;
61 stack.push(seed);
62 labels[seed] = componentId;
63 TID id = seed;
64
65 float size = 0;
66 float x, y, z;
67 float center[3] = {0, 0, 0};
68
69 while(!stack.empty()) {
70 const auto cIndex = stack.top();
71 stack.pop();
72
73 id = std::max(cIndex, id);
74
75 // update node data
76 triangulation->getVertexPoint(cIndex, x, y, z);
77 center[0] += x;
78 center[1] += y;
79 center[2] += z;
80 size++;
81
82 // add neihbors
83 size_t nNeighbors = triangulation->getVertexNeighborNumber(cIndex);
84 for(size_t i = 0; i < nNeighbors; i++) {
85 TID nIndex{-1};
86 triangulation->getVertexNeighbor(cIndex, i, nIndex);
87 if(labels[nIndex] == this->UNLABELED) {
88 labels[nIndex] = componentId;
89 stack.push(nIndex);
90 }
91 }
92 }
93 center[0] /= size;
94 center[1] /= size;
95 center[2] /= size;
96
97 // create component
98 components.resize(componentId + 1);
99 auto &c = components[componentId];
100 std::copy(center, center + 3, c.center);
101 c.id = id;
102 c.size = size;
103
104 return 1;
105 }
106
107 template <typename DT>
108 int initializeComponentIds(int *componentIds,
109 const TID nVertices,
110 const DT *featureMask = nullptr,
111 const DT backgroundThreshold = 0) const {
112 Timer timer;
113 std::string msg
114 = "Initializing IDs"
115 + std::string(featureMask
116 ? (" with BT: " + std::to_string(backgroundThreshold))
117 : "");
118 this->printMsg(msg, 0, 0, 1, ttk::debug::LineMode::REPLACE);
119 if(featureMask) {
120 for(TID i = 0; i < nVertices; i++)
121 componentIds[i] = featureMask[i] > backgroundThreshold
122 ? this->UNLABELED
123 : this->IGNORE;
124 } else {
125 std::fill(componentIds, componentIds + nVertices, this->UNLABELED);
126 }
127 this->printMsg(msg, 1, timer.getElapsedTime(), 1);
128
129 return 1;
130 }
131
132 template <typename TT = ttk::AbstractTriangulation>
133 int computeConnectedComponents(std::vector<Component> &components,
134 int *componentIds,
135 const TT *triangulation) const {
136
137 TID nVertices = triangulation->getNumberOfVertices();
138
139 Timer timer;
140 const std::string msg = "Computing Connected Components";
141 this->printMsg(msg, 0, 0, 1, ttk::debug::LineMode::REPLACE);
142
143 for(TID i = 0; i < nVertices; i++)
144 if(componentIds[i] == this->UNLABELED)
145 this->computeFloodFill<TT>(
146 componentIds, components, triangulation, i);
147
148 this->printMsg(msg, 1, timer.getElapsedTime(), 1);
149
150 return 1;
151 }
152
153 template <typename F, typename DT>
154 int mapData(std::vector<Component> &components,
155 const int *componentIds,
156 const int nVertices,
157 const F f,
158 DT *out) const {
159 for(TID i = 0; i < nVertices; i++)
160 out[i] = f(components, componentIds[i]);
161 return 1;
162 }
163 };
164} // namespace ttk
AbstractTriangulation is an interface class that defines an interface for efficient traversal methods...
TTK connectedComponents processing package.
int computeFloodFill(int *labels, std::vector< Component > &components, const TT *triangulation, const TID seed) const
int preconditionTriangulation(ttk::AbstractTriangulation *triangulation) const
int computeConnectedComponents(std::vector< Component > &components, int *componentIds, const TT *triangulation) const
int initializeComponentIds(int *componentIds, const TID nVertices, const DT *featureMask=nullptr, const DT backgroundThreshold=0) const
int mapData(std::vector< Component > &components, const int *componentIds, const int nVertices, const F f, DT *out) const
~ConnectedComponents() override=default
Minimalist debugging class.
Definition: Debug.h:88
void setDebugMsgPrefix(const std::string &prefix)
Definition: Debug.h:364
int printMsg(const std::string &msg, const debug::Priority &priority=debug::Priority::INFO, const debug::LineMode &lineMode=debug::LineMode::NEW, std::ostream &stream=std::cout) const
Definition: Debug.h:118
double getElapsedTime()
Definition: Timer.h:15
The Topology ToolKit.
int SimplexId
Identifier type for simplices of any dimension.
Definition: DataTypes.h:22