JaiaBot 3.0.0
JaiaBot micro-AUV software
Loading...
Searching...
No Matches
downsample.h
Go to the documentation of this file.
1#ifndef JAIABOT_UTILS_DOWNSAMPLE_H
2#define JAIABOT_UTILS_DOWNSAMPLE_H
3
4#include <algorithm>
5#include <cmath>
6#include <cstddef>
7#include <sstream>
8#include <string>
9#include <vector>
10
11// Usage example:
12//
13// Input data row format:
14// row_index value1 value2 value3 value4
15//
16// Lambda column mapping note:
17// - row_index is parsed separately and is not part of values
18// - values[0] == value1
19// - values[1] == value2
20// - values[2] == value3
21//
22// Example: use value1 for X and value3 for Y.
23//
24// const std::vector<std::string> downsampled =
25// jaiabot::utils::downsampleDatasetToMaxBytes(
26// data_to_downsample,
27// maximum_bytes,
28// 3, // values[2] is indexed below, so rows need 3 numeric columns
29// [](const std::vector<double>& values) { return values[0]; }, // X = value1
30// [](const std::vector<double>& values) { return values[2]; } // Y = value3
31// );
32
33namespace jaiabot
34{
35namespace utils
36{
37
39struct Point
40{
41 double x;
42 double y;
43};
44
55inline std::vector<size_t> downsampleIndices(const std::vector<Point>& data, size_t target_size)
56{
57 if (data.empty())
58 {
59 return {};
60 }
61
62 if (target_size >= data.size())
63 {
64 std::vector<size_t> all_indices;
65 all_indices.reserve(data.size());
66 for (size_t i = 0; i < data.size(); ++i) { all_indices.push_back(i); }
67 return all_indices;
68 }
69
70 if (target_size <= 2)
71 {
72 return {0, data.size() - 1};
73 }
74
75 std::vector<size_t> selected_indices;
76 selected_indices.reserve(target_size);
77
78 const size_t n = data.size();
79 const double bucket_size = static_cast<double>(n - 2) / static_cast<double>(target_size - 2);
80
81 selected_indices.push_back(0);
82 size_t a_index = 0;
83
84 for (size_t i = 0; i < target_size - 2; ++i)
85 {
86 size_t c_start = static_cast<size_t>(std::floor((i + 1) * bucket_size)) + 1;
87 size_t c_end = static_cast<size_t>(std::floor((i + 2) * bucket_size)) + 1;
88 c_end = std::min(c_end, n);
89 c_start = std::min(c_start, n);
90
91 double avg_cx = 0.0;
92 double avg_cy = 0.0;
93 const size_t c_bucket_size = (c_end > c_start) ? (c_end - c_start) : 0;
94
95 for (size_t c = c_start; c < c_end; ++c)
96 {
97 avg_cx += data[c].x;
98 avg_cy += data[c].y;
99 }
100
101 if (c_bucket_size > 0)
102 {
103 avg_cx /= static_cast<double>(c_bucket_size);
104 avg_cy /= static_cast<double>(c_bucket_size);
105 }
106 else
107 {
108 avg_cx = data[a_index].x;
109 avg_cy = data[a_index].y;
110 }
111
112 size_t b_start = static_cast<size_t>(std::floor(i * bucket_size)) + 1;
113 size_t b_end = static_cast<size_t>(std::floor((i + 1) * bucket_size)) + 1;
114 b_start = std::min(b_start, n - 1);
115 b_end = std::min(b_end, n - 1);
116 if (b_end <= b_start)
117 {
118 b_end = std::min(b_start + 1, n - 1);
119 }
120
121 const Point& point_a = data[a_index];
122 double max_area = -1.0;
123 size_t next_a_index = b_start;
124
125 for (size_t b = b_start; b < b_end; ++b)
126 {
127 const double area =
128 0.5 * std::abs(point_a.x * (data[b].y - avg_cy) + data[b].x * (avg_cy - point_a.y) +
129 avg_cx * (point_a.y - data[b].y));
130
131 if (area > max_area)
132 {
133 max_area = area;
134 next_a_index = b;
135 }
136 }
137
138 selected_indices.push_back(next_a_index);
139 a_index = next_a_index;
140 }
141
142 selected_indices.push_back(n - 1);
143 return selected_indices;
144}
145
157inline bool parseDataRowValues(const std::string& line, std::vector<double>& values_out,
158 size_t min_value_count = 2)
159{
160 // Expected row shape: "index value1 value2 ... valueN" where index is integer.
161 std::istringstream iss(line);
162 long long row_index = 0;
163 if (!(iss >> row_index))
164 {
165 return false;
166 }
167
168 values_out.clear();
169 double value = 0.0;
170 while (iss >> value) { values_out.push_back(value); }
171
172 // Never accept an empty row, so front()/back() stay in bounds.
173 if (values_out.empty() || values_out.size() < min_value_count)
174 {
175 return false;
176 }
177
178 return true;
179}
180
188inline bool parseDataRow(const std::string& line, Point& point_out)
189{
190 std::vector<double> values;
191 if (!parseDataRowValues(line, values))
192 {
193 return false;
194 }
195
196 // Use first and last numeric columns as the shape coordinates.
197 point_out.x = values.front();
198 point_out.y = values.back();
199 return true;
200}
201
208inline size_t joinedSizeBytes(const std::vector<std::string>& lines)
209{
210 if (lines.empty())
211 {
212 return 0;
213 }
214
215 size_t total = 0;
216 for (const std::string& line : lines) { total += line.size(); }
217
218 // Newline separators between lines.
219 total += lines.size() - 1;
220 return total;
221}
222
234inline std::vector<std::string>
235buildOutputWithSelectedRows(const std::vector<std::string>& input_lines,
236 const std::vector<size_t>& data_line_positions,
237 const std::vector<size_t>& selected_row_indices)
238{
239 std::vector<bool> keep_data_row(data_line_positions.size(), false);
240 for (size_t selected_row_index : selected_row_indices)
241 {
242 if (selected_row_index < keep_data_row.size())
243 {
244 keep_data_row[selected_row_index] = true;
245 }
246 }
247
248 std::vector<std::string> output_lines;
249 output_lines.reserve(input_lines.size());
250
251 size_t data_cursor = 0;
252 for (size_t line_index = 0; line_index < input_lines.size(); ++line_index)
253 {
254 if (data_cursor < data_line_positions.size() &&
255 data_line_positions[data_cursor] == line_index)
256 {
257 if (keep_data_row[data_cursor])
258 {
259 output_lines.push_back(input_lines[line_index]);
260 }
261 ++data_cursor;
262 }
263 else
264 {
265 output_lines.push_back(input_lines[line_index]);
266 }
267 }
268
269 return output_lines;
270}
271
297template <typename XSelector, typename YSelector>
298inline std::vector<std::string>
299downsampleDatasetToMaxBytes(const std::vector<std::string>& input_lines, size_t max_bytes,
300 size_t min_value_count, XSelector x_selector, YSelector y_selector)
301{
302 std::vector<Point> data_points;
303 std::vector<size_t> data_line_positions;
304 data_points.reserve(input_lines.size());
305 data_line_positions.reserve(input_lines.size());
306
307 std::vector<double> values;
308
309 for (size_t i = 0; i < input_lines.size(); ++i)
310 {
311 if (parseDataRowValues(input_lines[i], values, min_value_count))
312 {
313 Point point{};
314 point.x = static_cast<double>(x_selector(values));
315 point.y = static_cast<double>(y_selector(values));
316 data_points.push_back(point);
317 data_line_positions.push_back(i);
318 }
319 }
320
321 if (data_points.size() <= 2)
322 {
323 return input_lines;
324 }
325
326 // Keep at least first and last data row, then maximize kept rows within byte budget.
327 size_t low = 2;
328 size_t high = data_points.size();
329 size_t best_size = 2;
330
331 while (low <= high)
332 {
333 const size_t mid = low + (high - low) / 2;
334 const std::vector<size_t> selected_rows = downsampleIndices(data_points, mid);
335 const std::vector<std::string> candidate =
336 buildOutputWithSelectedRows(input_lines, data_line_positions, selected_rows);
337 const size_t candidate_size = joinedSizeBytes(candidate);
338
339 if (candidate_size <= max_bytes)
340 {
341 best_size = mid;
342 low = mid + 1;
343 }
344 else
345 {
346 if (mid == 0)
347 {
348 break;
349 }
350 high = mid - 1;
351 }
352 }
353
354 const std::vector<size_t> best_rows = downsampleIndices(data_points, best_size);
355 return buildOutputWithSelectedRows(input_lines, data_line_positions, best_rows);
356}
357} // namespace utils
358} // namespace jaiabot
359
360#endif // JAIABOT_UTILS_DOWNSAMPLE_H
bool parseDataRow(const std::string &line, Point &point_out)
Parses a data row into a point using the first and last numeric columns.
Definition downsample.h:188
std::vector< std::string > downsampleDatasetToMaxBytes(const std::vector< std::string > &input_lines, size_t max_bytes, size_t min_value_count, XSelector x_selector, YSelector y_selector)
Downsamples data rows to fit within a maximum serialized byte budget.
Definition downsample.h:299
bool parseDataRowValues(const std::string &line, std::vector< double > &values_out, size_t min_value_count=2)
Parses a data row into its numeric columns after the integer row index.
Definition downsample.h:157
size_t joinedSizeBytes(const std::vector< std::string > &lines)
Computes the serialized byte size of lines joined with newline separators.
Definition downsample.h:208
std::vector< size_t > downsampleIndices(const std::vector< Point > &data, size_t target_size)
Selects representative point indices while preserving the overall curve shape.
Definition downsample.h:55
std::vector< std::string > buildOutputWithSelectedRows(const std::vector< std::string > &input_lines, const std::vector< size_t > &data_line_positions, const std::vector< size_t > &selected_row_indices)
Rebuilds the output while preserving metadata lines and selected data rows.
Definition downsample.h:235
Simple 2D point used to represent a parsed data row during downsampling.
Definition downsample.h:40