17270491352

Committed 27 Aug 2025 02:57PM UTC coverage: 65.333%. Remained the same

Build # 17270491352

Build Type

push

github

Committed by

paulmthompson

Commit Message

Merge branch 'main' of https://github.com/paulmthompson/WhiskerToolbox

Run Details

352 of 628 new or added lines in 92 files covered. (56.05%)

357 existing lines in 24 files now uncovered.

26429 of 40453 relevant lines covered (65.33%)

1119.34 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/src/CoreGeometry/src/order_line.cpp

#include "CoreGeometry/order_line.hpp"

#include "CoreGeometry/masks.hpp"

#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstddef>  // for size_t

// Find putative endpoints of the line
std::pair<size_t, size_t> find_line_endpoints(const std::vector<Point2D<float>>& points) {
    if (points.size() <= 1) {
        return {0, 0}; // Not enough points
    }
    
    // Step 1: Pick an arbitrary starting point (e.g., the first point)
    size_t start_idx = 0;
    
    // Step 2: Find the point farthest from the starting point
    size_t first_endpoint_idx = 0;
    float max_dist = -1.0f;
    
    for (size_t i = 0; i < points.size(); ++i) {
        float dx = points[i].x - points[start_idx].x;
        float dy = points[i].y - points[start_idx].y;
        float dist = dx * dx + dy * dy;
        
        if (dist > max_dist) {
            max_dist = dist;
            first_endpoint_idx = i;
        }
    }
    
    // Step 3: Find the point farthest from the first endpoint
    size_t second_endpoint_idx = 0;
    max_dist = -1.0f;
    
    for (size_t i = 0; i < points.size(); ++i) {
        float dx = points[i].x - points[first_endpoint_idx].x;
        float dy = points[i].y - points[first_endpoint_idx].y;
        float dist = dx * dx + dy * dy;
        
        if (dist > max_dist) {
            max_dist = dist;
            second_endpoint_idx = i;
        }
    }
    
    return {first_endpoint_idx, second_endpoint_idx};
}

Line2D order_line(
        std::vector<Point2D<uint32_t>> const & line_pixels,
        Point2D<float> const & origin,
        int subsample,
        float tolerance) {

    std::vector<Point2D<float>> line_pixels_float;
    line_pixels_float.reserve(line_pixels.size());
    for (auto const & point : line_pixels) {
        line_pixels_float.push_back({static_cast<float>(point.x), static_cast<float>(point.y)});
    }

    return order_line(line_pixels_float, origin, subsample, tolerance);
}

Line2D order_line(
        std::vector<uint8_t> const & binary_img,
        ImageSize const image_size,
        Point2D<float> const & origin,
        int subsample,
        float tolerance) {

    auto line_pixels = extract_line_pixels(binary_img, image_size);

    return order_line(line_pixels, origin, subsample, tolerance);
}

Line2D order_line(
        std::vector<Point2D<float>> & line_pixels,
        Point2D<float> const & origin,
        int subsample,
        float tolerance) {

    static_cast<void>(tolerance);

    // If there are no line pixels, return empty vector
    if (line_pixels.empty()) {
        return {};
    }

    // Subsample the line pixels if subsample > 1
    if (subsample > 1) {
        std::vector<Point2D<float>> subsampled_pixels;
        subsampled_pixels.reserve(line_pixels.size() / static_cast<size_t>(subsample) + 1);
        
        for (size_t i = 0; i < line_pixels.size(); i += static_cast<size_t>(subsample)) {
            subsampled_pixels.push_back(line_pixels[i]);
        }
        line_pixels = std::move(subsampled_pixels);
    }

    // Find the endpoints of the line
    auto [first_endpoint_idx, second_endpoint_idx] = find_line_endpoints(line_pixels);
    
    // Calculate the distance from the origin to both endpoints to determine orientation
    float dist_origin_to_first = std::pow(line_pixels[first_endpoint_idx].x - origin.x, 2) +
                                 std::pow(line_pixels[first_endpoint_idx].y - origin.y, 2);
    float dist_origin_to_second = std::pow(line_pixels[second_endpoint_idx].x - origin.x, 2) +
                                  std::pow(line_pixels[second_endpoint_idx].y - origin.y, 2);
    
    // Start ordering from the endpoint farthest from the origin
    size_t start_point_idx = (dist_origin_to_first > dist_origin_to_second) ? 
                            first_endpoint_idx : second_endpoint_idx;
    
    const size_t num_points = line_pixels.size();
    
    // Precompute all pairwise distances between points
    std::vector<std::vector<float>> distance_matrix(num_points, std::vector<float>(num_points, 0.0f));
    
    for (size_t i = 0; i < num_points; ++i) {
        for (size_t j = i + 1; j < num_points; ++j) {
            float dx = line_pixels[i].x - line_pixels[j].x;
            float dy = line_pixels[i].y - line_pixels[j].y;
            float dist = dx * dx + dy * dy;
            
            distance_matrix[i][j] = dist;
            distance_matrix[j][i] = dist;
        }
    }
    
    // Initialize the ordered list with the starting point
    std::vector<Point2D<float>> ordered_pixels;
    ordered_pixels.reserve(num_points);
    ordered_pixels.push_back(line_pixels[start_point_idx]);
    
    // Create a visited flag array
    std::vector<bool> visited(num_points, false);
    visited[start_point_idx] = true;
    
    // Track minimum distances
    std::vector<float> min_distances;
    min_distances.reserve(num_points - 1);

    // Iteratively find the nearest neighbor
    size_t current_index = start_point_idx;
    size_t points_remaining = num_points - 1;
    
    while (points_remaining > 0) {
        float nearest_dist = std::numeric_limits<float>::max();
        size_t nearest_neighbor_index = 0;
        bool found_neighbor = false;
        
        // Find the nearest unvisited neighbor using precomputed distances
        for (size_t i = 0; i < num_points; ++i) {
            if (!visited[i]) {
                float dist = distance_matrix[current_index][i];
                
                if (dist < nearest_dist) {
                    nearest_dist = dist;
                    nearest_neighbor_index = i;
                    found_neighbor = true;
                }
            }
        }
        
        if (!found_neighbor) {
            break; // Safety check
        }
        
        // Add the nearest point to the ordered list
        ordered_pixels.push_back(line_pixels[nearest_neighbor_index]);
        min_distances.push_back(nearest_dist);
        
        // Mark as visited and update current point
        visited[nearest_neighbor_index] = true;
        current_index = nearest_neighbor_index;
        points_remaining--;
    }

    // Check if we need to flip the line based on which endpoint is closer to the origin
    bool should_flip = false;
    
    if (!ordered_pixels.empty()) {
        float dist_first_to_origin = std::pow(ordered_pixels.front().x - origin.x, 2) +
                                     std::pow(ordered_pixels.front().y - origin.y, 2);
        float dist_last_to_origin = std::pow(ordered_pixels.back().x - origin.x, 2) +
                                    std::pow(ordered_pixels.back().y - origin.y, 2);
                                   
        should_flip = dist_first_to_origin > dist_last_to_origin;
        
        if (should_flip) {
            std::reverse(ordered_pixels.begin(), ordered_pixels.end());
        }
    }

    return Line2D(ordered_pixels);
}

1	#include "CoreGeometry/order_line.hpp"
2
3	#include "CoreGeometry/masks.hpp"
4
5	#include <algorithm>
6	#include <cmath>
7	#include <limits>
8	#include <vector>
9	#include <cstddef> // for size_t
10
11	// Find putative endpoints of the line
12	std::pair<size_t, size_t> find_line_endpoints(const std::vector<Point2D<float>>& points) {	×
13	if (points.size() <= 1) {	×
14	return {0, 0}; // Not enough points	×
15	}
16
17	// Step 1: Pick an arbitrary starting point (e.g., the first point)
18	size_t start_idx = 0;	×
19
20	// Step 2: Find the point farthest from the starting point
21	size_t first_endpoint_idx = 0;	×
22	float max_dist = -1.0f;	×
23
24	for (size_t i = 0; i < points.size(); ++i) {	×
25	float dx = points[i].x - points[start_idx].x;	×
26	float dy = points[i].y - points[start_idx].y;	×
27	float dist = dx * dx + dy * dy;	×
28
29	if (dist > max_dist) {	×
30	max_dist = dist;	×
31	first_endpoint_idx = i;	×
32	}
33	}
34
35	// Step 3: Find the point farthest from the first endpoint
36	size_t second_endpoint_idx = 0;	×
37	max_dist = -1.0f;	×
38
39	for (size_t i = 0; i < points.size(); ++i) {	×
40	float dx = points[i].x - points[first_endpoint_idx].x;	×
41	float dy = points[i].y - points[first_endpoint_idx].y;	×
42	float dist = dx * dx + dy * dy;	×
43
44	if (dist > max_dist) {	×
45	max_dist = dist;	×
46	second_endpoint_idx = i;	×
47	}
48	}
49
50	return {first_endpoint_idx, second_endpoint_idx};	×
51	}
52
53	Line2D order_line(	×
54	std::vector<Point2D<uint32_t>> const & line_pixels,
55	Point2D<float> const & origin,
56	int subsample,
57	float tolerance) {
58
59	std::vector<Point2D<float>> line_pixels_float;	×
60	line_pixels_float.reserve(line_pixels.size());	×
61	for (auto const & point : line_pixels) {	×
62	line_pixels_float.push_back({static_cast<float>(point.x), static_cast<float>(point.y)});	×
63	}
64
65	return order_line(line_pixels_float, origin, subsample, tolerance);	×
66	}	×
67
68	Line2D order_line(	×
69	std::vector<uint8_t> const & binary_img,
70	ImageSize const image_size,
71	Point2D<float> const & origin,
72	int subsample,
73	float tolerance) {
74
75	auto line_pixels = extract_line_pixels(binary_img, image_size);	×
76
77	return order_line(line_pixels, origin, subsample, tolerance);	×
78	}	×
79
80	Line2D order_line(	×
81	std::vector<Point2D<float>> & line_pixels,
82	Point2D<float> const & origin,
83	int subsample,
84	float tolerance) {
85
86	static_cast<void>(tolerance);
87
88	// If there are no line pixels, return empty vector
89	if (line_pixels.empty()) {	×
90	return {};	×
91	}
92
93	// Subsample the line pixels if subsample > 1
94	if (subsample > 1) {	×
95	std::vector<Point2D<float>> subsampled_pixels;	×
NEW 96	subsampled_pixels.reserve(line_pixels.size() / static_cast<size_t>(subsample) + 1);	×
97
NEW 98	for (size_t i = 0; i < line_pixels.size(); i += static_cast<size_t>(subsample)) {	×
99	subsampled_pixels.push_back(line_pixels[i]);	×
100	}
101	line_pixels = std::move(subsampled_pixels);	×
102	}	×
103
104	// Find the endpoints of the line
105	auto [first_endpoint_idx, second_endpoint_idx] = find_line_endpoints(line_pixels);	×
106
107	// Calculate the distance from the origin to both endpoints to determine orientation
NEW 108	float dist_origin_to_first = std::pow(line_pixels[first_endpoint_idx].x - origin.x, 2) +	×
NEW 109	std::pow(line_pixels[first_endpoint_idx].y - origin.y, 2);	×
NEW 110	float dist_origin_to_second = std::pow(line_pixels[second_endpoint_idx].x - origin.x, 2) +	×
NEW 111	std::pow(line_pixels[second_endpoint_idx].y - origin.y, 2);	×
112
113	// Start ordering from the endpoint farthest from the origin
114	size_t start_point_idx = (dist_origin_to_first > dist_origin_to_second) ?	×
115	first_endpoint_idx : second_endpoint_idx;
116
117	const size_t num_points = line_pixels.size();	×
118
119	// Precompute all pairwise distances between points
120	std::vector<std::vector<float>> distance_matrix(num_points, std::vector<float>(num_points, 0.0f));	×
121
122	for (size_t i = 0; i < num_points; ++i) {	×
123	for (size_t j = i + 1; j < num_points; ++j) {	×
124	float dx = line_pixels[i].x - line_pixels[j].x;	×
125	float dy = line_pixels[i].y - line_pixels[j].y;	×
126	float dist = dx * dx + dy * dy;	×
127
128	distance_matrix[i][j] = dist;	×
129	distance_matrix[j][i] = dist;	×
130	}
131	}
132
133	// Initialize the ordered list with the starting point
134	std::vector<Point2D<float>> ordered_pixels;	×
135	ordered_pixels.reserve(num_points);	×
136	ordered_pixels.push_back(line_pixels[start_point_idx]);	×
137
138	// Create a visited flag array
139	std::vector<bool> visited(num_points, false);	×
140	visited[start_point_idx] = true;	×
141
142	// Track minimum distances
143	std::vector<float> min_distances;	×
144	min_distances.reserve(num_points - 1);	×
145
146	// Iteratively find the nearest neighbor
147	size_t current_index = start_point_idx;	×
148	size_t points_remaining = num_points - 1;	×
149
150	while (points_remaining > 0) {	×
151	float nearest_dist = std::numeric_limits<float>::max();	×
152	size_t nearest_neighbor_index = 0;	×
153	bool found_neighbor = false;	×
154
155	// Find the nearest unvisited neighbor using precomputed distances
156	for (size_t i = 0; i < num_points; ++i) {	×
157	if (!visited[i]) {	×
158	float dist = distance_matrix[current_index][i];	×
159
160	if (dist < nearest_dist) {	×
161	nearest_dist = dist;	×
162	nearest_neighbor_index = i;	×
163	found_neighbor = true;	×
164	}
165	}
166	}
167
168	if (!found_neighbor) {	×
169	break; // Safety check	×
170	}
171
172	// Add the nearest point to the ordered list
173	ordered_pixels.push_back(line_pixels[nearest_neighbor_index]);	×
174	min_distances.push_back(nearest_dist);	×
175
176	// Mark as visited and update current point
177	visited[nearest_neighbor_index] = true;	×
178	current_index = nearest_neighbor_index;	×
179	points_remaining--;	×
180	}
181
182	// Check if we need to flip the line based on which endpoint is closer to the origin
183	bool should_flip = false;	×
184
185	if (!ordered_pixels.empty()) {	×
NEW 186	float dist_first_to_origin = std::pow(ordered_pixels.front().x - origin.x, 2) +	×
NEW 187	std::pow(ordered_pixels.front().y - origin.y, 2);	×
NEW 188	float dist_last_to_origin = std::pow(ordered_pixels.back().x - origin.x, 2) +	×
NEW 189	std::pow(ordered_pixels.back().y - origin.y, 2);	×
190
191	should_flip = dist_first_to_origin > dist_last_to_origin;	×
192
193	if (should_flip) {	×
194	std::reverse(ordered_pixels.begin(), ordered_pixels.end());	×
195	}
196	}
197
198	return Line2D(ordered_pixels);	×
199	}	×

paulmthompson / WhiskerToolbox / 17270491352

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous