FOUND Coverage Report

src/
File: distance/edge.cpp
Date: 2025-11-20 21:57:26
Lines:
176/176
100.0%
Functions:
6/6
100.0%
Branches:
174/174
100.0%
Line Branch Exec Source
1 #include "distance/edge.hpp"
2
3 #include <unordered_map>
4 #include <algorithm>
5 #include <memory>
6 #include <vector>
7 #include <functional>
8 #include <unordered_set>
9
10 #include "common/style.hpp"
11 #include "common/decimal.hpp"
12
13 namespace found {
14
15 ////// Simple Edge Detection Algorithm //////
16
17 // TODO: Investigate if the use of the DECIMAL(x) cast is taking up too much time
18
19 25 Points SimpleEdgeDetectionAlgorithm::Run(const Image &image) {
20 // Step 0: Define Common Variables
21 25 uint64_t imageSize = image.width * image.height;
22
23 // Step 1: Obtain the component that represents space
24 50 Components spaces = ConnectedComponentsAlgorithm(image, [&](uint64_t index, const Image &image) {
25 // Average the pixel, then threshold it
26 3024804 int sum = 0;
27
2/2
✓ Branch 0 taken 9073572 times.
✓ Branch 1 taken 3024804 times.
 12098376 for (int i = 0; i < image.channels; i++) sum += image.image[image.channels * index + i];
28 3024804 return sum / image.channels < this->threshold_;
29
1/1
✓ Branch 4 taken 25 times.
 50 });
30 25 Component *space = nullptr;
31
2/2
✓ Branch 7 taken 370 times.
✓ Branch 8 taken 25 times.
 395 for (auto &component : spaces) {
32 // Basically, if the component touches the border, and its the biggest one,
33 // we assume it is space
34
2/2
✓ Branch 0 taken 358 times.
✓ Branch 1 taken 12 times.
 370 if ((component.upperLeft.x < this->borderLength_ ||
35
2/2
✓ Branch 0 taken 347 times.
✓ Branch 1 taken 11 times.
 358 component.upperLeft.y < this->borderLength_ ||
36
2/2
✓ Branch 0 taken 346 times.
✓ Branch 1 taken 1 times.
 347 component.lowerRight.x >= image.width - this->borderLength_ ||
37
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 345 times.
 346 component.lowerRight.y >= image.height - this->borderLength_)) {
38
6/6
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 21 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 23 times.
✓ Branch 7 taken 2 times.
 25 if (!space || component.points.size() > space->points.size())
39 23 space = &component;
40 }
41 }
42
6/6
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 4 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 20 times.
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 20 times.
 25 if (space == nullptr || space->points.size() == imageSize) return Points();
43 20 std::unordered_set<uint64_t> &points = space->points;
44
45 // Step 2: Identify the edge as the edge of space
46
47 // Step 2a: Figure out the centroids of space and the planet
48 20 Vec2 planetCentroid{0, 0};
49 20 Vec2 spaceCentroid{0, 0};
50 20 int64_t planetSize = 0;
51 20 int64_t spaceSize = 0;
52
2/2
✓ Branch 1 taken 1573209 times.
✓ Branch 2 taken 20 times.
 1573229 for (uint64_t i = 0; i < imageSize; i++) {
53
3/3
✓ Branch 4 taken 1573209 times.
✓ Branch 9 taken 303647 times.
✓ Branch 10 taken 1269562 times.
 1573209 if (points.find(i) == points.end()) {
54 303647 planetCentroid.x += i % image.width;
55 303647 planetCentroid.y += i / image.width;
56 303647 planetSize++;
57 } else {
58 1269562 spaceCentroid.x += i % image.width;
59 1269562 spaceCentroid.y += i / image.width;
60 1269562 spaceSize++;
61 }
62 }
63 20 planetCentroid.x /= planetSize;
64 20 planetCentroid.y /= planetSize;
65 20 spaceCentroid.x /= spaceSize;
66 20 spaceCentroid.y /= spaceSize;
67
68
1/1
✓ Branch 1 taken 20 times.
 20 Vec2 itrDirection = spaceCentroid - planetCentroid;
69
70 // Step 2b: Figure out how to iterate through the image,
71 // iterating from the planet into space
72 20 Points result;
73
2/2
✓ Branch 2 taken 7 times.
✓ Branch 3 taken 13 times.
 20 if (std::abs(itrDirection.y) > std::abs(itrDirection.x)) {
74 // Determine which direction we want to iterate,
75 // (we want to iterate into the space)
76 uint64_t update;
77 uint64_t start;
78 decimal offset;
79 uint64_t edge_condition;
80
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 3 times.
 7 if (itrDirection.y < 0) {
81 // Iterate up, and start at the bottom left corner
82 4 update = -image.width;
83 4 start = static_cast<uint64_t>(space->lowerRight.y * image.width + space->upperLeft.x);
84 4 offset = -this->offset_;
85 4 edge_condition = image.height - 1;
86 } else {
87 // Iterate down, and start at the top left corner
88 3 update = image.width;
89 3 start = static_cast<uint64_t>(space->upperLeft.y * image.width + space->upperLeft.x);
90 3 offset = this->offset_;
91 3 edge_condition = 0;
92 }
93 // Step 2c: Get all edge points along the edge, identifying the edge
94 // as the first point that is found inside space
95
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 7 times.
 41 for (int col = space->upperLeft.x; col <= space->lowerRight.x; col++) {
96 // because index is uint64_t, going below zero will overflow, and it will indeed be past the dimensions
97 34 uint64_t index = start;
98
3/3
✓ Branch 4 taken 55 times.
✓ Branch 9 taken 21 times.
✓ Branch 10 taken 34 times.
 55 while (points.find(index) == points.end()) index += update;
99
2/2
✓ Branch 0 taken 31 times.
✓ Branch 1 taken 3 times.
 34 if (index / image.width != edge_condition) {
100 31 index -= update;
101 62 result.push_back({DECIMAL(index % image.width),
102
1/1
✓ Branch 1 taken 31 times.
 31 DECIMAL(index / image.width) - offset});
103 }
104 34 start++;
105 }
106 } else {
107 // Determine which direction we want to iterate
108 uint64_t update;
109 uint64_t start;
110 decimal offset;
111 uint64_t edge_condition;
112
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12 times.
 13 if (itrDirection.x < 0) {
113 // Iterate left, and start at the top right corner
114 1 update = -1;
115 1 start = static_cast<uint64_t>(space->upperLeft.y * image.width + space->lowerRight.x);
116 1 offset = -this->offset_;
117 1 edge_condition = image.width - 1;
118 } else {
119 // Iterate right, and start at the top left corner
120 12 update = 1;
121 12 start = static_cast<uint64_t>(space->upperLeft.y * image.width + space->upperLeft.x);
122 12 offset = this->offset_;
123 12 edge_condition = 0;
124 }
125 // Step 2c: Get all edge points along the edge, identifying the edge
126 // as the first point that is found inside space
127
2/2
✓ Branch 0 taken 3102 times.
✓ Branch 1 taken 13 times.
 3115 for (int row = space->upperLeft.y; row <= space->lowerRight.y; row++) {
128 3102 uint64_t index = start;
129
3/3
✓ Branch 4 taken 23944 times.
✓ Branch 9 taken 20842 times.
✓ Branch 10 taken 3102 times.
 23944 while (points.find(index) == points.end()) index += update;
130
2/2
✓ Branch 0 taken 3101 times.
✓ Branch 1 taken 1 times.
 3102 if (index % image.width != edge_condition) {
131 3101 index -= update;
132 6202 result.push_back({DECIMAL(index % image.width) - offset,
133
1/1
✓ Branch 1 taken 3101 times.
 3101 DECIMAL(index / image.width)});
134 }
135 3102 start += image.width;
136 }
137 }
138
139 // Step 4: Return the points
140 20 return result;
141 25 }
142
143 ////// Connected Components Algorithm //////
144
145 /**
146 * Checks if a label is present in the list of adjacent labels
147 *
148 * @param label The label to check
149 * @param adjacentLabels The list of adjacent labels
150 * @param size The size of the list
151 *
152 * @return true iff label is in adjacentLabels
153 */
154 3795774 inline bool LabelPresent(int label, int *adjacentLabels, int size) {
155
2/2
✓ Branch 0 taken 3628 times.
✓ Branch 1 taken 3792146 times.
 3795774 if (size == 0) return false;
156
2/2
✓ Branch 0 taken 3792150 times.
✓ Branch 1 taken 46 times.
 3792196 for (int i = 0; i < size; i++) {
157
2/2
✓ Branch 0 taken 3792100 times.
✓ Branch 1 taken 50 times.
 3792150 if (adjacentLabels[i] == label) {
158 3792100 return true;
159 }
160 }
161 46 return false;
162 }
163
164 /**
165 * Updates the component with the given pixel
166 *
167 * @param component The component to update
168 * @param index The index to add
169 * @param pixel The pixel to add
170 *
171 * @pre Must be called in order of increasing index
172 */
173 1270412 inline void UpdateComponent(Component &component, uint64_t index, Vec2 &pixel) {
174 1270412 component.points.insert(index);
175
2/2
✓ Branch 0 taken 59 times.
✓ Branch 1 taken 1270353 times.
 1270412 if (component.upperLeft.x > pixel.x) component.upperLeft.x = pixel.x;
176
2/2
✓ Branch 0 taken 2696 times.
✓ Branch 1 taken 1267657 times.
 1270353 else if (component.lowerRight.x < pixel.x) component.lowerRight.x = pixel.x;
177 // We skip this statement, since its impossible:
178 // if (component.upperLeft.y > pixel.y) component.upperLeft.y = pixel.y;
179
2/2
✓ Branch 0 taken 3677 times.
✓ Branch 1 taken 1266735 times.
 1270412 if (component.lowerRight.y < pixel.y) component.lowerRight.y = pixel.y;
180 1270412 }
181
182 /**
183 * Adds a pixel to some component, creating a new component if necessary
184 *
185 * @param image The image to which the pixel belongs
186 * @param index The index of the pixel
187 * @param L The current label
188 * @param adjacentLabels The labels of the adjacent components
189 * @param size The number of adjacent labels
190 * @param components The components that are part of the image
191 * @param equivalencies The labels that are equivalent to each other
192 *
193 * @return The label of the component point that was added
194 *
195 * Updates components with the new pixel as appropriate
196 */
197 1270820 inline int NWayEquivalenceAdd(const Image &image,
198 uint64_t index,
199 int &L,
200 int adjacentLabels[4],
201 int size,
202 std::unordered_map<int, Component> &components,
203 std::unordered_map<int, int> &equivalencies) {
204 1270820 Vec2 pixel = {DECIMAL(index % image.width), DECIMAL(index / image.width)};
205
2/2
✓ Branch 0 taken 408 times.
✓ Branch 1 taken 1270412 times.
 1270820 if (size == 0) {
206 // No adjacent labels
207
1/1
✓ Branch 3 taken 408 times.
 1224 components.insert({++L, {{index}, pixel, pixel}});
208 408 return L;
209
2/2
✓ Branch 0 taken 1270370 times.
✓ Branch 1 taken 42 times.
 1270412 } else if (size == 1) {
210 // One adjacent label
211
2/2
✓ Branch 1 taken 1270370 times.
✓ Branch 4 taken 1270370 times.
 1270370 UpdateComponent(components[adjacentLabels[0]], index, pixel);
212 1270370 return adjacentLabels[0];
213
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 4 times.
 42 } else if (size == 2) { // Added for optimization
214
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 19 times.
 38 if (adjacentLabels[0] < adjacentLabels[1]) {
215 // Two adjacent labels, first is smaller
216
2/2
✓ Branch 1 taken 19 times.
✓ Branch 4 taken 19 times.
 19 UpdateComponent(components[adjacentLabels[0]], index, pixel);
217
3/3
✓ Branch 4 taken 19 times.
✓ Branch 9 taken 7 times.
✓ Branch 10 taken 12 times.
 19 if (equivalencies.find(adjacentLabels[1]) == equivalencies.end()) {
218
1/1
✓ Branch 1 taken 7 times.
 7 equivalencies.try_emplace(adjacentLabels[1], adjacentLabels[0]);
219 } else {
220
2/2
✓ Branch 1 taken 12 times.
✓ Branch 5 taken 12 times.
 12 equivalencies[adjacentLabels[1]] = std::min(equivalencies[adjacentLabels[1]], adjacentLabels[0]);
221 }
222 19 return adjacentLabels[0];
223 }
224
225 // Two adjacent labels, second is smaller
226
2/2
✓ Branch 1 taken 19 times.
✓ Branch 4 taken 19 times.
 19 UpdateComponent(components[adjacentLabels[1]], index, pixel);
227
3/3
✓ Branch 4 taken 19 times.
✓ Branch 9 taken 15 times.
✓ Branch 10 taken 4 times.
 19 if (equivalencies.find(adjacentLabels[0]) == equivalencies.end()) {
228
1/1
✓ Branch 1 taken 15 times.
 15 equivalencies.try_emplace(adjacentLabels[0], adjacentLabels[1]);
229 } else {
230
2/2
✓ Branch 1 taken 4 times.
✓ Branch 5 taken 4 times.
 4 equivalencies[adjacentLabels[0]] = std::min(equivalencies[adjacentLabels[0]], adjacentLabels[1]);
231 }
232 19 return adjacentLabels[1];
233 }
234 4 int minLabel = adjacentLabels[0];
235
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 for (int i = 1; i < size; i++) {
236
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 6 times.
 8 if (adjacentLabels[i] < minLabel) {
237 2 minLabel = adjacentLabels[i];
238 }
239 }
240
2/2
✓ Branch 1 taken 4 times.
✓ Branch 4 taken 4 times.
 4 UpdateComponent(components[minLabel], index, pixel);
241
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 4 times.
 16 for (int i = 0; i < size; i++) {
242
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 if (adjacentLabels[i] != minLabel) {
243
3/3
✓ Branch 4 taken 8 times.
✓ Branch 9 taken 4 times.
✓ Branch 10 taken 4 times.
 8 if (equivalencies.find(adjacentLabels[i]) == equivalencies.end()) {
244
1/1
✓ Branch 1 taken 4 times.
 4 equivalencies.try_emplace(adjacentLabels[i], minLabel);
245 } else {
246
2/2
✓ Branch 1 taken 4 times.
✓ Branch 5 taken 4 times.
 4 equivalencies[adjacentLabels[i]] = std::min(equivalencies[adjacentLabels[i]], minLabel);
247 }
248 }
249 }
250 4 return minLabel;
251 1224 }
252
253 47 Components ConnectedComponentsAlgorithm(const Image &image, std::function<bool(uint64_t, const Image &)> Criteria) {
254 // Step 0: Setup the Problem
255 47 std::unordered_map<int, Component> components;
256 47 std::unordered_map<int, int> equivalencies;
257 − std::unique_ptr<int[]> componentPoints(new int[image.width * image.height]{}); // Faster than using a hashset
258
259 46 int L = 0;
260 46 int adjacentLabels[4];
261 46 int size = 0;
262
263 // Step 1: Iterate through the image, forming primary groups of
264 // components, taking note of equivalent components
265
266 // Step 1a: Tackle the First Pixel
267
3/3
✓ Branch 1 taken 46 times.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 31 times.
 46 if (Criteria(0, image)) {
268
1/1
✓ Branch 3 taken 15 times.
 45 components.insert({++L, {{0}, {0, 0}, {0, 0}}});
269 15 componentPoints[0] = L;
270 }
271
272 46 uint64_t imageSize = static_cast<uint64_t>(image.width * image.height);
273
2/2
✓ Branch 0 taken 3025064 times.
✓ Branch 1 taken 46 times.
 3025110 for (uint64_t i = 1; i < imageSize; i++) {
274 // Step 1b: Check if the pixel is an component point
275
3/3
✓ Branch 1 taken 3025064 times.
✓ Branch 3 taken 1754244 times.
✓ Branch 4 taken 1270820 times.
 3025064 if (!Criteria(i, image)) {
276 1754244 continue;
277 }
278
279 // Step 1c: Figure out all adjacent labels
280
2/2
✓ Branch 0 taken 2574 times.
✓ Branch 1 taken 1268246 times.
 1270820 if (i / image.width == 0) {
281 // Top Row (1 other pixel)
282
2/2
✓ Branch 1 taken 2545 times.
✓ Branch 2 taken 29 times.
 2574 if (auto left = componentPoints[i - 1]; left != 0) {
283 2545 adjacentLabels[size++] = left;
284 }
285
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 1268190 times.
 1268246 } else if (i % image.width == 0) {
286 // Left Column (2 other pixels)
287
2/2
✓ Branch 1 taken 37 times.
✓ Branch 2 taken 19 times.
 56 if (auto top = componentPoints[i - image.width]; top != 0) {
288 37 adjacentLabels[size++] = top;
289 }
290
2/2
✓ Branch 1 taken 26 times.
✓ Branch 2 taken 30 times.
 56 if (auto topRight = componentPoints[i - image.width + 1]; topRight != 0) {
291
2/2
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 21 times.
 26 if (!LabelPresent(topRight, adjacentLabels, size)) {
292 5 adjacentLabels[size++] = topRight;
293 }
294 }
295
2/2
✓ Branch 0 taken 3133 times.
✓ Branch 1 taken 1265057 times.
 1268190 } else if ((i + 1) % image.width == 0) {
296 // Right Column (3 other pixels)
297
2/2
✓ Branch 1 taken 3108 times.
✓ Branch 2 taken 25 times.
 3133 if (auto left = componentPoints[i - 1]; left != 0) {
298 3108 adjacentLabels[size++] = left;
299 }
300
2/2
✓ Branch 1 taken 3107 times.
✓ Branch 2 taken 26 times.
 3133 if (auto topLeft = componentPoints[i - image.width - 1]; topLeft != 0) {
301
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 3099 times.
 3107 if (!LabelPresent(topLeft, adjacentLabels, size)) {
302 8 adjacentLabels[size++] = topLeft;
303 }
304 }
305
2/2
✓ Branch 1 taken 3121 times.
✓ Branch 2 taken 12 times.
 3133 if (auto top = componentPoints[i - image.width]; top != 0) {
306
2/2
✓ Branch 1 taken 14 times.
✓ Branch 2 taken 3107 times.
 3121 if (!LabelPresent(top, adjacentLabels, size)) {
307 14 adjacentLabels[size++] = top;
308 }
309 }
310 } else {
311 // All others pixels (4 other pixels)
312
2/2
✓ Branch 1 taken 1261094 times.
✓ Branch 2 taken 3963 times.
 1265057 if (auto left = componentPoints[i - 1]; left != 0) {
313 1261094 adjacentLabels[size++] = left;
314 }
315
2/2
✓ Branch 1 taken 1260994 times.
✓ Branch 2 taken 4063 times.
 1265057 if (auto topLeft = componentPoints[i - image.width - 1]; topLeft != 0) {
316
2/2
✓ Branch 1 taken 112 times.
✓ Branch 2 taken 1260882 times.
 1260994 if (!LabelPresent(topLeft, adjacentLabels, size)) {
317 112 adjacentLabels[size++] = topLeft;
318 }
319 }
320
2/2
✓ Branch 1 taken 1264417 times.
✓ Branch 2 taken 640 times.
 1265057 if (auto top = componentPoints[i - image.width]; top != 0) {
321
2/2
✓ Branch 1 taken 3393 times.
✓ Branch 2 taken 1261024 times.
 1264417 if (!LabelPresent(top, adjacentLabels, size)) {
322 3393 adjacentLabels[size++] = top;
323 }
324 }
325
2/2
✓ Branch 1 taken 1264109 times.
✓ Branch 2 taken 948 times.
 1265057 if (auto topRight = componentPoints[i - image.width + 1]; topRight != 0) {
326
2/2
✓ Branch 1 taken 142 times.
✓ Branch 2 taken 1263967 times.
 1264109 if (!LabelPresent(topRight, adjacentLabels, size)) {
327 142 adjacentLabels[size++] = topRight;
328 }
329 }
330 }
331
332 // Step 1d: Add the pixel to the appropriate component and prepare for the next iteration
333
1/1
✓ Branch 1 taken 1270820 times.
 1270820 componentPoints[i] = NWayEquivalenceAdd(image, i, L, adjacentLabels, size, components, equivalencies);
334 1270820 size = 0;
335 }
336
337 // Step 2: Now we need to merge the equivalent components. We merge the higher
338 // label into the lower label, and update the lowest and highest points,
339 // and then get rid of the higher label's component data. We iterate from highest to lowest
340
2/2
✓ Branch 1 taken 469 times.
✓ Branch 2 taken 46 times.
 515 for (int i = L; i >= 0; i--) {
341
1/1
✓ Branch 2 taken 469 times.
 469 auto it = equivalencies.find(i);
342
2/2
✓ Branch 4 taken 443 times.
✓ Branch 5 taken 26 times.
 469 if (it == equivalencies.end()) continue;
343
344 // Guarenteed to be the lowest label
345 26 int lowestLabel = it->second;
346
347 // Merge the components
348
1/1
✓ Branch 2 taken 26 times.
 26 auto compIt = components.find(i);
349 // compIt is guarenteed to exist, so we do not perform a check here
350 26 auto &compToMerge = compIt->second;
351
1/1
✓ Branch 1 taken 26 times.
 26 auto &lowestComp = components[lowestLabel];
352
1/1
✓ Branch 3 taken 26 times.
 26 lowestComp.points.insert(compToMerge.points.begin(), compToMerge.points.end());
353
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 11 times.
 26 if (compToMerge.upperLeft.x < lowestComp.upperLeft.x) lowestComp.upperLeft.x = compToMerge.upperLeft.x;
354
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 24 times.
 26 if (compToMerge.lowerRight.x > lowestComp.lowerRight.x) lowestComp.lowerRight.x = compToMerge.lowerRight.x;
355 // We skip this statement, because its impossible (a higher component is level or lower than a lower component):
356 // if (compToMerge.upperLeft.y < lowestComp.upperLeft.y) lowestComp.upperLeft.y = compToMerge.upperLeft.y;
357
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 25 times.
 26 if (compToMerge.lowerRight.y > lowestComp.lowerRight.y) lowestComp.lowerRight.y = compToMerge.lowerRight.y;
358
359
1/1
✓ Branch 1 taken 26 times.
 26 components.erase(compIt);
360 }
361
362 // Step 3: Return the components
363 46 Components result;
364
3/3
✓ Branch 8 taken 397 times.
✓ Branch 12 taken 397 times.
✓ Branch 13 taken 46 times.
 443 for (const auto &[label, component] : components) result.push_back(component);
365
366 46 return result;
367 93 }
368
369 } // namespace found
370